Problema

Nivel de dificultad:
  • 8.67

Su valoración: No ha valorado al problema en un nivel de dificultad.
Las adivinanzas del mentiroso es un juego entre dos jugadores $A$ y $B$. Las reglas del juego dependen de enteros positivos $k$ y $n$ que son conocidos para ambos jugadores.

Al comienzo del juego $A$ escoge enteros $x$ y $N$ con $1 \le x \le N.$ El jugdor $A$ mantiene $x$ en secreto, y le revela de manera honesta $N$ al jugador $B$. El jugador $B$ ahora intenta obtener información sobre $x$ preguntándole al jugador $A$ preguntas de la siguiente forma:
Cada pregunta consiste en $B$ especificando un conjunto arbitrario $S$ de enteros positivos (posiblemente uno especificado en una pregunta previa), y preguntándole a $A$ si $x$ pertenece a $S$. El jugador $B$ puede preguntar todas las preguntas que él desee.
Después de cada pregunta,  $A$ debe responder inmediatamente con o no, pero se le permite mentir cuantas veces desee; la única restricción es que entre cualequiera $k+1$ respuestas consecutivas, una debe ser verdad.

Cuando $B$ termina de hacer todas las preguntas que quiera, debe especificar un conjunto $X$ de a lo sumo $n$ enteros positivos. Si $x$ pertenece a $X$, entonces $B$ gana; caso contrario, pierde. Demostrar que:

1. Si $n \ge 2^k,$ entonces $B$ tiene una estrategia ganadora.
2. Para todo $k$ suficientemente grande, existe un entero $n$ tal que $n \ge (1.99)^k$ de tal manera que $B$ no puede garantizar la victoria.

Autor Tema: IMO 2012 Argentina - Problema 3  (Leído 1184 veces)

AV

  • Perl!
  • Administrador
  • Hero Member
  • *****
  • Mensajes: 1331
  • ¿Qué se siente?
    • Ver Perfil
    • Quest For Freedom
IMO 2012 Argentina - Problema 3
« : julio 10, 2012, 03:22:18 pm »
Pusieron un juego como tres.

materechm

  • Alumno - Nivel 1
  • Miembro
  • *
  • Mensajes: 9
    • Ver Perfil
Re:IMO 2012 Argentina - Problema 3
« Respuesta #1 : julio 22, 2012, 12:05:05 pm »
yo tengo una solucion para ese problema pero no lo resolví sola y es muy larga... Me ayudó Michal Rolínek
« Última Modificación: julio 22, 2012, 01:53:02 pm por materechm »
"Mathematics consists on proving the most obvious things in the least obvious way."

AV

  • Perl!
  • Administrador
  • Hero Member
  • *****
  • Mensajes: 1331
  • ¿Qué se siente?
    • Ver Perfil
    • Quest For Freedom
Re:IMO 2012 Argentina - Problema 3
« Respuesta #2 : agosto 02, 2012, 05:51:20 am »
Tienes una solución? Eso sería muy sobresaliente, porque es un problema 3 de una IMO, muy difícil.

materechm

  • Alumno - Nivel 1
  • Miembro
  • *
  • Mensajes: 9
    • Ver Perfil
Re:IMO 2012 Argentina - Problema 3
« Respuesta #3 : agosto 13, 2012, 06:24:28 pm »
si la tengo :) pero mas que todo el que lo resolvió fue Michal Rolinek
"Mathematics consists on proving the most obvious things in the least obvious way."

materechm

  • Alumno - Nivel 1
  • Miembro
  • *
  • Mensajes: 9
    • Ver Perfil
Re:IMO 2012 Argentina - Problema 3
« Respuesta #4 : agosto 13, 2012, 07:46:55 pm »
la solución esta en ingles y es bastante larga pero aqui esta el resumen:

Spoiler (click to show/hide)
                                   

 
« Última Modificación: agosto 13, 2012, 07:48:56 pm por materechm »
"Mathematics consists on proving the most obvious things in the least obvious way."

 


zzz