OFO 2020 Problema 9

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

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-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 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 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
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

OFO 2020 Problema 9

Mensaje sin leer por AgusBarreto »

En una olimpíada de matemática muchos participantes hicieron nuevos amigos. Al finalizar la olimpíada se observó que en cualquier grupo de 4 participantes, o bien hay 3 participantes que son todos amigos entre sí o bien hay 3 participantes tales que ningún par de ellos son amigos.
Demostrar que es posible distribuir a los participantes de esta olimpíada en dos aulas $A$ y $B$ de manera tal que en el aula $A$ todos los participantes son amigos entre sí, y en el aula $B$ no hay dos participantes que sean amigos.

Aclaraciones: La amistad es recíproca, es decir, si $X$ es amigo de $Y$, entonces $Y$ es amigo de $X$.
Está permitido que una de las dos aulas quede vacía.
Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-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 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 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
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: OFO 2020 Problema 9

Mensaje sin leer por AgusBarreto »

Solución oficial:
Spoiler: mostrar
De entre todos los alumnos, tomemos un grupo en el que todos son amigos con todos con la máxima cantidad de alumnos posible. Llamaremos $G$ a este grupo. Afirmo que poner a los alumnos de $G$ en el aula $A$ y a los demás en el aula $B$ cumple las condiciones del enunciado. Para probar esto basta con demostrar que si tomo dos alumnos fuera de $G$, éstos no son amigos. Si hay sólo uno o ningún alumno fuera del grupo $G$ no hay nada que probar, así que supongamos que hay al menos dos.

Tomemos $v$ y $w$ dos alumnos fuera del grupo $G$ y supongamos, a modo de contradicción, que éstos son amigos. Si $v$ (respectivamente $w$) fuese amigo de todos los integrantes de $G$, podría agregar $v$ (respectivamente $w$) a $G$ y así obtener un grupo con más alumnos que $G$ en el cuál todos son amigos con todos, pero esto es absurdo ya que tomamos a $G$ con la máxima cantidad de alumnos posible. Luego, como el absurdo provino de suponer que o bien $v$ o bien $w$ era amigo de todos los integrantes de $G$, concluímos que existe algún integrante de $G$ — que llamaremos $v'$ — tal que $v$ no es su amigo y que existe algún integrante de $G$ — que llamaremos $w'$ — tal que $w$ no es su amigo.


Caso 1: podemos elegir $v'$ y $w'$ de manera que sean alumnos distintos.

Recordemos que $v$ y $w$ son amigos y además, como $v'$ y $w'$ pertenecen ambos a $G$, son otra pareja de amigos. Consideremos el grupo de $4$ personas $\{v, w, v', w'\}$ y observemos que cualquier subconjunto de $3$ personas tiene, o bien a $v$ y $w$, o bien a $v'$ y $w'$, y por lo tanto, como siempre tenemos una pareja de amigos, no puede haber $3$ tales que ninguno sea amigo de ninguno. De la misma forma, cualquier subconjunto de $3$ personas tiene, o bien a $v$ y $v'$, o bien a $w$ y $w'$, por lo tanto, como siempre tenemos una pareja de no-amigos, no puede haber $3$ tales que todos son amigos con todos. Juntando estos dos últimos hechos llegamos a que el cuarteto $\{v, w, v', w'\}$ no cumple las condiciones del enunciado y por lo tanto este caso no puede ocurrir.

Caso 2: hay un sólo no-amigo de $v$ en $G$ y un sólo no-amigo de $w$ en $G$, y son el mismo alumno (lo llamaremos $v'$).

En este caso tenemos que tanto $v$ como $w$ son amigos de todos los integrantes de $G$ excepto de $v'$, por lo tanto agregando $v$ y $w$ al grupo $G$ y quitando $v'$ del mismo, obtenemos un grupo con más alumnos que $G$ en el cuál todos son amigos con todos, lo cuál es una contradicción ya que tomamos a $G$ con la máxima cantidad de alumnos posible. Entonces este caso tampoco puede ocurrir.


Habiendo visto todos los casos, concluímos que no puede ocurrir que $v$ y $w$ sean amigos y por lo tanto no lo son.
Hemos probado que dados dos alumnos cualesquiera fuera del grupo $G$, éstos no son amigos y de esto se sigue que poner a todos los alumnos de $G$ en el aula $A$ y a los demás en el aula $B$ cumple las condiciones del enunciado, como queríamos ver. ■
5  
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: OFO 2020 Problema 9

Mensaje sin leer por Sandy »

Spoiler: mostrar

Procederemos por inducción sobre la cantidad de participantes. Sabemos que con $2$ participantes es posible distribuirlos (van uno a cada aula y listo), veremos que si con $k$ se puede, con $k+1$ también.
Supongamos que tenemos a todos los $k$ participantes divididos como se debe, pero se habían olvidado de Juli Fabbri porque no lo vieron por ser muy petiso. Mostraremos que existe una manera de dividir a los $k+1$ participantes (los $k$ de estatura normal y Juli).
NOTA: En algunos casos, areviaré "Juli" como "J".
Dividiremos en $4$ grupos a los $k$ participantes:
$w_1, w_2, ...$ pertenecientes al aula $A$ y amigos de Juli. La cantidad de éstos será $W$.
$x_1, x_2, ...$ pertenecientes al aula $A$ y no amigos de Juli. La cantidad de éstos será $X$.
$y_1, y_2, ...$ pertenecientes al aula $B$ y amigos de Juli. La cantidad de éstos será $Y$.
$z_1, z_2, ...$ pertenecientes al aula $B$ y no amigos de Juli. La cantidad de éstos será $Z$.

NOTA 1: En algunos casos, areviaré "Juli" como "J".
NOTA 2: Con "$w_i$", "$x_i$", "$y_i$", "$z_i$" denoto un miembro de un grupo que podría ser cualquiera (es decir, $z_i$ puede ser $z_1$, $z_2$, etc.)

Dividiremos todo en $14 $ posibles (sub)casos:

1) $X=0$ o $Y=0$
2) $Y\geq 1$ y $X\geq 1$
.... 2.1) $X=1$
........ 2.1.1) $W=0$
............ 2.1.1.1) $Z\geq 1$
................ 2.1.1.1.1) $Y=1$
................ 2.1.1.1.2) $Y\geq 2$
............ 2.1.1.2) $Z=0$
................ 2.1.1.2.1) $Y=1$
................ 2.1.1.2.2) $Y\geq 2$
........ 2.1.2) $W\geq 1$
............ 2.1.2.1) $Z=0$
................ 2.1.2.1.1) $Y=1$
................ 2.1.2.1.2) $Y\geq 2$
............ 2.1.2.2) $Z\geq 1$
................ 2.1.2.2.1) $Y=1$
................ 2.1.2.2.2) $Y\geq 2$
.... 2.2) $X\geq 2$
........ 2.2.1) $Y\geq 2$
........ 2.2.2) $Y=1$
............ 2.2.2.1) $W=0$
................ 2.2.2.1.1) $Z=0$
................ 2.2.2.1.2) $Z\geq 1$
............ 2.2.2.2) $W\geq 1$
................ 2.2.2.2.1) $Z=0$
................ 2.2.2.2.2) $Z\geq 1$

