Selectivo Cono Sur 1997 P6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020
Mensajes: 956
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

Selectivo Cono Sur 1997 P6

Mensaje sin leer por Matías V5 » Lun 16 Abr, 2012 7:51 pm

En un grupo de [math] personas, cada dos de ellas son amigos o enemigos y cada una tiene exactamente [math] enemigos. Además se cumple la ley:
“Los enemigos de mis amigos son mis enemigos”.
¿Qué valores puede tener [math]?
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020
Mensajes: 956
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

Re: Semana de Entrenamiento para la Cono Sur - Día 4

Mensaje sin leer por Matías V5 » Mar 17 Abr, 2012 9:32 pm

Spoiler: mostrar
La clave está en notar que cualquier conjunto de personas donde se cumpla la "ley" que menciona el enunciado se puede dividir en grupos de manera que dentro de un mismo grupo todos son amigos entre sí, y nadie tiene amigos fuera del grupo.
Para probar esto, observemos primero que si dos personas [math] e [math] tienen un amigo en común [math], necesariamente [math] e [math] son amigos (si no fuera así, [math] tendría un amigo que es enemigo de [math], contradiciendo la ley).
Con esto ya podemos hacer la división en grupos que decíamos. Tomemos una persona cualquiera [math], y formamos un grupo con [math] y todos los amigos de [math]. Por lo que dijimos antes, cada par de estas personas son amigas entre sí, y no pueden tener ningún amigo fuera del grupo. Ahora tomemos una persona [math] que no esté en el primer grupo y formamos un grupo junto con sus amigos. Repetimos este proceso hasta que no haya más personas.
Como cada persona tiene la misma cantidad de enemigos, también cada persona tiene la misma cantidad de amigos, así que todos los grupos tienen la misma cantidad de personas. Supongamos que hay [math] grupos y que cada uno tiene [math] personas, entonces [math] y además como cada persona tiene exactamente [math] enemigos es [math]. De modo que [math], y [math] puede ser cualquier divisor positivo de [math]. Los posibles valores de [math] son entonces [math] y [math].
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Carolang
Mensajes: 65
Registrado: Vie 05 Nov, 2010 12:14 am
Nivel: Exolímpico
Ubicación: Flores

Re: Semana de Entrenamiento para la Cono Sur - Día 4

Mensaje sin leer por Carolang » Mar 17 Abr, 2012 10:36 pm

Problema íntimamente relacionado, el problema 2 de la maratón (problema 4 de nivel 2 del nacional de OMA de 2007):

http://omaforos.com.ar/viewtopic.php?p=30#p29
Se dibujan [math] rectas distintas en el plano. Se sabe que cada recta corta exactamente a otras [math] rectas. Hallar los valores de [math] para los cuales esta situación es posible.

La relación, en spoiler por si alguien lo quiere pensar:
Spoiler: mostrar
Podemos decir que dos rectas son "amigas" si son paralelas, y "enemigas" si no lo son. Vemos que se cumple la "ley": si dos rectas son amigas (paralelas), tienen el mismo conjunto de rectas con las que se cortan (todas las que no van en su dirección). Entonces por definición tienen el mismo conjunto de rectas enemigas. Se traduce la ley como "dada una recta [math], las rectas que intersecan a las paralelas de [math] también intersecan a [math]".
Entonces existe una analogía entre los "cliqués de amigos" del problema anterior y "grupos de rectas paralelas" en este problema. Al final, la cuenta es la misma.
1  
Imagen Azúcar, flores y muchos colores.

alerodri1976
Mensajes: 4
Registrado: Jue 20 Feb, 2020 7:21 pm
Nivel: Ñandú

Re: Selectivo Cono Sur 1997 P6

Mensaje sin leer por alerodri1976 » Vie 28 Feb, 2020 6:30 pm

Spoiler: mostrar
Tomemos a una persona cualquiera y llamémosle Ana. Por el enunciado Ana tiene $10$ enemigos. Llamemos a uno de ellos Eduardo ¿Cuántos amigos puede tener Ana? Ana puede tener a lo sumo $9$ amigos ya que si tiene $10$ o más amigos entonces Eduardo tiene $11$ o más enemigos. Entonces sabemos que hay como mínimo $11$ personas (Ana y sus $10$ enemigos) y como máximo $20$ personas (Ana, sus $9$ amigos y sus $10$ enemigos).

Supongamos ahora que Ana tiene $X$ amigos. Eduardo entonces tiene $X+1$ enemigos y hay otras $9$ personas que faltaría determinar su relación con Eduardo. Llamemos $Y$ a la cantidad de amigos de Eduardo. Como Eduardo también tiene $10$ enemigos tenemos que $10=(X+1)+(9-Y)$, donde $9-Y$ son los enemigos que comparte con Ana. Resolvemos y obtenemos $Y=X$. Por lo tanto Ana y Eduardo tienen la misma cantidad de amigos. Como no hay nada de especial en Eduardo como enemigo de Ana lo mismo podemos concluir para Ernesto, Ema y cualquier otro enemigo de Ana. O sea que los $10$ enemigos de Ana tienen que estar dividos en $G$ grupos de amigos de $X+1$ miembros cada uno. Entonces podemos concluir que $X+1$ puede ser $1$, $2$, $5$ ó $10$ en cuyo caso $G$ sería $10$, $5$, $2$ ó $1$, respectivamente. En conclusión el número total de personas puede ser $11$, $12$, $15$ ó $20$.

Responder