Problema 6 Selectivo de IMO 2005

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

Colaborador OFO - Jurado
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Problema 6 Selectivo de IMO 2005

Mensaje sin leer por Nacho » Mié 25 Jul, 2012 11:41 pm

Sea [math] un entero. Diremos que un conjunto de [math] personas es amigable de orden [math] si para toda persona del conjunto, si se excluye a esa persona, hay otras [math] personas tales que en el grupo de las [math] personas son todas amigas entre si. Hallar el máximo valor de [math] tal que todo conjunto de [math] personas que sea amigable de orden [math] contenga necesariamente un grupo de [math] personas que son todas amigas entre sí.
"Though my eyes could see I still was a blind man"

Avatar de Usuario
Prillo

Colaborador OFO - Jurado
Mensajes: 396
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Problema 6 Selectivo de IMO 2005

Mensaje sin leer por Prillo » Vie 27 Jul, 2012 11:22 am

Casi un paper.
Spoiler: mostrar
Primero veamos que [math]. Para ello, basta notar que el grafo de [math] vértices formado por dos componente que son [math]-cliqués cada una satisface la condición del enunciado, pero no tiene ningún [math]-cliqué.

Ahora veamos que todo grafo de [math] vértices con la propiedad del enunciado debe tener un [math]-cliqué. Para ello, supongamos a modo de contradicción que existe un grafo [math] con la propiedad del enunciado de [math] vértices pero que no tiene un [math]-cliqué, y lleguemos a un absurdo.

Le demostración que sigue de basa fuertemente del uso de notación la cual nos va a permitir entender un poco mejor el grafo que tenemos. Después hay varias igualdades asquerosas que intimidan y que necesitamos usar para ser rigurosos, pero viendo los ejemplitos mostrados queda clara la idea de lo que estamos haciendo.

Obviamente [math] contiene al menos dos [math]-cliqués. Más aún, [math] contiene al menos tres [math]-cliqués: si hubiera a los sumo dos [math]-cliqués los podemos reventar sacándoles un vértice en común. Supongamos entonces que [math] contiene exactamente [math] [math]-cliqués, los cuales denotamos [math]. Sea [math]. Vamos a particionar al conjunto [math] de los vértices de [math] en varios subconjuntos, cada uno indexado por un subconjunto de [math]. Lo hacemos de la siguiente forma: Para cada subconjunto [math] (posiblemente vacío) de [math], [math] es el conjunto de aquellos vértices de [math] que pertenecen exactamente a los [math]-cliqués [math]. Más precisamente,
[math]
Es inmediato verificar las siguientes observaciones:

[math] [math] es una partición de [math] como una unión de subconjuntos disjuntos. En particular,
[math]
[math] [math] es un cliqué para cada [math].
[math] [math], pues en caso contrario al retirar un vértice de [math] se destruyen todos los [math]-cliqués, contradiciendo la hipótesis del enunciado.
[math] Para cada [math], se tiene que [math]. En particular,
[math]
Más aún, sumando sobre estas [math] igualdades, cada término [math] se suma una vez por cada [math], y entonces es fácil ver que obtenemos
[math]
[math] Sea [math] una familia de subconjuntos de [math] tal que [math] para cada [math]. Entonces [math] es un cliqué. Esta es una observación crucial a la que recurriremos como (*).

Al hacer la resta [math] nos queda que
[math]
Ahora viene la idea principal, que va a ser la siguiente: Construiremos inductivamente subconjuntos [math] de vértices de [math] con las dos siguientes propiedades:
i. Cada [math] es un cliqué.
ii.
[math]
En tal caso habremos terminado porque tendremos que, como [math] y [math] solo resta,
[math]

[math]
y entonces por Principio del Palomar alguno de los cliqués [math] tendrá al menos [math] elementos, una contradicción a la suposición de que no hay [math]-cliqués.

Vamos a los ejemplos de la construcción para entender lo que haremos. Escribimos por comodidad [math]. Entonces, por ejemplo [math].

Para [math], podemos considerar simplemente [math]. Por (*), [math] es un cliqué, y encima verifica la igualdad ii.

Para [math], tomamos el [math] que teníamos antes y le agregamos los mismos subconjuntos pero agregandoles el número [math]. Nos quedaría
[math]
que trivialmente sigue cumpliendo (*) entonces [math] es un cliqué. Definimos [math] como sigue: [math] es la unión de todos los [math] con [math] tales que [math] pero [math], y además le agregamos al final el [math]. Nos quedaría
[math]
Notar a ojo en este caso chico que [math] resulta un cliqué (después lo demostraremos en el paso inductivo, por ahora solo veamos la idea). Y además se verifica fácilmente a mano la igualdad ii.

