IMO 2019 - P3

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 922
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

IMO 2019 - P3

Mensaje sin leer por Matías V5 » Mar 16 Jul, 2019 9:34 am

Una red social tiene $2019$ usuarios, algunos de los cuales son amigos. Siempre que el usuario $A$ es amigo del usuario $B$, el usuario $B$ también es amigo del usuario $A$. Eventos del siguiente tipo pueden ocurrir repetidamente, uno a la vez:

Tres usuarios $A$, $B$ y $C$ tales que $A$ es amigo de $B$ y de $C$, pero $B$ y $C$ no son amigos, cambian su estado de amistad de modo que $B$ y $C$ ahora son amigos, pero $A$ ya no es amigo ni de $B$ ni de $C$. Las otras relaciones de amistad no cambian.

Inicialmente, hay $1010$ usuarios que tienen $1009$ amigos cada uno, y hay $1009$ usuarios que tienen $1010$ amigos cada uno. Demostrar que hay una sucesión de este tipo de eventos después de la cual cada usuario es amigo como máximo de uno de los otros usuarios.
1  
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 999
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: IMO 2019 - P3

Mensaje sin leer por Gianni De Rico » Vie 26 Jul, 2019 12:21 pm

Solución:
Spoiler: mostrar
Representamos el problema con un grafo $G$ en el que los usuarios son los nodos y dos nodos $A$ y $B$ están unidos por una arista si y sólo si $A$ y $B$ son amigos. Entonces la operación consiste en tomar tres nodos $A,B,C$ tales que $AB$ y $AC$ son aristas pero $BC$ no lo es, eliminar las aristas $AB$ y $AC$, y agregar la arista $BC$.
Decimos que un grafo es ganador si realizando algunas operaciones (posiblemente $0$), podemos llegar a un grafo en el que todos sus vértices tienen grado a lo sumo $1$. Luego, queremos demostrar que cualquier grafo que cumpla las condiciones del enunciado es ganador.

Observación 1: $G$ es conexo.
Demostración:
En efecto, si dos vértices $u$ y $v$ no están conectados, entonces entre los dos tienen al menos $1009+1009=2018$ vecinos, pero al haber $2017$ vértices distintos de $u$ y $v$, por Palomar hay al menos uno que es vecino de ambos.

Observación 2: El grado de cada vértice es invariante módulo $2$ bajo la operación.
Demostración:
Al aplicar la operación resulta $\delta (A)\to \delta (A)-2$, $\delta (B)\to \delta (B)+1-1=\delta (B)$ y $\delta (C)\to \delta (C)+1-1=\delta (C)$.

Observación 3: La cantidad de aristas decrece en uno al aplicar la operación.
Demostración:
Sea $m$ la cantidad de aristas de $G$. Al aplicar la operación resulta $m\to m-2+1=m-1$, pues eliminamos las aristas $AB$ y $AC$, y agregamos la arista $BC$.

Lema: Un árbol es ganador
Demostración:
Spoiler: mostrar
Por inducción fuerte sobre $n$, donde $n$ es la cantidad de vértices del grafo.
Consideremos como casos base $n=1,2,3$.
Los casos $n=1$ y $n=2$ son ganadores pues cumplen con las condiciones del enunciado al ser un vértice y una arista, respectivemente. El caso $n=3$ es ganador pues el grafo es un camino del longitud $3$, sobre el que podemos aplicar la operación (y de una única forma).
Supongamos como hipótesis inductiva que un árbol de $n$ vértices es ganador para todo $n\leqslant k$. Veamos que un grafo de $k+1$ vértices es ganador.
En efecto, sea $T$ un árbol de $k+1$ vértices, y consideremos los nodos $A,B,C$ tales que $A$ es vecino de $B$ y $C$, pero $B$ no es vecino de $C$.
Entonces la operación tiene esta forma:

IMO 2019 P3.png