Diremos que un subgrupo de $3$ personas es bueno si son todos amigos, malo si nadie es amigo de nadie, y neutro si no es ni bueno ni malo.
1) $X=0$ o $Y=0$
Spoiler: mostrar
Si $X=0$, Juli puede ir al aula A, ya que es amigo de todos los de ahí.
Si $Y=0$, Juli puede ir al aula B, ya que no es amigo de nadie de ahí.
2.1.1.1.1) $X=1$, $W=0$, $Z\geq 1$, $Y=1$
Spoiler: mostrar
Veamos el grupo de Juli, $x_1$, $y_1$, $z_i$.
Sabemos que $y_1$ es amigo de Juli, pero no de $z_i$, y que Juli no es amigo ni de $x_1$ ni de $z_i$.
Evaluemos los posibles subgrupos de $3$:
En $Jx_1y_1$, Juli es amigo de $y_1$ pero no de $x_1$, luego no puede ser bueno ni malo.
En $Jz_iy_1$, Juli es amigo de $y_1$, pero $y_1$ no es amigo de ninguno de los dos, luego no puede ser ni bueno ni malo.
En $x_1y_1z_i$, sólo sabemos que $z_i$ no es amigo de $y_1$. Entonces puede ser malo, si $x_1$ no es amigo ni de $y_1$ ni de $z_i$.
En $Jx_1z_i$, sabemos que Juli no es amigo de $x_1$ ni de $z_i$, por lo tanto puede ser malo si $x_1$ no es amigo de $z_i$.
Por lo tanto, sea cualquiera de los dos posibles el subgrupo bueno o malo, en ambos casos $x_1$ y $z_i$ deben no ser amigos. Es decir, $x_1$ no es amigo de ningún miembro de $z$ (porque podríamos haber tomado a cualquier $z_i$).
Por lo tanto, una manera de separar las aulas sería:
En el aula A, $y_1$.
En el aula B, $x_1$ y todos los $z$.
Y Juli puede ir a cualquiera de las dos aulas, ya que es amigo de $y_1$ pero no de $x_1$ ni de ningún $z$.
2.1.1.1.2) $X=1$, $W=0$, $Z\geq 1$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo conformado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_i$ e $y_j$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí.
Evaluemos los $4$ posibles subgrupos de $3$:
En cualquier subgrupo va a haber alguno de los siguientes pares: $\{y_i, y_j\}, \{x_1, J\}$. Luego ningún subgrupo será bueno, por lo que debe haber uno malo. Pero si está Juli en un subgrupo de $3$, deben estar o $y_i$ o $y_j$, que son sus amigos, luego no podrá ser tampoco malo. Por lo tanto el único subgrupo potencialmente bueno o malo es $y_iy_jx_1$, que deberá ser malo, luego $x_1$ no es amigo de ningún $y_i$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_i$ y $z_i$. Sabemos que $x_1$ no es amigo ni de Juli ni de $y_i$, que Juli es amigo de $y_i$, y que $z_i$ no es amigo ni de Juli ni de $y_i$. Pero notemos que, al igual que antes, cualquier subgrupo de $3$ debe incluir al menos un par dentro de $\{y_i, z_i\}, \{x_1, J\}$, por lo que ningún subgrupo podrá ser bueno, luego debe haber uno malo. Este subgrupo malo no puede contener, al mismo tiempo, a Juli y a $y_i$, porque son amigos, luego el subgrupo malo debe contener a $x_1$ y a $z_i$, lo cual implica que $x_1$ no es amigo de ningún $z$.
Luego en el aula A puede ir Juli y en el aula B $x_1$, todos los $y$ y todos los $z$.
2.1.1.2.1) $X=1$, $W=0$, $Z=0$, $Y=1$
Spoiler: mostrar
Podemos poner a $y_1$ y a Juli en el aula A, y a $x_1$ en el aula B.
2.1.1.2.2) $X=1$, $W=0$, $Z=0$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo conformado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_i$ e $y_j$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. Analizando los $4$ subgrupos de $3$ posibles, el único donde pueden ser todos amigos o nadie amigo, es el de $y_iy_jx_1$, lo cual implica que $x_1$ no es amigo ni de $y_i$ ni de $y_j$ (es decir, $x_1$ no es amigo de ningún $y$).
Por lo tanto, podemos ubicar a $x_1$ en el aula B junto a todos los $y$, y a Juli en el aula A solo.
2.1.2.1.1) $X=1$, $W\geq 1$, $Z=0$, $Y=1$
Spoiler: mostrar
Veamos un grupo conformado por Juli, $x_1$, $y_1$ y $w_i$. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_1$, y que $x_1$ es amigo de $w_1$. Cualquier subgrupo de $3$ incluye a algún par entre $\{y_i, J\}, \{x_1, w_i\}$, luego no habrá un subgrupo malo, por lo que debe haber uno bueno, por lo tanto no pueden estar al mismo tiempo $x_1$ y Juli, luego deberán estar al mismo tiempo $y_1$ y $w_i$, que por consiguiente deberán ser amigos.
Entonces en el aula A ponemos a $y_1$ y a todos los $w$, mientras que en el aula B podemos poner a $x_1$. Juli puede ir a cualquiera de las dos aulas.
2.1.2.1.2) $X=1$, $W\geq 1$, $Z=0$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. De nuevo, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$, por lo que podemos poner en el aula A a Juli con todos los $w$, y en el aula B a $x_1$ junto a todos los $y$.
2.1.2.2.1) $X=1$, $W\geq 1$, $Z\geq 1$, $Y=1$
Spoiler: mostrar

Veamos un grupo conformado por $w_i$, $x_1$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ y de $w_i$, pero no de $x_1$, y que $w_i$ es amigo de $x_1$. En cualquier subgrupo habrá un par entre $\{J, y_1\}, \{x_1, w_i\}$, luego no habrá ningún subgrupo malo. Luego, un subgrupo bueno no puede contener al mismo tiempo a $x_1$ y a Juli, por lo que el subgrupo bueno deberá contener a $y_1$ y a $w_i$. Por lo tanto, $y_1$ es amigo de todos los $w$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_1$ y $z_i$. Sabemos que Juli es amigo de $y_1$ pero no de $x_1$ ni de $z_i$, y que $z_i$ no es amigo de $y_1$. En cualquier subgrupo habrá un par entre $\{J, x_1\}, \{y_1, z_i\}$, luego no habrá ningún subgrupo bueno. Luego, un subgrupo malo no puede contener al mismo tiempo a $y_1$ y a Juli, por lo que el subgrupo bueno deberá contener a $x_1$ y a $z_i$, por lo que $x_1$ será amigo de todos los $z$.
Por lo tanto en el aula A pueden ir $y_1$ y todos los $w$, y en el aula B pueden ir $x_1$ y todos los $z$. Juli podrá ir a cualquier aula porque es amigo de todos los del aula A, y no es amigo de ninguno de los del aula B.
2.1.2.2.2) $X=1$, $W\geq 1$, $Z\geq 1$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. De nuevo, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_i$ y $z_i$. Sabemos que $x_1$ no es amigo ni de Juli ni de $y_i$, que Juli es amigo de $y_i$, y que $z_i$ no es amigo ni de Juli ni de $y_i$. Pero notemos que cualquier subgrupo de $3$ debe incluir al menos un par dentro de $\{y_i, z_i\}, \{x_1, J\}$, por lo que ningún subgrupo podrá ser bueno, luego debe haber uno malo. Este subgrupo malo no puede contener, al mismo tiempo, a Juli y a $y_i$, porque son amigos, luego el subgrupo malo debe contener a $x_1$ y a $z_i$, lo cual implica que $x_1$ no es amigo de ningún $z_i$.
Por lo tanto, podemos poner en el aula A a Juli con todos los $w$, y en el aula B a $x_1$, todos los $y$ y todos los $z$.
2.2.1) $X\geq 2$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_i$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$.
Veamos ahora un grupo formado por $x_i$, $x_j$, $y_i$ y Juli. Sabemos que Juli es amigo de $y_i$ pero no de $x_i$ ni de $x_j$ que $y_i$ no es amigo ni de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Por un lado, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, x_j\}, \{x_i, J\}$, por lo que no podrá haber un subgrupo bueno. Pero por otro lado, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero que en ese grupo de $4$ no haya ningún subgrupo bueno ni ningún grupo malo es una contradicción con el enunciado, por lo que no es posible que, al mismo tiempo, $X\geq 2$ y $Y\geq 2$.
2.2.2.1.1) $X\geq 2$, $Y=1$, $W=0$, $Z=0$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$, por lo que en el aula A pueden ir $y_1$ y todos los $x$, quedando Juli en el aula B.
2.2.2.1.2) $X\geq 2$, $Y=1$, $W=0$, $Z\geq 1$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$. Entonces en el aula A pueden ir $y_1$ y todos los $x$, y en el aula B pueden ir Juli y todos los $z$.
2.2.2.2.1) $X\geq 2$, $Y=1$, $W\geq 1$, $Z=0$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$.
Veamos ahora un grupo formado por $x_i$, $y_1$, $w_i$ y Juli. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_i$, y que $x_i$ es amigo de $y_1$ y de $w_i$. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, w_i\}$, por lo que no habrá ningún subgrupo malo. Por esto, un subgrupo no neutro no puede incluir al mismo tiempo a $x_i$ y a Juli, por lo tanto deberá incluir a $w_i$ y a $y_1$, por lo que $y_1$ será amigo de todos los $w$.
Luego, podemos poner en el aula A a $y_1$, todos los $x$ y todos los $w$, y en el aula B a Juli.
2.2.2.2.2) $X\geq 2$, $Y=1$, $W\geq 1$, $Z\geq 1$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$.
Veamos ahora un grupo formado por $x_i$, $y_1$, $w_i$ y Juli. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_i$, y que $x_i$ es amigo de $y_1$ y de $w_i$. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, w_i\}$, por lo que no habrá ningún subgrupo malo. Por esto, un subgrupo no neutro no puede incluir al mismo tiempo a $x_i$ y a Juli, por lo tanto deberá incluir a $w_i$ y a $y_1$, por lo que $y_1$ será amigo de todos los $w$.
Luego, podemos poner en el aula A a $y_1$, todos los $x$ y todos los $w$, y en el aula B a todos los $z$ y a Juli.
Última edición por Sandy el Lun 01 Feb, 2021 11:37 pm, editado 1 vez en total.
1  
Fallo inapelable.
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 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: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: OFO 2020 Problema 9

