34 T. I. de las Ciudades Primavera 2012 N Mayor Problema 7

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

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

34 T. I. de las Ciudades Primavera 2012 N Mayor Problema 7

Mensaje sin leer por Nacho »

El rey decidió reducir su gabinete que consiste de [math] genios. Los colocó en una fila y les colocó sombreros con números enteros de [math] a [math], no necesariamente en ese orden (escondió un sombrero). Cada genio puede ver los números de los sombreros de todos los que están adelante suyo, pero no puede ver el propio ni los que están detrás suyo. Por orden del rey, comenzando por el final de la fila, cada genio dice un entero de [math] a [math] de modo que todos los genios lo oigan. Ningún número se puede repetir dos veces. Al final, cada genio que no haya dicho el número de su propio sombrero es expulsado del gabinete. Los genios conocen las reglas y pueden desarrollar entre ellos estrategias antes de que les repartan los sombreros.

a) Determinar si los genios pueden desarrollar una estrategia que les garantice que más de [math] de ellos permanezcan en el gabinete. (5 puntos)

b) Determinar si los genios pueden desarrollar una estrategia que les garantice que por lo menos [math] de ellos permanezcan en el gabinete. (7 puntos)
"Though my eyes could see I still was a blind man"

Avatar de Usuario
Prillo

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

Re: 34 T. I. de las Ciudades Primavera 2012 N Mayor Problema

Mensaje sin leer por Prillo »

Spoiler: mostrar
Se puede salvar con certeza a [math] genios.

Para la siguiente solución vamos a usar lo que se conoce como la paridad de una permutación.

Brevemente, sea [math] un entero positivo. Dada una permutación [math] de los números enteros del [math] al [math], esta permutación se puede obtener empezando por la permutación [math], e intercabiando pares de números distintos en cada paso. Por ejemplo, la permutación [math] se puede obtener de la permutación [math] intercambiando primero el [math] con el [math], y luego el [math] con el [math]. Hay infinitas formas de obtener la permutación [math] a partir de la permutación inicial [math]. Sin embargo, hay un teorema que nos dice que no importa cómo se haga estas operaciones, la cantidad de operaciones hechas tiene siempre la misma paridad. Si esta cantidad es par, decimos que [math] es un parmutación par. En caso contrario decimos que [math] es una permutación impar. Entonces, con esta definición, la permutación [math] es par. Un ejemplo de una permutación impar sería [math].

Vamos a mostrar que es posible salvar con certeza a [math] de los genios. La estrategia es la siguiente (más adelante mostraremos porqué está bien definida): Sean [math] los genios. Sean [math] los números de sus sombreros respectivamente. El genio [math] puede ver los números [math]. Sea [math] la sucesión de números que se va formando a medida que los genios dicen números. Cuando le toca el turno al genio [math], considera las siguientes dos permutaciones:
[math]
[math]
donde [math] e [math] son los dos números del conjunto [math] que no aparecen entre
[math]
Notemos que de las permutaciones [math] y [math], una es par y la otra es impar, ya que [math] se obtiene de [math] intercambiando los números [math] e [math]. El genio [math] se queda con la permutación que sea par. Supongamos sin pérdida de generalidad que [math] es la permutación par (por simetría de [math] e [math]). Para elegir entre [math] e [math], si [math] es par, el genio [math] elige [math], y si [math] es impar, elige [math].

Vamos a demostrar que esta estrategia está bien definida y que con ella todos los genios a partir del segundo se salvan. Para mostrar la buena definición de la estrategia, que sería la unicidad de [math] e [math] en cada paso, observamos que a lo largo del procedimiento ningún genio dice el número del sombrero de un genio de más adelante. Esto también implica que en el turno del genio [math], su número de sombrero [math] debe ser [math] ó [math]. Y ahora para ver que se salvan todos los genios a partir del segundo, supongamos a modo de contradicción que hay algún genio [math] ([math]) que con este procedimiento no dice el número de su sombrero. Supongamos que [math] es par (el caso [math] impar es análogo). Supongamos que en su turno, [math] eligió la permutación par
[math]
y por lo tanto a continuación escogió [math]. Pero por suposición la elección fue incorrecta, ó sea que su sombrero era en realidad [math]. Sea [math] el número que había elegido en el turno anterior [math]. ¿Qué pasó en el turno anterior? [math] tenía que elegir entre las permutaciones
[math]
[math]
Como [math] es impar, sabemos que [math] tuvo que haber elegido la permutación [math] para quedarse con [math] (por definición del procedimiento). Luego [math] es par. Pero [math] se obtiene de [math] intercambiando las posiciones de [math] y [math], ó sea que [math] debería ser impar. Esto contradice que [math] sea par. Luego con este procedimiento todos los genios salvo quizá el primero, se salvan.

