IMO 2007 - P3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Gianni De Rico

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

IMO 2007 - P3

Mensaje sin leer por Gianni De Rico »

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.
♪♫ do re mi función lineal ♪♫
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: IMO 2007 - P3

Mensaje sin leer por usuario250 »

No tengo ganas de postear mi solución acá. cualquier cosa, preguntenlé a Peter que ya se la expliqué a él.
7  
Carlos V.
Mensajes: 13
Registrado: Lun 19 Oct, 2020 10:14 pm

Re: IMO 2007 - P3

Mensaje sin leer por Carlos V. »

Si no entendí mal, la cosa viene más o menos sencilla.
Spoiler: mostrar
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.
Avatar de Usuario
Gianni De Rico

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

Re: IMO 2007 - P3

Mensaje sin leer por Gianni De Rico »

Carlos V. escribió: Sab 07 Nov, 2020 11:00 pm
Spoiler: mostrar
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.
Ojo con esto
Spoiler: mostrar
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.
Carlos V. escribió: Sab 07 Nov, 2020 11:00 pm
Spoiler: mostrar
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
Spoiler: mostrar
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 ;)
♪♫ do re mi función lineal ♪♫
Carlos V.
Mensajes: 13
Registrado: Lun 19 Oct, 2020 10:14 pm

Re: IMO 2007 - P3

Mensaje sin leer por Carlos V. »

:lol: jajaja, lo leí como tres veces y creí que lo entendí. Me ayudó tu aclaración.
Responder