Mensaje sin leer por Joacoini »

Spoiler: mostrar
Vamos a ver a las personas como vértices y si dos son amigos entonces están unidos por una arista azul, en caso contrario están unidos por una arista roja.

Sea $\alpha$ el conjunto de vértices que están todos unidos por aristas azules y $\beta$ en el que están todos unidos por aristas rojas.

Voy a proceder por inducción en la cantidad de personas.

Si son $4$ entonces tenemos que entre esas $4$ hay $3$ que son todos amigos entre sí y mandamos a estas a $\alpha$ y al restante a $\beta$ o hay tres que no son amigos entre sí por lo que mandamos esos tres a $\beta$ al restante a $\alpha$.

Supongamos que para $n-1$ participantes se puede, veamos que para $n$ también.

Separamos a un vértice $P$ de los demás y al resto lo separamos en $\alpha$ y $\beta$ (podemos por la inducción), si uno de estos esta vació entonces mandamos ahí a $P$ así que supongamos que no están vacíos.

Supongamos que hay un conjunto ($\alpha$ o $\beta$) tal que para todo $V$ perteneciente a ese conjunto $VP$ es del mismo color que el que representa el conjunto entonces metemos a $P$ en es conjunto y listo.
Por lo que en $\alpha$ hay al menos un vértice $V$ tal que $VP$ es rojo y en $\beta$ hay al menos un vértice $V$ tal que $VP$ es azul. (!)

Lema
Sean $A, B, C, D$ y $E$ $5$ vértices no puede suceder que $AB$ es rojo, $CD$ es azul, $AE$ y $BE$ son azules y $CE$ y $DE$ son rojos.

Demostración:
Si sucediese entonces para que $BCDE$ cumpla la propiedad del enunciado $CB$ y $DB$ tienen que ser azules pero entonces $ABCE$ no cumple la propiedad del enunciado.

Ahora por el lema tenemos que en uno de los dos conjuntos $\alpha$ y $\beta$ hay como mucho un vértice $A$ tal que $AP$ es del color contrario al que representa su conjunto (si no habría dos de estos en cada conjunto y tendríamos la situación del lema) y por (!) hay exactamente uno.

WLOG es $\alpha$ y sea $A$ este vértice en $\alpha$ tal que $AP$ es rojo tenemos que para todo vértice $V$ de $\alpha$ distinto de $A$, $VP$ es azul.

Sea $B$ un vértice en $\beta$ tal que $BP$ sea azul, por (!) hay al menos uno.

Si $V$ es un vértice de $\alpha$ distinto de $A$, como $VP$, $VA$ y $PB$ son azules y $AP$ es rojo, para que $ABPV$ cumpla la propiedad $VAB$ o $PBV$ tiene que ser azul, de cualquier forma $VB$ es azul para todo vértice de $\alpha$ distinto de $A$.

Sea $X$ un vértice de $\beta$ distinto de $B$, como $XB$ y $AP$ son rojos y $PB$ es azul para que $APBX$ cumpla la propiedad del enunciado $XAB$ o $XAP$ tiene que ser rojo, de cualquier forma $XA$ es rojo para todo vértice de $\alpha$ distinto de $B$.

Como todo vértice $V$ de $\alpha$ distinto de $A$ (puede que no haya ninguno) cumple que $VP$ y $VB$ son azules ademas de que $PB$ es azul entonces podemos sacar a $A$ de $\alpha$ y meter a $P$ y a $B$ sin alterar que todos dos vértices en $\alpha$ están conectados por una arista azul.

Como todo vértice $X$ de $\beta$ distinto de $B$ cumple que $XA$ es rojo entonces al sacar a $B$ de $\beta$ y meter a $A$ se sigue cumpliendo que todos dos vértices en $\beta$ están conectados por una arista roja.

Y listo, ya están los $n$ puntos separados en dos conjuntos $\alpha$ y $\beta$.
NO HAY ANÁLISIS.
Avatar de Usuario
lichafilloy

Colaborador-Varias OFO - Mención-OFO 2015 OFO - Jurado-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Plata-OFO 2019
OFO - Medalla de Oro-OFO 2020 OFO - Medalla de Bronce-OFO 2021
Mensajes: 116
Registrado: Dom 02 Sep, 2012 12:51 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Quilmes

Re: OFO 2020 Problema 9

Mensaje sin leer por lichafilloy »

No me gusta escribir y me gusta que el lector piense: (?)
Spoiler: mostrar
Tomar el clique minimo anda
1  
Master de Rumania y paz mundial
Avatar de Usuario
lichafilloy

Colaborador-Varias OFO - Mención-OFO 2015 OFO - Jurado-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Plata-OFO 2019
OFO - Medalla de Oro-OFO 2020 OFO - Medalla de Bronce-OFO 2021
Mensajes: 116
Registrado: Dom 02 Sep, 2012 12:51 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Quilmes

Re: OFO 2020 Problema 9

Mensaje sin leer por lichafilloy »

Sandy escribió: Sab 01 Feb, 2020 1:04 am
AgusBarreto escribió: Mar 21 Ene, 2020 11:59 pm En una olimpíada de matemática muchos participantes hicieron nuevos amigos. Al finalizar la olimpíada se observó que en cualquier grupo de 4 participantes, o bien hay 3 participantes que son todos amigos entre sí o bien hay 3 participantes tales que ningún par de ellos son amigos.
Demostrar que es posible distribuir a los participantes de esta olimpíada en dos aulas $A$ y $B$ de manera tal que en el aula $A$ todos los participantes son amigos entre sí, y en el aula $B$ no hay dos participantes que sean amigos.

Aclaraciones: La amistad es recíproca, es decir, si $X$ es amigo de $Y$, entonces $Y$ es amigo de $X$.
Está permitido que una de las dos aulas quede vacía.
Spoiler: mostrar

Procederemos por inducción sobre la cantidad de participantes. Sabemos que con $2$ participantes es posible distribuirlos (van uno a cada aula y listo), veremos que si con $k$ se puede, con $k+1$ también.
Supongamos que tenemos a todos los $k$ participantes divididos como se debe, pero se habían olvidado de Juli Fabbri porque no lo vieron por ser muy petiso. Mostraremos que existe una manera de dividir a los $k+1$ participantes (los $k$ de estatura normal y Juli).
NOTA: En algunos casos, areviaré "Juli" como "J".
Dividiremos en $4$ grupos a los $k$ participantes:
$w_1, w_2, ...$ pertenecientes al aula $A$ y amigos de Juli. La cantidad de éstos será $W$.
$x_1, x_2, ...$ pertenecientes al aula $A$ y no amigos de Juli. La cantidad de éstos será $X$.
$y_1, y_2, ...$ pertenecientes al aula $B$ y amigos de Juli. La cantidad de éstos será $Y$.
$z_1, z_2, ...$ pertenecientes al aula $B$ y no amigos de Juli. La cantidad de éstos será $Z$.

NOTA 1: En algunos casos, areviaré "Juli" como "J".
NOTA 2: Con "$w_i$", "$x_i$", "$y_i$", "$z_i$" denoto un miembro de un grupo que podría ser cualquiera (es decir, $z_i$ puede ser $z_1$, $z_2$, etc.)

Dividiremos todo en $14 $ posibles (sub)casos:

1) $X=0$ o $Y=0$
2) $Y\geq 1$ y $X\geq 1$
.... 2.1) $X=1$
........ 2.1.1) $W=0$
............ 2.1.1.1) $Z\geq 1$
................ 2.1.1.1.1) $Y=1$
................ 2.1.1.1.2) $Y\geq 2$
............ 2.1.1.2) $Z=0$
................ 2.1.1.2.1) $Y=1$
................ 2.1.1.2.2) $Y\geq 2$
........ 2.1.2) $W\geq 1$
............ 2.1.2.1) $Z=0$
................ 2.1.2.1.1) $Y=1$
................ 2.1.2.1.2) $Y\geq 2$
............ 2.1.2.2) $Z\geq 1$
................ 2.1.2.2.1) $Y=1$
................ 2.1.2.2.2) $Y\geq 2$
.... 2.2) $X\geq 2$
........ 2.2.1) $Y\geq 2$
........ 2.2.2) $Y=1$
............ 2.2.2.1) $W=0$
................ 2.2.2.1.1) $Z=0$
................ 2.2.2.1.2) $Z\geq 1$
............ 2.2.2.2) $W\geq 1$
................ 2.2.2.2.1) $Z=0$
................ 2.2.2.2.2) $Z\geq 1$

Diremos que un subgrupo de $3$ personas es bueno si son todos amigos, malo si nadie es amigo de nadie, y neutro si no es ni bueno ni malo.
1) $X=0$ o $Y=0$
Spoiler: mostrar
Si $X=0$, Juli puede ir al aula A, ya que es amigo de todos los de ahí.
Si $Y=0$, Juli puede ir al aula B, ya que no es amigo de nadie de ahí.
2.1.1.1.1) $X=1$, $W=0$, $Z\geq 1$, $Y=1$
Spoiler: mostrar
Veamos el grupo de Juli, $x_1$, $y_1$, $z_i$.
Sabemos que $y_1$ es amigo de Juli, pero no de $z_i$, y que Juli no es amigo ni de $x_1$ ni de $z_i$.
Evaluemos los posibles subgrupos de $3$:
En $Jx_1y_1$, Juli es amigo de $y_1$ pero no de $x_1$, luego no puede ser bueno ni malo.
En $Jz_iy_1$, Juli es amigo de $y_1$, pero $y_1$ no es amigo de ninguno de los dos, luego no puede ser ni bueno ni malo.
En $x_1y_1z_i$, sólo sabemos que $z_i$ no es amigo de $y_1$. Entonces puede ser malo, si $x_1$ no es amigo ni de $y_1$ ni de $z_i$.
En $Jx_1z_i$, sabemos que Juli no es amigo de $x_1$ ni de $z_i$, por lo tanto puede ser malo si $x_1$ no es amigo de $z_i$.
Por lo tanto, sea cualquiera de los dos posibles el subgrupo bueno o malo, en ambos casos $x_1$ y $z_i$ deben no ser amigos. Es decir, $x_1$ no es amigo de ningún miembro de $z$ (porque podríamos haber tomado a cualquier $z_i$).
Por lo tanto, una manera de separar las aulas sería:
En el aula A, $y_1$.
En el aula B, $x_1$ y todos los $z$.
Y Juli puede ir a cualquiera de las dos aulas, ya que es amigo de $y_1$ pero no de $x_1$ ni de ningún $z$.
2.1.1.1.2) $X=1$, $W=0$, $Z\geq 1$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo conformado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_i$ e $y_j$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí.
Evaluemos los $4$ posibles subgrupos de $3$:
En cualquier subgrupo va a haber alguno de los siguientes pares: $\{y_i, y_j\}, \{x_1, J\}$. Luego ningún subgrupo será bueno, por lo que debe haber uno malo. Pero si está Juli en un subgrupo de $3$, deben estar o $y_i$ o $y_j$, que son sus amigos, luego no podrá ser tampoco malo. Por lo tanto el único subgrupo potencialmente bueno o malo es $y_iy_jx_1$, que deberá ser malo, luego $x_1$ no es amigo de ningún $y_i$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_i$ y $z_i$. Sabemos que $x_1$ no es amigo ni de Juli ni de $y_i$, que Juli es amigo de $y_i$, y que $z_i$ no es amigo ni de Juli ni de $y_i$. Pero notemos que, al igual que antes, cualquier subgrupo de $3$ debe incluir al menos un par dentro de $\{y_i, z_i\}, \{x_1, J\}$, por lo que ningún subgrupo podrá ser bueno, luego debe haber uno malo. Este subgrupo malo no puede contener, al mismo tiempo, a Juli y a $y_i$, porque son amigos, luego el subgrupo malo debe contener a $x_1$ y a $z_i$, lo cual implica que $x_1$ no es amigo de ningún $z$.
Luego en el aula A puede ir Juli y en el aula B $x_1$, todos los $y$ y todos los $z$.
2.1.1.2.1) $X=1$, $W=0$, $Z=0$, $Y=1$
Spoiler: mostrar
Podemos poner a $y_1$ y a Juli en el aula A, y a $x_1$ en el aula B.
2.1.1.2.2) $X=1$, $W=0$, $Z=0$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo conformado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_i$ e $y_j$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. Analizando los $4$ subgrupos de $3$ posibles, el único donde pueden ser todos amigos o nadie amigo, es el de $y_iy_jx_1$, lo cual implica que $x_1$ no es amigo ni de $y_i$ ni de $y_j$ (es decir, $x_1$ no es amigo de ningún $y$).
Por lo tanto, podemos ubicar a $x_1$ en el aula B junto a todos los $y$, y a Juli en el aula A solo.
2.1.2.1.1) $X=1$, $W\geq 1$, $Z=0$, $Y=1$
Spoiler: mostrar
Veamos un grupo conformado por Juli, $x_1$, $y_1$ y $w_i$. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_1$, y que $x_1$ es amigo de $w_1$. Cualquier subgrupo de $3$ incluye a algún par entre $\{y_i, J\}, \{x_1, w_i\}$, luego no habrá un subgrupo malo, por lo que debe haber uno bueno, por lo tanto no pueden estar al mismo tiempo $x_1$ y Juli, luego deberán estar al mismo tiempo $y_1$ y $w_i$, que por consiguiente deberán ser amigos.
Entonces en el aula A ponemos a $y_1$ y a todos los $w$, mientras que en el aula B podemos poner a $x_1$. Juli puede ir a cualquiera de las dos aulas.
2.1.2.1.2) $X=1$, $W\geq 1$, $Z=0$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. De nuevo, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$, por lo que podemos poner en el aula A a Juli con todos los $w$, y en el aula B a $x_1$ junto a todos los $y$.
2.1.2.2.1) $X=1$, $W\geq 1$, $Z\geq 1$, $Y=1$
Spoiler: mostrar

