Imo 2012

O desafio do mentiroso é um jogo para dois jogadores A e B. As regras do jogo dependem de dois inteiros positivos k e n conhecidos por ambos os jogadores. 
No início do jogo, o jogador A escolhe inteiros x e N com 1≤ x ≤N. O jogador A mantém x em segredo, e diz a B o verdadeiro valor de N. Em seguida, o jogador B tenta obter informação acerca de x fazendo perguntas a A da seguinte maneira: em cada pergunta, B especifica um conjunto arbitrário S de inteiros positivos (que pode ser um dos especificados nalguma pergunta anterior), e pergunta a A se x pertence a S. O jogador B pode fazer tantas perguntas desse tipo como deseje. Depois de cada pergunta, o jogador A deve responder imediatamente com sim ou não, mas pode mentir tantas vezes como queira. A única restrição é que dadas quaisquer k+1 respostas consecutivas, pelo menos uma deve ser verdadeira.
Quando B tenha feito tantas perguntas como pretenda, deve especificar um conjunto X com no máximo n inteiros positivos. Se x pertencer a X então ganha B; caso contrário, B perde. Prove que:

1. Se n ≥ 2^k, então B pode garantir a sua vitória.

2. Para todo k suficientemente grande, existe um inteiro n≥1,99^k tal que B não pode garantir a sua vitória.