Para [math], hacemos con [math] y [math] lo que para [math] hicimos sólo con [math], y definimos [math] en forma análoga a como definimos [math] para [math]. Nos quedaría
[math]
[math]
[math]
[math]
[math]
[math]
Si se fijan estos subconjuntos cumplen con i y también la cuenta de ii (se puede ver a mano).

Ahora al paso inductivo. Supongamos que para algún [math] hemos conseguido subconjuntos [math]
con las propiedades de arriba. Hallemos una tal familia para [math]. Consideremos los conjuntos [math] donde abusando un poco de notación, [math]. Es fácil ver que los [math] son cliques porque si [math] cumple (*) entonces se verifica también fácilmente para [math]. Definimos el conjunto [math] como sigue: [math] es la unión de todos los [math] tales que [math], [math], [math], y encima agregamos por último el conjunto [math]. [math] cumple con (*) porque: si [math] y [math] ya está ([math] y [math] tendrían intersección no vacía). El único caso a considerar es entonces el que involucra al conjunto [math], pero este se interseca trivialmente con cualquier otro [math] que aparece en [math] porque [math] (acá es donde usamos que no estamos incluyendo el [math]) Ahora verifiquemos la cuenta monstruosa en ii. Usando la hipótesis inductiva, miremos la suma
[math]
que queremos ver que es igual a
[math]
Pero usando la hipótesis inductiva,
[math]

[math]

[math]

[math]
Ahora solo hay que verificar que cada cosa está en su lugar: Si [math] es un subconjunto propio de [math], entonces [math] aparece sumado [math] veces en la primer suma. Si [math] entonces [math] aparece sumado [math] veces en la primera suma y una última vez en la tercera (la aparición que nos da [math]), o sea en total [math]. Los [math] con [math] propios que contienen al [math] pero no son [math] aparecen sumados [math] veces en la segunda suma, mas una última vez en la tercer suma, dándonos [math] apariciones en total. Por último, para [math], [math] aparece sumado [math] veces en la segunda suma, y una última en la tercera, es decir en total [math] veces. O sea que todo está en su lugar y el paso inductivo se completa.

Con esto hecho, ahora en nuestro problema podemos construir [math] con las propiedades i y ii, llevándonos a la existencia de un [math]-cliqué, contradicción!
2  

juandodyk
Mensajes: 4
Registrado: Mar 26 Jun, 2018 1:59 am
Nivel: Exolímpico

Re: Problema 6 Selectivo de IMO 2005

Mensaje sin leer por juandodyk » Mar 26 Jun, 2018 2:12 am

Se cumplen 10 años desde que empecé a pensar este problema. Finalmente creo que me salió. La solución es algo distinta a la de Prillo.
Spoiler: mostrar
Antes de empezar: llamo $G$ al grafo y asumo que la cantidad de vértices es a lo sumo $2n-1$ y lo que hay que probar es que tiene un $n+1$-clique. (Si el grafo tiene al menos $2n$ vértices puede no haber un $n+1$-clique, por ejemplo si hay dos $n$-cliques disjuntos.)

Sea $u_1$ un vértice, y sea $A_1$ un $n$-clique en $G \smallsetminus \{u_1\}$. Sea $u_2 \in A_1$, y sea $A_2$ un $n$-clique en $G \smallsetminus \{u_2\}$. Sea $u_3 \in A_1 \cap A_2$ (si no es vacío), y sea $A_3$ un $n$-clique en $G \smallsetminus \{u_3\}$. Continuando este proceso obtenemos $k$ $n$-cliques $A_1, \ldots, A_k$ tales que $A_1 \cap \cdots \cap A_k = \emptyset$ pero $A_1 \cap \cdots \cap A_{k-1} \neq \emptyset$. Notar que $k\geqq 3$, ya que $k\neq1$ porque $A_1 \neq \emptyset$, y $k\neq2$ porque si $A_1 \cap A_2 = \emptyset$, $|A_1 \cup A_2| = 2n$, pero hay a lo sumo $2n-1$ vértices.

Supongamos que $i\in\{1,\ldots,k\}$ cumple que $\bigcap_{j\neq i} A_j = \emptyset$. Sea $G'$ un grafo formado con los vértices de $G$ y las aristas de los cliques $A_j$ con $j\neq i$. Cumple la condición: si $u\in G'$, como $\bigcap_{j\neq i} A_j = \emptyset$ hay $j\neq i$ con $u\not\in A_j$, luego hay un $n$-clique en $G'\smallsetminus\{u\}$. Bastaría probar que hay un $n+1$-clique en $G'$, ya que también estará presente en $G$. Por lo tanto podemos asumir que, para todo $i$, $\bigcap_{j\neq i} A_j \neq \emptyset$. Es más, asumimos que las aristas de $G$ son sólo aquellas presentes en los cliques $A_i$; es decir, $u,v$ están conectados si y sólo si pertenecen a un mismo clique $A_i$.

