\(\qquad\)Два гравцi \(A\) та \(B\) грають у гру \(\it{Ти\ ж\ мене\ пiдманула}\). Правила цiєї гри залежать вiд двох натуральних чисел \(k\) та \(n\), якi вiдомi обом гравцям. \(\newline\)\(\qquad\)На початку гри \(A\) обирає натуральнi числа \(x\) i \(N\), для яких \(1 \le x \lt N\). Гравець \(A\) зберiгає число \(x\) у таємницi, а число \(N\) правдиво повiдомляє гравцю \(B\). Гравець \(B\) пiсля цього намагається отримати iнформацiю про \(x\), задаючи гравцю \(A\) питання наступним чином: перед кожним питанням \(B\) вказує довiльну множину \(S\) натуральних чисел (можливо, вже вказану в попередньому питаннi) та питає \(A\), чи належить \(x\) множинi \(S\). Гравець \(B\) може запитати стiльки питань, скiльки вiн захоче. На кожне задане \(B\) питання гравець \(A\) мусить одразу вiдповiдати \(\it{так}\) чи \(\it{нi}\), але йому дозволяється збрехати стiльки разiв, скiльки він забажає. Єдине обмеження — iз будь-яких \(k + 1\) послiдовних вiдповiдей принаймнi одна має бути правдивою. \(\newline\)\(\qquad\)Пiсля того, як \(B\) задав стiльки запитань, скiльки вiн уважав за потрiбне, вiн мусить указати множину \(X\) з щонайбiльше \(n\) натуральних чисел. Якщо \(x\) належить \(X\), то \(B\) перемагає; iнакше вiн програє. Доведiть, що: \(\newline\)\(\qquad\)1. Якщо \(n \ge 2^k\), то \(B\) має виграшну стратегiю. \(\newline\)\(\qquad\)2. Для довiльного достатньо великого \(k\) знайдеться таке цiле число \(n \ge 1.99^k\), що \(B\) не має виграшної стратегiї.
| Attributes | Олімпіадна |
|---|---|
| Source | International Mathematical Olympiad |
| Year | 2012 |
| Number | 3 |
| Difficulty | 10.0 |
| Themes |