IMO олимпиада по математике 2012 года | Казахстанские олимпиады

Два игрока $A$ и $B$ играют в игру Угадай-ка. Правила этой игры зависят от двух положительных целых чисел $k$ и $n$, и эти числа известны обоим игрокам. В начале игры $A$ выбирает целые числа $x$ и $N$ такие, что $1\le x\le N$. Игрок $A$ держит число $x$ в секрете, а число $N$ честно сообщает игроку $B$. После этого игрок $B$ пытается получить информацию о числе $x$, задавая игроку $A$ вопросы следующего типа: за один вопрос $B$ указывает по своему усмотрению множество $S$, состоящее из целых положительных чисел (возможно, это множество уже было указано в одном из предыдущих вопросов) и спрашивает игрока $A$ принадлежит ли число $x$ множеству $S$. Игрок $B$ может задать столько вопросов, сколько он хочет. На каждый вопрос игрока $B$ игрок $A$ должен сразу ответить да или нет, при этом ему разрешается соврать столько раз, сколько он хочет; единственное ограничение состоит в том, что из любых $k+1$ подряд идущих ответов хотя бы один ответ должен быть правдивым.
После того, как $B$ задаст столько вопросов, сколько он сочтет нужным, он должен указать множество $X$, содержащее не более $n$ целых положительных чисел. Если $x$принадлежит множеству $X$, то игрок $B$ выиграл; иначе $B$ проиграл. Докажите, что:
1. Если $n\ge {{2}^{k}}$, то $B$ может гарантировать себе выигрыш.
2. Для всякого достаточно большого $k$ найдется целое число $n\ge {{1,99}^{k}}$, при котором игрок $B$ не сможет гарантировать себе выигрыш.