Si $j=1,\ldots,k$ sea $\Gamma_j$ el conjunto de vértices de $G$ que están en exactamente $j$ de los $n$-cliques $A_i$, y sea $N_j = |\Gamma_j|$. Tenemos que $|A_1| + \cdots + |A_k| = kn$, y también es $N_1 + 2N_2 + \cdots + kN_k$, por lo que $\sum_{j=1}^k jN_j = kn$. Notar que por lo anterior $N_k=0$ y $N_{k-1} \geqq 1$.

Si $u\in\Gamma_r$ y $v\in\Gamma_s$ con $r+s\geqq k+1$ entonces $u$ y $v$ están conectados; en efecto, si $U$ es el conjunto de cliques en los que está $u$ y $V$ en los que está $v$, tenemos $|U \cap V| = r + s - |U \cup V| \geqq k + 1 - k = 1$, por lo que están en un clique común, y por lo tanto están conectados. En particular $\Gamma_{k-1}$ es un clique ya que $2(k-1) \geqq k+1$ pues $k\geqq 3$, y si $B \subset \Gamma_2 \cup \cdots \cup \Gamma_{k-2}$ es un clique, entonces $B \cup \Gamma_{k-1}$ también.

Vamos a probar el teorema por inducción. El caso $n=2$ es obvio. Suponemos que el teorema es cierto para $n-1$ y lo vamos a probar para $n$.

Supongamos que $N_1 \neq 0$. Sea pues $u \in \Gamma_1$, y sea $i$ con $u \in A_i$. Vimos que podemos asumir que $\bigcap_{j\neq i} A_j \neq \emptyset$, así que sea $v \in \bigcap_{j\neq i} A_j$. Veamos que $G' = G \smallsetminus \{u, v\}$ cumple las condiciones del teorema para $n-1$. En efecto, si $w$ es un vértice de $G'$, hay $j$ con $w\not\in A_j$; si $j=i$, como $v\not\in A_i$ tenemos que $A_i \smallsetminus \{u\}$ es un $n-1$-clique en $G' \smallsetminus \{w\}$; si $j\neq i$, como $u\not\in A_j$ tenemos que $A_i \smallsetminus \{u\}$ es un $n-1$-clique en $G' \smallsetminus \{w\}$; en ambos casos en $G' \smallsetminus \{w\}$ hay un $n-1$-clique. Por lo tanto, por hipótesis inductiva, hay un $n$-clique $B$ en $G \smallsetminus \{u, v\}$. Veamos que $B \cup \{v\}$ es un $n+1$-clique. Esto sólo podría no ocurrir si hay $w \in B$ que sólo está en $A_i$, ya que si está en $A_j$ con $j\neq i$, como $v\in A_j$, $u$ y $v$ están conectados. Ahora si hay $w\in B$ que sólo está en $A_i$, para que esté conectado al resto de los vértices de $B$ debe suceder que $B = A_i$, pero $u\not\in B$ ya que $B\subset G \smallsetminus \{u, v\}$. Probamos, pues, que si $N_1 \neq 0$ hay un $n+1$-clique, y terminamos.

Supongamos, para terminar, que $N_1 = 0$. Tenemos que $2N_2 + \cdots + (k-1)N_{k-1} = kn$. Veamos que en $C=\Gamma_2 \cup \cdots \cup \Gamma_{k-2}$ hay un clique de tamaño al menos $\left\lceil \frac{2N_2 + \cdots + (k-2)N_{k-2}}k \right\rceil$. En efecto, si $a_i = |C \cap A_i|$ tenemos $a_1 + \cdots + a_k = 2N_2 + \cdots + (k-2)N_{k-2}$, por lo que hay $i$ con $a_i \geqq \left\lceil \frac{2N_2 + \cdots + (k-2)N_{k-2}}k \right\rceil$. Esos vértices están en $C$ y en $A_i$, por lo que forman un clique $B$ de tamaño al menos $\left\lceil \frac{2N_2 + \cdots + (k-2)N_{k-2}}k \right\rceil$, como dije. Como probé antes, $B \cup \Gamma_{k-1}$ es un clique, de tamaño al menos $\left\lceil \frac{2N_2 + \cdots + (k-2)N_{k-2}}k \right\rceil + N_{k-1} = \left\lceil \frac{2N_2 + \cdots + (k-1)N_{k-1}}k + \frac{N_{k-1}}k \right\rceil = n+1$, como queríamos.
1  

Responder