Mariano Juncal

Colaborador-Varias OFO - Medalla de Bronce-OFO 2015
Mensajes: 37
Registrado: Sab 16 Oct, 2010 6:49 pm
Medallas: 2

Re: 34 T. I. de las Ciudades Primavera 2012 N Mayor Problema

Mensaje sin leer por Mariano Juncal »

Larga vida al Rey Prillo.

tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años 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
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
Mensajes: 607
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 12
Nivel: Exolímpico

Re: 34 T. I. de las Ciudades Primavera 2012 N Mayor Problema

Mensaje sin leer por tuvie »

Se me ocurrió una solución usando congruencias, despues a la tarde la subo.

tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años 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
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
Mensajes: 607
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 12
Nivel: Exolímpico

Re: 34 T. I. de las Ciudades Primavera 2012 N Mayor Problema

Mensaje sin leer por tuvie »

Spoiler: mostrar
Vamos a demostrar que con certeza se pueden salvar [math], y con suerte el otro :P .
Sea [math] la persona con [math] personas por detrás. A [math] le asignanos [math], la respuesta de [math] y [math] el gorro de [math]. Vamos a trabajar con congruencias módulo [math].
Lo que hace [math] es sumar todos los gorros que ve y decir su resto módulo [math]. Notemos que [math] ve todos los gorros que veía [math], menos el suyo, entonces calcula el resto en la división por [math] de la suma de los gorros que ve. Sea este número, el que piensa [math], [math]. Ahora [math] calcula [math], para un entero positivo [math] adecuado. Ese número es la solución al sistemaa de congruencias que tenemos, pues tenemos un total y otro total sin un número. Este sistema tiene una única solución, pues ningún par de gorros tienen dos números con el mismo resto en la división por [math], pues son todos enteros positivos menores a iguales a [math]. Ahora, para todo [math], con [math], lo que calcula es [math], para un [math] entero positivo adecuado, que como dijimos antes, funciona.
Entonces concluímos que para todo [math], [math] se salva, y, con suerte, [math] también.

Avatar de Usuario
Prillo

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

Re: 34 T. I. de las Ciudades Primavera 2012 N Mayor Problema

Mensaje sin leer por Prillo »

Ningúno de los números que dicen los genios se puede repetir. En tu argumento puede ser que un genio [math] con [math] repita el número que dijo [math].
2  

tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años 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
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
Mensajes: 607
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 12
Nivel: Exolímpico

Re: 34 T. I. de las Ciudades Primavera 2012 N Mayor Problema

Mensaje sin leer por tuvie »

Prillo escribió:Ningúno de los números que dicen los genios se puede repetir. En tu argumento puede ser que un genio [math] con [math] repita el número que dijo [math].
Tenés razón, igual se puede modificar un poco, no para resolver el problema, si no para garantizar que [math] se salven, resolviendo la parte a).
EDIT: Esta idea se caga, pero debe venir por acá la idea de la parte a)

Nowhereman

FOFO 6 años - Mención Especial-FOFO 6 años
Mensajes: 65
Registrado: Mar 17 Mar, 2015 12:18 pm
Medallas: 1
Nivel: 3

Re: 34 T. I. de las Ciudades Primavera 2012 N Mayor Problema

Mensaje sin leer por Nowhereman »

tuvie escribió:
Prillo escribió:Ningúno de los números que dicen los genios se puede repetir. En tu argumento puede ser que un genio [math] con [math] repita el número que dijo [math].
Tenés razón, igual se puede modificar un poco, no para resolver el problema, si no para garantizar que [math] se salven, resolviendo la parte a).
EDIT: Esta idea se caga, pero debe venir por acá la idea de la parte a)
La idea para la parte a para mi es que el genio numero 1000 le diga al 999 el numero de su sombrero, el 998 al 997, y asi de esta manera se salvarian exactamente la mitad.

Responder