Veamos un grupo conformado por $w_i$, $x_1$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ y de $w_i$, pero no de $x_1$, y que $w_i$ es amigo de $x_1$. En cualquier subgrupo habrá un par entre $\{J, y_1\}, \{x_1, w_i\}$, luego no habrá ningún subgrupo malo. Luego, un subgrupo bueno no puede contener al mismo tiempo a $x_1$ y a Juli, por lo que el subgrupo bueno deberá contener a $y_1$ y a $w_i$. Por lo tanto, $y_1$ es amigo de todos los $w$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_1$ y $z_i$. Sabemos que Juli es amigo de $y_1$ pero no de $x_1$ ni de $z_i$, y que $z_i$ no es amigo de $y_1$. En cualquier subgrupo habrá un par entre $\{J, x_1\}, \{y_1, z_i\}$, luego no habrá ningún subgrupo bueno. Luego, un subgrupo malo no puede contener al mismo tiempo a $y_1$ y a Juli, por lo que el subgrupo bueno deberá contener a $x_1$ y a $z_i$, por lo que $x_1$ será amigo de todos los $z$.
Por lo tanto en el aula A pueden ir $y_1$ y todos los $w$, y en el aula B pueden ir $x_1$ y todos los $z$. Juli podrá ir a cualquier aula porque es amigo de todos los del aula A, y no es amigo de ninguno de los del aula B.
2.1.2.2.2) $X=1$, $W\geq 1$, $Z\geq 1$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. De nuevo, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_i$ y $z_i$. Sabemos que $x_1$ no es amigo ni de Juli ni de $y_i$, que Juli es amigo de $y_i$, y que $z_i$ no es amigo ni de Juli ni de $y_i$. Pero notemos que cualquier subgrupo de $3$ debe incluir al menos un par dentro de $\{y_i, z_i\}, \{x_1, J\}$, por lo que ningún subgrupo podrá ser bueno, luego debe haber uno malo. Este subgrupo malo no puede contener, al mismo tiempo, a Juli y a $y_i$, porque son amigos, luego el subgrupo malo debe contener a $x_1$ y a $z_i$, lo cual implica que $x_1$ no es amigo de ningún $z_i$.
Por lo tanto, podemos poner en el aula A a Juli con todos los $w$, y en el aula B a $x_1$, todos los $y$ y todos los $z$.
2.2.1) $X\geq 2$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_i$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$.
Veamos ahora un grupo formado por $x_i$, $x_j$, $y_i$ y Juli. Sabemos que Juli es amigo de $y_i$ pero no de $x_i$ ni de $x_j$ que $y_i$ no es amigo ni de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Por un lado, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, x_j\}, \{x_i, J\}$, por lo que no podrá haber un subgrupo bueno. Pero por otro lado, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero que en ese grupo de $4$ no haya ningún subgrupo bueno ni ningún grupo malo es una contradicción con el enunciado, por lo que no es posible que, al mismo tiempo, $X\geq 2$ y $Y\geq 2$.
2.2.2.1.1) $X\geq 2$, $Y=1$, $W=0$, $Z=0$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$, por lo que en el aula A pueden ir $y_1$ y todos los $x$, quedando Juli en el aula B.
2.2.2.1.2) $X\geq 2$, $Y=1$, $W=0$, $Z\geq 1$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$. Entonces en el aula A pueden ir $y_1$ y todos los $x$, y en el aula B pueden ir Juli y todos los $z$.
2.2.2.2.1) $X\geq 2$, $Y=1$, $W\geq 1$, $Z=0$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$.
Veamos ahora un grupo formado por $x_i$, $y_1$, $w_i$ y Juli. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_i$, y que $x_i$ es amigo de $y_1$ y de $w_i$. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, w_i\}$, por lo que no habrá ningún subgrupo malo. Por esto, un subgrupo no neutro no puede incluir al mismo tiempo a $x_i$ y a Juli, por lo tanto deberá incluir a $w_i$ y a $y_1$, por lo que $y_1$ será amigo de todos los $w$.
Luego, podemos poner en el aula A a $y_1$, todos los $x$ y todos los $w$, y en el aula B a Juli.
2.2.2.2.2) $X\geq 2$, $Y=1$, $W\geq 1$, $Z\geq 1$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$.
Veamos ahora un grupo formado por $x_i$, $y_1$, $w_i$ y Juli. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_i$, y que $x_i$ es amigo de $y_1$ y de $w_i$. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, w_i\}$, por lo que no habrá ningún subgrupo malo. Por esto, un subgrupo no neutro no puede incluir al mismo tiempo a $x_i$ y a Juli, por lo tanto deberá incluir a $w_i$ y a $y_1$, por lo que $y_1$ será amigo de todos los $w$.
Luego, podemos poner en el aula A a $y_1$, todos los $x$ y todos los $w$, y en el aula B a todos los $z$ y a Juli.
El corrector ha abandonado la sala
11  
Master de Rumania y paz mundial
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 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
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: OFO 2020 Problema 9

Mensaje sin leer por Turko Arias »

lichafilloy escribió: Sab 01 Feb, 2020 1:14 pm
Sandy escribió: Sab 01 Feb, 2020 1:04 am
AgusBarreto escribió: Mar 21 Ene, 2020 11:59 pm En una olimpíada de matemática muchos participantes hicieron nuevos amigos. Al finalizar la olimpíada se observó que en cualquier grupo de 4 participantes, o bien hay 3 participantes que son todos amigos entre sí o bien hay 3 participantes tales que ningún par de ellos son amigos.
Demostrar que es posible distribuir a los participantes de esta olimpíada en dos aulas $A$ y $B$ de manera tal que en el aula $A$ todos los participantes son amigos entre sí, y en el aula $B$ no hay dos participantes que sean amigos.

Aclaraciones: La amistad es recíproca, es decir, si $X$ es amigo de $Y$, entonces $Y$ es amigo de $X$.
Está permitido que una de las dos aulas quede vacía.
Spoiler: mostrar

Procederemos por inducción sobre la cantidad de participantes. Sabemos que con $2$ participantes es posible distribuirlos (van uno a cada aula y listo), veremos que si con $k$ se puede, con $k+1$ también.
Supongamos que tenemos a todos los $k$ participantes divididos como se debe, pero se habían olvidado de Juli Fabbri porque no lo vieron por ser muy petiso. Mostraremos que existe una manera de dividir a los $k+1$ participantes (los $k$ de estatura normal y Juli).
NOTA: En algunos casos, areviaré "Juli" como "J".
Dividiremos en $4$ grupos a los $k$ participantes:
$w_1, w_2, ...$ pertenecientes al aula $A$ y amigos de Juli. La cantidad de éstos será $W$.
$x_1, x_2, ...$ pertenecientes al aula $A$ y no amigos de Juli. La cantidad de éstos será $X$.
$y_1, y_2, ...$ pertenecientes al aula $B$ y amigos de Juli. La cantidad de éstos será $Y$.
$z_1, z_2, ...$ pertenecientes al aula $B$ y no amigos de Juli. La cantidad de éstos será $Z$.

NOTA 1: En algunos casos, areviaré "Juli" como "J".
NOTA 2: Con "$w_i$", "$x_i$", "$y_i$", "$z_i$" denoto un miembro de un grupo que podría ser cualquiera (es decir, $z_i$ puede ser $z_1$, $z_2$, etc.)

Dividiremos todo en $14 $ posibles (sub)casos:

1) $X=0$ o $Y=0$
2) $Y\geq 1$ y $X\geq 1$
.... 2.1) $X=1$
........ 2.1.1) $W=0$
............ 2.1.1.1) $Z\geq 1$
................ 2.1.1.1.1) $Y=1$
................ 2.1.1.1.2) $Y\geq 2$
............ 2.1.1.2) $Z=0$
................ 2.1.1.2.1) $Y=1$
................ 2.1.1.2.2) $Y\geq 2$
........ 2.1.2) $W\geq 1$
............ 2.1.2.1) $Z=0$
................ 2.1.2.1.1) $Y=1$
................ 2.1.2.1.2) $Y\geq 2$
............ 2.1.2.2) $Z\geq 1$
................ 2.1.2.2.1) $Y=1$
................ 2.1.2.2.2) $Y\geq 2$
.... 2.2) $X\geq 2$
........ 2.2.1) $Y\geq 2$
........ 2.2.2) $Y=1$
............ 2.2.2.1) $W=0$
................ 2.2.2.1.1) $Z=0$
................ 2.2.2.1.2) $Z\geq 1$
............ 2.2.2.2) $W\geq 1$
................ 2.2.2.2.1) $Z=0$
................ 2.2.2.2.2) $Z\geq 1$

