IMO 2012 en Mar del Plata – Problema nº 3

Tercer problema de la IMO 2012, celebrada en Mar del Plata en julio de este año. Ahí va:

El juego de la adivinanza del mentiroso es un juego para dos jugadores A y B. Las reglas del juego dependen de dos enteros positivos k y n conocidos por ambos jugadores.

Al principio del juego, el jugador A elige enteros x y N con 1 \le x \le N. El jugador A mantiene x en secreto, y le dice a B el verdadero valor de N. A continuación, el jugador B intenta obtener información acerca de x formulando preguntas a A de la siguiente manera: en cada pregunta, B especifica un conjunto arbitrario S de enteros positivos (que puede ser uno de los especificados en alguna pregunta anterior), y pregunta a A si x pertenece a S. El jugador B puede hacer tantas preguntas de ese tipo como desee. Después de cada pregunta, el jugador A debe responderla inmediatamente con o no, pero puede mentir tantas veces como quiera. La única restricción es que entre cualesquiera k+1 respuestas consecutivas, al menos una debe ser verdadera.

Cuando B haya formulado tantas preguntas como haya deseado, debe especificar un conjunto X de a lo más n enteros positivos. Si x pertenece a X entonces gana B; en caso contrario, pierde.

Demostrar que:

  1. Si n \ge 2^k, entonces B puede asegurarse la victoria.
  2. Para todo k suficientemente grande, existe un entero n \ge (1,99)^k tal que B no puede asegurarse la victoria.

Que se os dé bien.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

2 Comentarios

  1. Según está planteado el problema, B nunca podrá asegurarse la respuesta correcta salvo que n=N. Para ello, la estrategia que seguirá A será responder sí-no-sí-no-… a las preguntas de B. Esta secuencia cumple la condición impuesta de que haya al menos una respuesta verdadera en cualquier secuencia de k+1 respuestas consecutivas, y no da ninguna información a B.

    Publica una respuesta
  2. El objetivo del juego es obtener información; puesto que la opción inicial es que al menos una cualquiera de las k+1 respuestas debe ser verdadera, se puede considerar como k+1 opciones lógicas unidas con una “o” Sería imposible verificar cuál de todas es verdadera, así que enfrentemos el reto por la negación de estas “o” es decir que evaluemos si para algún conjunto de números se puede obtener algún número que no esté en  \boldsymbol {ninguno} de los k+1 subconjuntos.

    Para hacer esto, empecemos dividiendo el conjunto original en la mitad y preguntando si x pertenece a este subconjunto; de la mitad donde supuestamente no está x -llamémoslo  S_1 – preguntamos si x está en esta mitad, la mitad en que la respuesta no está x, llamémoslo  S_2 , procedemos a hacer lo mismo. Es decir se divide el conjunto de N números en k+1 subconjuntos donde el último está compuesto por  {N \over 2^{k+1}} elementos. puesto que en este último subconjunto no están ciertos números y por la forma como fueron construidos no están en ningún otros subconjunto, se puede afirmar que en éstos no está x.

    Hasta ahora no hemos detallado el número N, si es par o impar , etc. Veamos como influye esto en el procedimiento:
    1.  N\geqslant2^{k+1} En este caso, siempre se puede eliminar al menos un número, puesto que el último subconjunto tendrá al menos un elemento.
    2.  N<2^{k+1} En este caso cambiamos el procedimiento: Siguiendo los mismos pasos, cuando se llegue a la última pregunta habrá un número del cual no podrá obtenerse información, pero igual se pregunta si este número  {y} \ es igual a x. Si se dice que no, este número puede descartarse, si se responde que sí, se parte de ésta para reiniciar el procedimiento, pero esta vez teniendo  2^k respuestas, de donde se podrá descartar algún numero.
    3. Finalmente, cuando  N = 2^k no se podrá obtener más información, así que si  n \eqslantgtr2^k se tendría con certeza que x pertenece al subconjunto de  S_1 sin contar el último número encontrado y el valor mínimo elementos de este subconjunto es  N = 2^k

    De esta manera se demuestra que por este procedimiento se obtiene una respuesta.

    Para la segunda parte, de acuerdo a los preceptos tenidos en cuenta y ya que N es grande, se tendría  n < 2^k y por lo tanto, no podría asegurarse la victoria.

    De esta manera se tendría la respuesta al problema, pero tengo dos observaciones:
    1. Que este procedimiento sea óptimo, porque de lo contrario no podría responder la parte b del problema ya que podría existir otro procedimiento aún mejor y que pueda encontrar una solución con menos valores.
    2. He pensado en este problema varias horas y creo haber encontrado una solución, sin embrago, estos niños en hora y media deben haber encontrado la respuesta, NOTABLE!!

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Tercer problema de la IMO 2012, celebrada en Mar del Plata en julio de…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *