En una competencia de matemáticas algunos participantes son amigos. La amistad es siempre recíproca. Decimos que un grupo de participantes es una cliqué si dos cualesquiera de ellos son amigos. (En particular, cualquier grupo con menos de dos participantes es una cliqué). Al número de elementos de una cliqué se le llama tamaño.
Se sabe que en esta competencia el mayor de los tamaños de las cliqués es par.
Demostrar que los participantes pueden distribuirse en dos aulas, de manera que el mayor de los tamaños de las cliqués contenidos en un aula sea igual al mayor de los tamaños de las cliqués contenidos en la otra.
Básicamente si numeramos a los participantes de 1 a n, el conjunto se parte en subconjuntos propios y disjuntos. Por ejemplo para n=14
{1}, {2},;{3,4}, {5,6,7},{8,9,10}, {11,12,13,14}
Osea que el que corresponde a 1 no tiene amigos, el 2 tampoco, el 5,6 y 7 son amigos, etc.
Luego la única forma de "achicar" los tamaños es que los amigos que están en el mismo grupo vayan a salas distintas.
Estrategia: Si 2N es el tamaño del mayor cliqué
Si hay al menos dos representantes con ese tamaño, deben ir por lo menos un representante por aula.
Si hay solo un representante, debo partirlos en dos grupos de N, pero también debo separar todos los grupos: los de tamaño 2K en dos de tamaño K, los de tamaño 2K+1 uno en tamaño K y el otro K+1. Y por último mandar un grupo de tamaño N a cada sala, y los demás nuevos grupos mandarlos a cualquier aula.
Básicamente si numeramos a los participantes de 1 a n, el conjunto se parte en subconjuntos propios y disjuntos. Por ejemplo para n=14
{1}, {2},;{3,4}, {5,6,7},{8,9,10}, {11,12,13,14}
Osea que el que corresponde a 1 no tiene amigos, el 2 tampoco, el 5,6 y 7 son amigos, etc.
Los grupos de amigos no son "cerrados", o sea, no tienen que ser únicamente amigos entre ellos.
Si te estoy entendiendo bien, lo que vos decís es que cada uno es amigo con todos los de su grupo, el problema es que puede pasar por ejemplo que $7$ sea amigo de $12$ y de $14$, pero no de $11$ o de $13$. Entonces no podés dividir a todos los participantes en cliqués disjuntas.
Si hay solo un representante, debo partirlos en dos grupos de N, pero también debo separar todos los grupos: los de tamaño 2K en dos de tamaño K, los de tamaño 2K+1 uno en tamaño K y el otro K+1. Y por último mandar un grupo de tamaño N a cada sala, y los demás nuevos grupos mandarlos a cualquier aula.
Y justamente por lo que dije antes es que falla la estrategia
Puede ser que sin importar cómo los distribuyas, si mandás $N$ y $N$ a cada aula, entonces siempre pase que en exactamente una de las dos haya algún participante que es amigo de todos los $N$ que mandaste ahí, entonces te va a quedar una cliqué de tamaño $N+1$.
PD: El problema es un 3 de IMO, así que no es sencillo