Como $T$ es un árbol, entonces ningún nodo de $V_1$ es vecino de un nodo de $V_2$ o $V_3$, y ningún nodo de $V_2$ es vecino de un nodo de $V_3$, pues en caso contrario existe un ciclo en $T$, lo que contradice que sea un árbol. Luego, las dos componentes conexas son árboles y tienen a lo sumo $k$ vértices, entonces son ganadoras por hipótesis inductiva, luego, $T$ es ganador. Esto completa la inducción. $\blacksquare$
Supongamos que luego de aplicar algunas operaciones, llegamos a un punto en el que al aplicar una operación podemos hacer que el grafo sea disconexo. Veamos entonces que o bien el grafo es un árbol o podemos aplicar otra operación que no desconecta el grafo.
En efecto, supongamos que el grafo no es un árbol. Como es conexo, entonces tiene al menos un ciclo, consideremos uno de los ciclos de menor tamaño, digamos $\mathcal{C}$. Tenemos dos casos
Caso 1: Hay al menos un vértice que no pertenece al ciclo
Spoiler: mostrar
Como el grafo es conexo, alguno de los vértices que no pertenecen $\mathcal{C}$ debe ser adyacente a por lo menos un vértice de $\mathcal{C}$. Sea $C$ un vértice que verifica esto y sea $A$ un vértice de $\mathcal{C}$ tal que $AC$ es una arista de $G$. Sea $B\in \mathcal{C}$ un vecino de $A$, si $BC$ no es una arista, podemos realizar la operación y el grafo no se desconecta; si $BC$ es una arista, entonces $ABC$ es un triángulo, por lo que $\mathcal{C}$ debe ser un triángulo, al ser uno de los ciclos de menor tamaño. Sea entonces $D\in \mathcal{C}$, si $C$ no es adyacente a $D$, entonces podemos aplicar la operación en $A,D,C$ sin que se desconecte el grafo. Si $C$ es adyacente a $D$, entonces el subgrafo de $G$ inducido por $ABCD$ es completo.

Veamos ahora por inducción en $n$ que si tenemos una clique (esto es, un subgrafo que induce un grafo completo) de $n\geqslant 3$ vértices, siempre podemos "desarmarla" (esto es, deja de ser una clique) con alguna operación que no desconecta el grafo, o bien tenemos una clique de $n+1$ vértices.
El caso base $n=3$ ya lo vimos. Supongamos como hipótesis inductiva que vale para $n=k-1$, veamos que vale para $n=k$.
En efecto, tomemos un vértice cualquiera (digamos $Y$) adyacente a la clique (digamos en el vértice $X$), si existe algún vértice de la clique al que $X$ no es adyacente (digamos $Z$), podemos aplicar la operación en $X,Y,Z$, la clique se desarma y el grafo no se desconecta. Si no existe tal $Z$, entonces $X$ es adyacente a todos los vértices de la clique, y tenemos una clique $k+1$ vértices. Esto completa la inducción.
Como el grafo inicial $G$ no es completo pues hay al menos un vértice de grado $1010$, no podemos tener una clique de $2019$ vértices, por lo tanto, siempre podemos desarmar las cliques, es decir, siempre podemos operar y mantener el grafo conexo. Pero por la Observación 3 este proceso no puede continuar infinitamente. Entonces debemos llegar a un grafo que no contiene ninguna clique, luego, podemos operar en cada ciclo y eliminarlo, manteniendo el grafo conexo. Por lo que luego de una cantidad finita de pasos llegaremos a un grafo conexo y sin ciclos, es decir, a un árbol.
Caso 2: Todos los vértices pertenecen al ciclo
Spoiler: mostrar
Entonces ningún vértice está conectado con otro que no sean sus vecinos en $\mathcal{C}$ (o sea, que las aristas sean aristas de $\mathcal{C}$), pues en ese caso se formaría un ciclo de menor tamaño que $\mathcal{C}$, absurdo.
Por lo tanto, todos los vértices tienen grado $2$, pero por la Observación 2 y como hay al menos un vértice de grado $1009$, tenemos que hay al menos un vértice de grado impar. Absurdo.
Entonces este caso no puede pasar.
Por lo tanto, si el grafo no es un árbol, podemos convertirlo en un árbol luego de una cantidad finita de operaciones. Pero por el Lema tenemos que un árbol es ganador, luego, $G$ es ganador. Queda demostrado el problema.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
[math]

Responder