Q13 Matemática  (IMO Shortlist 2012)

jogo de adivinhação do mentiroso é um jogo entre dois jogadores $A$ e $B$. As regras do jogo dependem de dois inteiros positivos $k$ e $n$ que são conhecidos por ambos os jogadores. No início do jogo $A$ escolhe os inteiros $x$ e $N$ com $1\le x\le N.$ O jogador $A$ mantém $x$ em segredo e diz a verdade $N$ ao jogador $B$. O jogador $B$ agora tenta obter informações sobre $x$ fazendo perguntas ao jogador $A$ da seguinte forma: cada pergunta consiste em $B$ especificando um conjunto arbitrário $S$ de inteiros positivos (possivelmente um especificado em alguma pergunta anterior), e perguntando a $A$ se $x$ pertence a $S$. O jogador $B$ pode fazer quantas perguntas quiser. Após cada pergunta, o jogador $A$ deve responder imediatamente com sim ou não, mas pode mentir quantas vezes quiser; a única restrição é que, entre quaisquer $k+1$ respostas consecutivas, pelo menos uma resposta deve ser verdadeira. Depois que $B$ fizer quantas perguntas quiser, ele deve especificar um conjunto $X$ de no máximo $n$ inteiros positivos. Se $x$ pertencer a $X$, então $B$ vence; caso contrário, ele perde. Prove que: 1. Se $n\ge 2^k,$ então $B$ pode garantir uma vitória. 2. Para todo $k$ suficientemente grande, existe um inteiro $n\ge (1.99{)}^k$ tal que $B$ não pode garantir uma vitória. Proposto por David Arthur, Canadá