Diremos que un subgrupo de $3$ personas es bueno si son todos amigos, malo si nadie es amigo de nadie, y neutro si no es ni bueno ni malo.
1) $X=0$ o $Y=0$
Spoiler: mostrar
Si $X=0$, Juli puede ir al aula A, ya que es amigo de todos los de ahí.
Si $Y=0$, Juli puede ir al aula B, ya que no es amigo de nadie de ahí.
2.1.1.1.1) $X=1$, $W=0$, $Z\geq 1$, $Y=1$
Spoiler: mostrar
Veamos el grupo de Juli, $x_1$, $y_1$, $z_i$.
Sabemos que $y_1$ es amigo de Juli, pero no de $z_i$, y que Juli no es amigo ni de $x_1$ ni de $z_i$.
Evaluemos los posibles subgrupos de $3$:
En $Jx_1y_1$, Juli es amigo de $y_1$ pero no de $x_1$, luego no puede ser bueno ni malo.
En $Jz_iy_1$, Juli es amigo de $y_1$, pero $y_1$ no es amigo de ninguno de los dos, luego no puede ser ni bueno ni malo.
En $x_1y_1z_i$, sólo sabemos que $z_i$ no es amigo de $y_1$. Entonces puede ser malo, si $x_1$ no es amigo ni de $y_1$ ni de $z_i$.
En $Jx_1z_i$, sabemos que Juli no es amigo de $x_1$ ni de $z_i$, por lo tanto puede ser malo si $x_1$ no es amigo de $z_i$.
Por lo tanto, sea cualquiera de los dos posibles el subgrupo bueno o malo, en ambos casos $x_1$ y $z_i$ deben no ser amigos. Es decir, $x_1$ no es amigo de ningún miembro de $z$ (porque podríamos haber tomado a cualquier $z_i$).
Por lo tanto, una manera de separar las aulas sería:
En el aula A, $y_1$.
En el aula B, $x_1$ y todos los $z$.
Y Juli puede ir a cualquiera de las dos aulas, ya que es amigo de $y_1$ pero no de $x_1$ ni de ningún $z$.
2.1.1.1.2) $X=1$, $W=0$, $Z\geq 1$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo conformado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_i$ e $y_j$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí.
Evaluemos los $4$ posibles subgrupos de $3$:
En cualquier subgrupo va a haber alguno de los siguientes pares: $\{y_i, y_j\}, \{x_1, J\}$. Luego ningún subgrupo será bueno, por lo que debe haber uno malo. Pero si está Juli en un subgrupo de $3$, deben estar o $y_i$ o $y_j$, que son sus amigos, luego no podrá ser tampoco malo. Por lo tanto el único subgrupo potencialmente bueno o malo es $y_iy_jx_1$, que deberá ser malo, luego $x_1$ no es amigo de ningún $y_i$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_i$ y $z_i$. Sabemos que $x_1$ no es amigo ni de Juli ni de $y_i$, que Juli es amigo de $y_i$, y que $z_i$ no es amigo ni de Juli ni de $y_i$. Pero notemos que, al igual que antes, cualquier subgrupo de $3$ debe incluir al menos un par dentro de $\{y_i, z_i\}, \{x_1, J\}$, por lo que ningún subgrupo podrá ser bueno, luego debe haber uno malo. Este subgrupo malo no puede contener, al mismo tiempo, a Juli y a $y_i$, porque son amigos, luego el subgrupo malo debe contener a $x_1$ y a $z_i$, lo cual implica que $x_1$ no es amigo de ningún $z$.
Luego en el aula A puede ir Juli y en el aula B $x_1$, todos los $y$ y todos los $z$.
2.1.1.2.1) $X=1$, $W=0$, $Z=0$, $Y=1$
Spoiler: mostrar
Podemos poner a $y_1$ y a Juli en el aula A, y a $x_1$ en el aula B.
2.1.1.2.2) $X=1$, $W=0$, $Z=0$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo conformado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_i$ e $y_j$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. Analizando los $4$ subgrupos de $3$ posibles, el único donde pueden ser todos amigos o nadie amigo, es el de $y_iy_jx_1$, lo cual implica que $x_1$ no es amigo ni de $y_i$ ni de $y_j$ (es decir, $x_1$ no es amigo de ningún $y$).
Por lo tanto, podemos ubicar a $x_1$ en el aula B junto a todos los $y$, y a Juli en el aula A solo.
2.1.2.1.1) $X=1$, $W\geq 1$, $Z=0$, $Y=1$
Spoiler: mostrar
Veamos un grupo conformado por Juli, $x_1$, $y_1$ y $w_i$. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_1$, y que $x_1$ es amigo de $w_1$. Cualquier subgrupo de $3$ incluye a algún par entre $\{y_i, J\}, \{x_1, w_i\}$, luego no habrá un subgrupo malo, por lo que debe haber uno bueno, por lo tanto no pueden estar al mismo tiempo $x_1$ y Juli, luego deberán estar al mismo tiempo $y_1$ y $w_i$, que por consiguiente deberán ser amigos.
Entonces en el aula A ponemos a $y_1$ y a todos los $w$, mientras que en el aula B podemos poner a $x_1$. Juli puede ir a cualquiera de las dos aulas.
2.1.2.1.2) $X=1$, $W\geq 1$, $Z=0$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. De nuevo, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$, por lo que podemos poner en el aula A a Juli con todos los $w$, y en el aula B a $x_1$ junto a todos los $y$.
2.1.2.2.1) $X=1$, $W\geq 1$, $Z\geq 1$, $Y=1$
Spoiler: mostrar

Veamos un grupo conformado por $w_i$, $x_1$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ y de $w_i$, pero no de $x_1$, y que $w_i$ es amigo de $x_1$. En cualquier subgrupo habrá un par entre $\{J, y_1\}, \{x_1, w_i\}$, luego no habrá ningún subgrupo malo. Luego, un subgrupo bueno no puede contener al mismo tiempo a $x_1$ y a Juli, por lo que el subgrupo bueno deberá contener a $y_1$ y a $w_i$. Por lo tanto, $y_1$ es amigo de todos los $w$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_1$ y $z_i$. Sabemos que Juli es amigo de $y_1$ pero no de $x_1$ ni de $z_i$, y que $z_i$ no es amigo de $y_1$. En cualquier subgrupo habrá un par entre $\{J, x_1\}, \{y_1, z_i\}$, luego no habrá ningún subgrupo bueno. Luego, un subgrupo malo no puede contener al mismo tiempo a $y_1$ y a Juli, por lo que el subgrupo bueno deberá contener a $x_1$ y a $z_i$, por lo que $x_1$ será amigo de todos los $z$.
Por lo tanto en el aula A pueden ir $y_1$ y todos los $w$, y en el aula B pueden ir $x_1$ y todos los $z$. Juli podrá ir a cualquier aula porque es amigo de todos los del aula A, y no es amigo de ninguno de los del aula B.
2.1.2.2.2) $X=1$, $W\geq 1$, $Z\geq 1$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. De nuevo, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_i$ y $z_i$. Sabemos que $x_1$ no es amigo ni de Juli ni de $y_i$, que Juli es amigo de $y_i$, y que $z_i$ no es amigo ni de Juli ni de $y_i$. Pero notemos que cualquier subgrupo de $3$ debe incluir al menos un par dentro de $\{y_i, z_i\}, \{x_1, J\}$, por lo que ningún subgrupo podrá ser bueno, luego debe haber uno malo. Este subgrupo malo no puede contener, al mismo tiempo, a Juli y a $y_i$, porque son amigos, luego el subgrupo malo debe contener a $x_1$ y a $z_i$, lo cual implica que $x_1$ no es amigo de ningún $z_i$.
Por lo tanto, podemos poner en el aula A a Juli con todos los $w$, y en el aula B a $x_1$, todos los $y$ y todos los $z$.
2.2.1) $X\geq 2$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_i$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$.
Veamos ahora un grupo formado por $x_i$, $x_j$, $y_i$ y Juli. Sabemos que Juli es amigo de $y_i$ pero no de $x_i$ ni de $x_j$ que $y_i$ no es amigo ni de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Por un lado, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, x_j\}, \{x_i, J\}$, por lo que no podrá haber un subgrupo bueno. Pero por otro lado, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero que en ese grupo de $4$ no haya ningún subgrupo bueno ni ningún grupo malo es una contradicción con el enunciado, por lo que no es posible que, al mismo tiempo, $X\geq 2$ y $Y\geq 2$.
2.2.2.1.1) $X\geq 2$, $Y=1$, $W=0$, $Z=0$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$, por lo que en el aula A pueden ir $y_1$ y todos los $x$, quedando Juli en el aula B.
2.2.2.1.2) $X\geq 2$, $Y=1$, $W=0$, $Z\geq 1$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$. Entonces en el aula A pueden ir $y_1$ y todos los $x$, y en el aula B pueden ir Juli y todos los $z$.
2.2.2.2.1) $X\geq 2$, $Y=1$, $W\geq 1$, $Z=0$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$.
Veamos ahora un grupo formado por $x_i$, $y_1$, $w_i$ y Juli. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_i$, y que $x_i$ es amigo de $y_1$ y de $w_i$. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, w_i\}$, por lo que no habrá ningún subgrupo malo. Por esto, un subgrupo no neutro no puede incluir al mismo tiempo a $x_i$ y a Juli, por lo tanto deberá incluir a $w_i$ y a $y_1$, por lo que $y_1$ será amigo de todos los $w$.
Luego, podemos poner en el aula A a $y_1$, todos los $x$ y todos los $w$, y en el aula B a Juli.
2.2.2.2.2) $X\geq 2$, $Y=1$, $W\geq 1$, $Z\geq 1$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$.
Veamos ahora un grupo formado por $x_i$, $y_1$, $w_i$ y Juli. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_i$, y que $x_i$ es amigo de $y_1$ y de $w_i$. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, w_i\}$, por lo que no habrá ningún subgrupo malo. Por esto, un subgrupo no neutro no puede incluir al mismo tiempo a $x_i$ y a Juli, por lo tanto deberá incluir a $w_i$ y a $y_1$, por lo que $y_1$ será amigo de todos los $w$.
Luego, podemos poner en el aula A a $y_1$, todos los $x$ y todos los $w$, y en el aula B a todos los $z$ y a Juli.
El corrector ha abandonado la sala
Este si que no va a lograr la paz mundial Lichin, no aprende más, pensamos que con el $1$ de la OFO pasada tenía suficiente :lol: :lol: :lol:
5  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
Gregorio

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2024
Mensajes: 123
Registrado: Dom 01 Ene, 2012 3:01 pm
Medallas: 3
Nivel: 3

