OMEO 2019 N3 P2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
MateoCV

OFO - Medalla de Bronce-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 FOFO 7 años - Medalla Especial-FOFO 7 años
OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021
Mensajes: 255
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 14
Nivel: Exolímpico
Ubicación: Córdoba

OMEO 2019 N3 P2

Mensaje sin leer por MateoCV »

Consideramos un grupo de $n>1$ personas. Cualesquiera dos personas de este grupo están relacionadas por amistad o enemistad mutua. Todo amigo de un amigo y todo enemigo de un enemigo es un amigo. Si $A$ y $B$ son amigos/enemigos entonces lo contamos como $1$ amistad/enemistad. Observamos que el número de amistades y el número de enemistades son iguales en el grupo. Encuentre todos los posibles valores de $n$.
$2^{82589933}-1$ es primo
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2210
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: OMEO 2019 N3 P2

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Armamos el grafo $G$ donde las personas son los vértices y dos vértices son adyacentes si y sólo si las personas son amigas, como para cada par de personas sólo hay dos opciones, ser amigas o enemigas, tenemos además que dos vértices no son adyacentes si y sólo si las personas no son amigas. Entonces si $A$ es adyacente a $B$ y $B$ es adyacente a $C$, resulta que $A$ es adyacente a $C$; y si $A$ no es adyacente a $B$ y $B$ no es adyacente a $C$, resulta que $A$ es adyacente a $C$. Por lo tanto, el subgrafo formado por los amigos de $A$ es un clique (que llamamos $a$), el subgrafo formado por los enemigos de $A$ es un clique (que llamamos $e$), no hay ningún vértice que no pertenezca a alguno de estos subgrafos y ningún vértice de $a$ es adyacente a un vértice de $e$. Notemos además que $G$ es un subgrafo de $K_n$, el clique de $n$ vértices.
Sean $x$ la cantidad de vértices de $a$ e $y$ la cantidad de vértices de $e$ (entonces $x+y=n$), como $a$ y $e$ son cliques tenemos que la cantidad de aristas de $a$ es $\frac{x(x-1)}{2}$ y la cantidad de aristas de $e$ es $\frac{y(y-1)}{2}$, entonces la cantidad de aristas (amistades) de $G$ es $\frac{x(x-1)+y(y-1)}{2}=\frac{x^2-x+y^2-y}{2}$, y la cantidad de aristas borradas de $K_n$ (enemistades) para llegar a $G$ es $xy$ (porque a cada vértice de $a$ se le borran todas las aristas que lo conectan con un vértice de $e$). Luego, $\frac{x^2-x+y^2-y}{2}=xy\Leftrightarrow x^2-x+y^2-y=2xy\Leftrightarrow x^2-2xy+y^2=x+y\Leftrightarrow (x-y)^2=x+y$, entonces si $n$ funciona, es un cuadrado perfecto. (*)
Veamos que si $(x,y)$ con $x,y\in \mathbb{N}$ y $x>y$ es solución de $k^2=(x-y)^2=x+y$ con $k\in \mathbb{N}$, entonces $(x',y')=(x+k+1,y+k)$ es solución de $(k+1)^2=(x'-y')^2=x'+y'$. En efecto, como $x,y\in \mathbb{N}$ y $x>y$, de la primer igualdad se desprende $x-y=k$, luego $x'-y'=x+k+1-y-k=x-y+1=k+1$, por lo que $(x'-y')^2=(k+1)^2$. Por otro lado, $x'+y'=x+k+1+y+k=x+y+2k+1=k^2+2k+1=(k+1)^2$. Finalmente $x>y\Rightarrow x'=x+k+1>y+k=y'$, y claramente todas las variables son naturales. Como $(x,y)=(3,1)$ es solución para $k=2$, por inducción tenemos que hay solución para todo $k\geqslant 2$, es decir, para todos los cuadrados perfectos mayores a $1$. (**)
De (*) y (**) tenemos que $n$ es solución si y sólo si es un cuadrado perfecto.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
JPablo
Mensajes: 360
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Re: OMEO 2019 N3 P2

Mensaje sin leer por JPablo »

Misma solución en otro lenguaje; y una manera más corta y concisa de probar la vuelta:
Spoiler: mostrar
Sea $G$ el grupo de personas. Definimos una relación $\sim $ en $G$ de modo que, para todo $\left (x,y\right )\in G^2$, $x\sim y$ si y solo si $x=y$ o bien $x$ y $y$ son amigos. Es claro, por definición, que $x\sim x$ para todo $x\in G$. Como la relación de amistad es mutua, si $x,y\in G$ entonces $x\sim y$ si y solo si $y\sim x$. Por otra parte, el hecho de que "todo amigo de un amigo es un amigo" nos dice que si $x,y,z\in G$ son tales que $x\sim y$ y $y\sim z$, entonces $x\sim z$. Concluimos entonces que $\sim $ define una relación de equivalencia en $G$. Sea $m\in \mathbb{N}$ la cantidad de clases de equivalencia y sea $\left \{G_i:i\in \left [1,m\right ]\cap \mathbb{N}\right \}$ el conjunto de clases de equivalencia.

De esta forma, dos personas son amigas si y solo si pertenecen a la misma clase de equivalencia, y son enemigas en caso contrario. Supongamos que $m\geq 3$. Entonces sea $x\in G_1$, sea $y\in G_2$ y sea $z\in G_3$. Como pertenecen a distintas clases de equivalencia, son enemigos dos a dos, lo cual contradice que todo enemigo de un enemigo es un amigo. Por otra parte, si fuera $m=1$, se tendría que son todos amigos entre sí y no hay enemistad, contradiciendo la hipótesis que dice que hay tantas relaciones de amistad como de enemistad. Por lo tanto, necesariamente debe ser $m=2$. Sea $a$ el cardinal de $G_1$ y sea $b$ el cardinal de $G_2$. Entonces $a+b=n$.

Tenemos $\binom{a}{2}=\frac{a\left (a-1\right )}{2}$ relaciones de amistad entre los integrantes de $G_1$ y $\binom{b}{2}=\frac{b\left (b-1\right )}{2}$ relaciones de amistad entre los integrantes de $G_2$. No puede haber otras relaciones de amistad porque estas solamente se dan dentro de $G_1$ o dentro de $G_2$. Por otra parte, tenemos $ab$ relaciones de enemistad (cada integrante de $G_1$ es enemigo de todos los integrantes de $G_2$, o sea que por cada integrante de $G_1$ tenemos $b$ relaciones de enemistad).

Así, la cantidad de amistades y la cantidad de enemistades coinciden si y solo si $\frac{a\left (a-1\right )}{2}+\frac{b\left (b-1\right )}{2}=ab$, lo cual se puede reescribir como $\left (a-b\right )^2=a+b$, y como $a+b=n$, concluimos que $n$ debe ser un cuadrado perfecto.

Recíprocamente, si $n>1$ y $n=k^2$ con $k\in \mathbb{N}$, queremos ver que existe $\left (a,b\right )\in \mathbb{N}^2$ tal que $a+b=n$ y $a-b=k$. Como $n>1$, entonces $n>k$. Además $n$ y $k$ tienen la misma paridad. Por lo tanto, tomando $\left (a,b\right )=\left (\frac{n+k}{2},\frac{n-k}{2}\right )$ obtenemos lo que queremos.

Entonces la respuesta es que $n$ puede tomar cualquier valor que sea un cuadrado perfecto mayor que $1$.
Responder