Nacional 2019 - Nivel 2 - Problema 5

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

OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Mención
Mensajes: 159
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 3
Nivel: 1

Nacional 2019 - Nivel 2 - Problema 5

Mensaje sin leer por Monazo » Jue 14 Nov, 2019 11:04 am

En un club algunos pares de socios son amigos. Dado $k\geq 3$ diremos que un club es $k-amigable$ si en todo grupo de $k$ socios estos se pueden sentar en una mesa redonda de modo que cada par de vecino son amigos.
A) Demostrar que si un club es $6-amigable$ entonces es $7-amigable$.
B) ¿Es cierto que si un club es $9-amigable$ entonces es $10-amigable$?.

Sandy

OFO - Medalla de Bronce
Mensajes: 71
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 1
Nivel: 2

Re: Nacional 2019 - Nivel 2 - Problema 5

Mensaje sin leer por Sandy » Sab 16 Nov, 2019 3:03 am

Spoiler: mostrar
Primero una observación: si un club es $k$-amigable entonces todos los subclubes incluidos en él lo son. Además, si todos los subclubes lo son, el club debe serlo (ya que incluye a todo grupo de $k$ personas posible).
Entonces con ver que un club de $7$ personas $6$-amigable debe ser también $7$-amigable ganamos, ya que aplicamos este razonamiento a cada subclub de $7$ personas. Pero asumamos lo contrario.

Supongamos que en este club hay un socio (llamémoslo Juan$_1$) con menos de $3$ amigos.
Tomamos el grupo de $6$ que excluye a uno de ellos y Juan$_1$ no puede tener de vecinos a dos amigos (ya que en dicho club tiene sólo $2$ y uno quedó excluido), luego el club no es $6$-amigable, absurdo. Entonces todos tienen al menos $3$.

Supongamos ahora que existe un socio Juan$_2$ que tiene al menos $4$ amigos.
Tomaremos el grupo de $6$ socios que no lo incluye y veremos que debe haber dos socios consecutivos amigos de Juan$_2$, luego Juan$_2$ se sienta entre ellos y perdimos porque se pueden sentar los $7$. Pero intentemos evitar esto. Los sentamos a los $6$ en una mesa redonda (lo cual es posible, ya que es $6$-amigable). Supongamos, sin pérdida de generalidad, que Juan$_2$ es amigo de Juan$_3$. Luego no puede ser amigo Juan$_2$ de ninguno de los adyacentes a Juan$_3$. Quedan sólo 3 socios en la ronda, pero si Juan$_2$ fuese amigo de todos, sería amigo de $3$ adyacentes (y en particular de $2$). Luego nadie tiene más de $3$ amigos.

Por lo tanto todos deben tener $3$ amigos, y en total sumarían $7\times 3=21$ amistades, pero cada amistad, al ser recíproca entre $2$, debe sumar $2$ a esa suma, por lo que debe ser siempre par, lo cual es un absurdo. Luego o alguien tiene menos de $3$ amigos (y el club no es $6$-amigable) o alguien tiene más de $3$ amigos (y el club es $7$-amigable)

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 893
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nacional 2019 - Nivel 2 - Problema 5

Mensaje sin leer por Fran5 » Sab 16 Nov, 2019 7:15 pm

Parte b)
Spoiler: mostrar
Esto es un spoiler... Seguro que no querés seguir pensando un poquito?
Spoiler: mostrar
Dalee, no te ortives. Pensa un contraejemplo
Spoiler: mostrar
Es tu última oportunidad de seguir pensando antes de spoilearte...
Spoiler: mostrar
El grafo de Petersen tiene un camino hamiltoniano pero no un ciclo hamiltoniano [...]. Es hipoamiltoniano, lo que significa que aunque no tiene un ciclo hamiltoniano, al eliminar cualquier vértice se convierte en hamiltoniano, y es el grafo hipoamiltoniano más pequeño.


Nora: Un camino Hamiltoniano es un recorrido de los vértices del grafo. Un ciclo es un camino que termina en el mismo punto del inicio.
Si nuestros vértices son los socios, y dos socios están unidos si son amigos, entonces que haya un ciclo Hamiltoniano es lo mismo que ubicarlos a todos en una mesa redonda.
3  
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
NPCPepe

FOFO 9 años - Mención Especial
Mensajes: 17
Registrado: Lun 17 Jun, 2019 9:22 pm
Medallas: 1
Nivel: 2

Re: Nacional 2019 - Nivel 2 - Problema 5

Mensaje sin leer por NPCPepe » Vie 22 Nov, 2019 9:19 am

jajaja se re zarparon con el pentagrama ese era para perder tiempo tratar de resolver el b
$3=569936821221962380720^3+(-569936821113563493509)^3+(-472715493453327032)^3$: esta es la tercer menor solucion descubierta para la ecuación $a^3+b^3+c^3=3$ , las otras dos son $1^3+1^3+1^3=3$ y $4^3+4^3+(-5)^3=3$

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 893
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nacional 2019 - Nivel 2 - Problema 5

Mensaje sin leer por Fran5 » Sab 23 Nov, 2019 6:20 pm

La idea era encontrar 10 personas tales que cada uno tenía tres amigos. Una forma era hacer un ciclo de 9 con uno en el medio. Querés que todo sea simétrico así que al décimo lo unis con el 3ro 6to y 9no.
Luego unis 1 y 5; 4 y 8; 7 y 11, es decir, 7 y 2
Te queda que todos tienen 3 amigos y ves que anda
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Responder