Re: OFO 2020 Problema 9

Mensaje sin leer por Gregorio »

Sandy escribió: Sab 01 Feb, 2020 1:04 am
AgusBarreto escribió: Mar 21 Ene, 2020 11:59 pm En una olimpíada de matemática muchos participantes hicieron nuevos amigos. Al finalizar la olimpíada se observó que en cualquier grupo de 4 participantes, o bien hay 3 participantes que son todos amigos entre sí o bien hay 3 participantes tales que ningún par de ellos son amigos.
Demostrar que es posible distribuir a los participantes de esta olimpíada en dos aulas $A$ y $B$ de manera tal que en el aula $A$ todos los participantes son amigos entre sí, y en el aula $B$ no hay dos participantes que sean amigos.

Aclaraciones: La amistad es recíproca, es decir, si $X$ es amigo de $Y$, entonces $Y$ es amigo de $X$.
Está permitido que una de las dos aulas quede vacía.
Spoiler: mostrar

Procederemos por inducción sobre la cantidad de participantes. Sabemos que con $2$ participantes es posible distribuirlos (van uno a cada aula y listo), veremos que si con $k$ se puede, con $k+1$ también.
Supongamos que tenemos a todos los $k$ participantes divididos como se debe, pero se habían olvidado de Juli Fabbri porque no lo vieron por ser muy petiso. Mostraremos que existe una manera de dividir a los $k+1$ participantes (los $k$ de estatura normal y Juli).
NOTA: En algunos casos, areviaré "Juli" como "J".
Dividiremos en $4$ grupos a los $k$ participantes:
$w_1, w_2, ...$ pertenecientes al aula $A$ y amigos de Juli. La cantidad de éstos será $W$.
$x_1, x_2, ...$ pertenecientes al aula $A$ y no amigos de Juli. La cantidad de éstos será $X$.
$y_1, y_2, ...$ pertenecientes al aula $B$ y amigos de Juli. La cantidad de éstos será $Y$.
$z_1, z_2, ...$ pertenecientes al aula $B$ y no amigos de Juli. La cantidad de éstos será $Z$.

NOTA 1: En algunos casos, areviaré "Juli" como "J".
NOTA 2: Con "$w_i$", "$x_i$", "$y_i$", "$z_i$" denoto un miembro de un grupo que podría ser cualquiera (es decir, $z_i$ puede ser $z_1$, $z_2$, etc.)

Dividiremos todo en $14 $ posibles (sub)casos:

1) $X=0$ o $Y=0$
2) $Y\geq 1$ y $X\geq 1$
.... 2.1) $X=1$
........ 2.1.1) $W=0$
............ 2.1.1.1) $Z\geq 1$
................ 2.1.1.1.1) $Y=1$
................ 2.1.1.1.2) $Y\geq 2$
............ 2.1.1.2) $Z=0$
................ 2.1.1.2.1) $Y=1$
................ 2.1.1.2.2) $Y\geq 2$
........ 2.1.2) $W\geq 1$
............ 2.1.2.1) $Z=0$
................ 2.1.2.1.1) $Y=1$
................ 2.1.2.1.2) $Y\geq 2$
............ 2.1.2.2) $Z\geq 1$
................ 2.1.2.2.1) $Y=1$
................ 2.1.2.2.2) $Y\geq 2$
.... 2.2) $X\geq 2$
........ 2.2.1) $Y\geq 2$
........ 2.2.2) $Y=1$
............ 2.2.2.1) $W=0$
................ 2.2.2.1.1) $Z=0$
................ 2.2.2.1.2) $Z\geq 1$
............ 2.2.2.2) $W\geq 1$
................ 2.2.2.2.1) $Z=0$
................ 2.2.2.2.2) $Z\geq 1$

Diremos que un subgrupo de $3$ personas es bueno si son todos amigos, malo si nadie es amigo de nadie, y neutro si no es ni bueno ni malo.
1) $X=0$ o $Y=0$
Spoiler: mostrar
Si $X=0$, Juli puede ir al aula A, ya que es amigo de todos los de ahí.
Si $Y=0$, Juli puede ir al aula B, ya que no es amigo de nadie de ahí.
2.1.1.1.1) $X=1$, $W=0$, $Z\geq 1$, $Y=1$
Spoiler: mostrar
Veamos el grupo de Juli, $x_1$, $y_1$, $z_i$.
Sabemos que $y_1$ es amigo de Juli, pero no de $z_i$, y que Juli no es amigo ni de $x_1$ ni de $z_i$.
Evaluemos los posibles subgrupos de $3$:
En $Jx_1y_1$, Juli es amigo de $y_1$ pero no de $x_1$, luego no puede ser bueno ni malo.
En $Jz_iy_1$, Juli es amigo de $y_1$, pero $y_1$ no es amigo de ninguno de los dos, luego no puede ser ni bueno ni malo.
En $x_1y_1z_i$, sólo sabemos que $z_i$ no es amigo de $y_1$. Entonces puede ser malo, si $x_1$ no es amigo ni de $y_1$ ni de $z_i$.
En $Jx_1z_i$, sabemos que Juli no es amigo de $x_1$ ni de $z_i$, por lo tanto puede ser malo si $x_1$ no es amigo de $z_i$.
Por lo tanto, sea cualquiera de los dos posibles el subgrupo bueno o malo, en ambos casos $x_1$ y $z_i$ deben no ser amigos. Es decir, $x_1$ no es amigo de ningún miembro de $z$ (porque podríamos haber tomado a cualquier $z_i$).
Por lo tanto, una manera de separar las aulas sería:
En el aula A, $y_1$.
En el aula B, $x_1$ y todos los $z$.
Y Juli puede ir a cualquiera de las dos aulas, ya que es amigo de $y_1$ pero no de $x_1$ ni de ningún $z$.
2.1.1.1.2) $X=1$, $W=0$, $Z\geq 1$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo conformado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_i$ e $y_j$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí.
Evaluemos los $4$ posibles subgrupos de $3$:
En cualquier subgrupo va a haber alguno de los siguientes pares: $\{y_i, y_j\}, \{x_1, J\}$. Luego ningún subgrupo será bueno, por lo que debe haber uno malo. Pero si está Juli en un subgrupo de $3$, deben estar o $y_i$ o $y_j$, que son sus amigos, luego no podrá ser tampoco malo. Por lo tanto el único subgrupo potencialmente bueno o malo es $y_iy_jx_1$, que deberá ser malo, luego $x_1$ no es amigo de ningún $y_i$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_i$ y $z_i$. Sabemos que $x_1$ no es amigo ni de Juli ni de $y_i$, que Juli es amigo de $y_i$, y que $z_i$ no es amigo ni de Juli ni de $y_i$. Pero notemos que, al igual que antes, cualquier subgrupo de $3$ debe incluir al menos un par dentro de $\{y_i, z_i\}, \{x_1, J\}$, por lo que ningún subgrupo podrá ser bueno, luego debe haber uno malo. Este subgrupo malo no puede contener, al mismo tiempo, a Juli y a $y_i$, porque son amigos, luego el subgrupo malo debe contener a $x_1$ y a $z_i$, lo cual implica que $x_1$ no es amigo de ningún $z$.
Luego en el aula A puede ir Juli y en el aula B $x_1$, todos los $y$ y todos los $z$.
2.1.1.2.1) $X=1$, $W=0$, $Z=0$, $Y=1$
Spoiler: mostrar
Podemos poner a $y_1$ y a Juli en el aula A, y a $x_1$ en el aula B.
2.1.1.2.2) $X=1$, $W=0$, $Z=0$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo conformado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_i$ e $y_j$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. Analizando los $4$ subgrupos de $3$ posibles, el único donde pueden ser todos amigos o nadie amigo, es el de $y_iy_jx_1$, lo cual implica que $x_1$ no es amigo ni de $y_i$ ni de $y_j$ (es decir, $x_1$ no es amigo de ningún $y$).
Por lo tanto, podemos ubicar a $x_1$ en el aula B junto a todos los $y$, y a Juli en el aula A solo.
2.1.2.1.1) $X=1$, $W\geq 1$, $Z=0$, $Y=1$
Spoiler: mostrar
Veamos un grupo conformado por Juli, $x_1$, $y_1$ y $w_i$. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_1$, y que $x_1$ es amigo de $w_1$. Cualquier subgrupo de $3$ incluye a algún par entre $\{y_i, J\}, \{x_1, w_i\}$, luego no habrá un subgrupo malo, por lo que debe haber uno bueno, por lo tanto no pueden estar al mismo tiempo $x_1$ y Juli, luego deberán estar al mismo tiempo $y_1$ y $w_i$, que por consiguiente deberán ser amigos.
Entonces en el aula A ponemos a $y_1$ y a todos los $w$, mientras que en el aula B podemos poner a $x_1$. Juli puede ir a cualquiera de las dos aulas.
2.1.2.1.2) $X=1$, $W\geq 1$, $Z=0$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. De nuevo, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$, por lo que podemos poner en el aula A a Juli con todos los $w$, y en el aula B a $x_1$ junto a todos los $y$.
2.1.2.2.1) $X=1$, $W\geq 1$, $Z\geq 1$, $Y=1$
Spoiler: mostrar

Veamos un grupo conformado por $w_i$, $x_1$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ y de $w_i$, pero no de $x_1$, y que $w_i$ es amigo de $x_1$. En cualquier subgrupo habrá un par entre $\{J, y_1\}, \{x_1, w_i\}$, luego no habrá ningún subgrupo malo. Luego, un subgrupo bueno no puede contener al mismo tiempo a $x_1$ y a Juli, por lo que el subgrupo bueno deberá contener a $y_1$ y a $w_i$. Por lo tanto, $y_1$ es amigo de todos los $w$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_1$ y $z_i$. Sabemos que Juli es amigo de $y_1$ pero no de $x_1$ ni de $z_i$, y que $z_i$ no es amigo de $y_1$. En cualquier subgrupo habrá un par entre $\{J, x_1\}, \{y_1, z_i\}$, luego no habrá ningún subgrupo bueno. Luego, un subgrupo malo no puede contener al mismo tiempo a $y_1$ y a Juli, por lo que el subgrupo bueno deberá contener a $x_1$ y a $z_i$, por lo que $x_1$ será amigo de todos los $z$.
Por lo tanto en el aula A pueden ir $y_1$ y todos los $w$, y en el aula B pueden ir $x_1$ y todos los $z$. Juli podrá ir a cualquier aula porque es amigo de todos los del aula A, y no es amigo de ninguno de los del aula B.
2.1.2.2.2) $X=1$, $W\geq 1$, $Z\geq 1$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_1$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. De nuevo, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$.
Veamos ahora un grupo conformado por Juli, $x_1$, $y_i$ y $z_i$. Sabemos que $x_1$ no es amigo ni de Juli ni de $y_i$, que Juli es amigo de $y_i$, y que $z_i$ no es amigo ni de Juli ni de $y_i$. Pero notemos que cualquier subgrupo de $3$ debe incluir al menos un par dentro de $\{y_i, z_i\}, \{x_1, J\}$, por lo que ningún subgrupo podrá ser bueno, luego debe haber uno malo. Este subgrupo malo no puede contener, al mismo tiempo, a Juli y a $y_i$, porque son amigos, luego el subgrupo malo debe contener a $x_1$ y a $z_i$, lo cual implica que $x_1$ no es amigo de ningún $z_i$.
Por lo tanto, podemos poner en el aula A a Juli con todos los $w$, y en el aula B a $x_1$, todos los $y$ y todos los $z$.
2.2.1) $X\geq 2$, $Y\geq 2$
Spoiler: mostrar
Veamos un grupo formado por $y_i$, $y_j$, $x_i$ y Juli. Sabemos que Juli es amigo de $y_j$ y de $y_i$, pero no de $x_1$, y que $y_i$ e $y_j$ no son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, y_j\}, \{x_1, J\}$, por lo que no podrá haber un subgrupo bueno, Además, si un subgrupo incluye a Juli, incluirá a $y_i$ o a $y_j$, por lo que no podrá ser malo tampoco. Luego el subgrupo $x_1, y_i, y_j$ debe ser malo, y entonces $x_1$ no será amigo de ningún $y$.
Veamos ahora un grupo formado por $x_i$, $x_j$, $y_i$ y Juli. Sabemos que Juli es amigo de $y_i$ pero no de $x_i$ ni de $x_j$ que $y_i$ no es amigo ni de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Por un lado, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, x_j\}, \{x_i, J\}$, por lo que no podrá haber un subgrupo bueno. Pero por otro lado, cualquier subgrupo de $3$ incluirá a algún par entre $\{y_i, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero que en ese grupo de $4$ no haya ningún subgrupo bueno ni ningún grupo malo es una contradicción con el enunciado, por lo que no es posible que, al mismo tiempo, $X\geq 2$ y $Y\geq 2$.
2.2.2.1.1) $X\geq 2$, $Y=1$, $W=0$, $Z=0$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$, por lo que en el aula A pueden ir $y_1$ y todos los $x$, quedando Juli en el aula B.
2.2.2.1.2) $X\geq 2$, $Y=1$, $W=0$, $Z\geq 1$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$. Entonces en el aula A pueden ir $y_1$ y todos los $x$, y en el aula B pueden ir Juli y todos los $z$.
2.2.2.2.1) $X\geq 2$, $Y=1$, $W\geq 1$, $Z=0$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$.
Veamos ahora un grupo formado por $x_i$, $y_1$, $w_i$ y Juli. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_i$, y que $x_i$ es amigo de $y_1$ y de $w_i$. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, w_i\}$, por lo que no habrá ningún subgrupo malo. Por esto, un subgrupo no neutro no puede incluir al mismo tiempo a $x_i$ y a Juli, por lo tanto deberá incluir a $w_i$ y a $y_1$, por lo que $y_1$ será amigo de todos los $w$.
Luego, podemos poner en el aula A a $y_1$, todos los $x$ y todos los $w$, y en el aula B a Juli.
2.2.2.2.2) $X\geq 2$, $Y=1$, $W\geq 1$, $Z\geq 1$
Spoiler: mostrar
Veamos un grupo formado por $x_i$, $x_j$, $y_1$ y Juli. Sabemos que Juli es amigo de $y_1$ pero no de $x_i$ ni de $x_j$, y que $x_i$ y $x_j$ son amigos entre sí. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, x_j\}$, por lo que no podrá haber un subgrupo malo. Pero, de incluir a Juli, un subgrupo incluirá a $x_i$ o a $x_j$, por lo que el subgrupo no podría ser bueno tampoco. Por lo tanto, el único subgrupo que puede ser bueno o malo será $x_i$, $x_j$, $y_1$, por lo que $y_1$ será amigo de todos los $x$.
Veamos ahora un grupo formado por $x_i$, $y_1$, $w_i$ y Juli. Sabemos que Juli es amigo de $w_i$ y de $y_1$, pero no de $x_i$, y que $x_i$ es amigo de $y_1$ y de $w_i$. Cualquier subgrupo de $3$ incluirá a algún par entre $\{y_1, J\}, \{x_i, w_i\}$, por lo que no habrá ningún subgrupo malo. Por esto, un subgrupo no neutro no puede incluir al mismo tiempo a $x_i$ y a Juli, por lo tanto deberá incluir a $w_i$ y a $y_1$, por lo que $y_1$ será amigo de todos los $w$.
Luego, podemos poner en el aula A a $y_1$, todos los $x$ y todos los $w$, y en el aula B a todos los $z$ y a Juli.
Yo te banco pibe, en el 2016 nos reíamos ̶d̶e̶ con Ian por hacer estas cosas y miralo dónde está ahora!
2  
I said I was the cops
And your husband's in jail
The state looks down on sodomy!
Responder