Районная олимпиада, 2015-2016 учебный год, 8 класс


$A$ и $B$ играют в игру. Ход состоит в том, что соответствующий игрок называет натуральное число, меньшее $31$, которое не равно ни одному из названных ранее чисел и не имеет общих делителей больше $1$ ни с одним из названных ранее чисел. После этого ход переходит к другому игроку. Проигрывает тот, кто не может сделать ход. Начинает $A$. У кого из игроков есть выигрышная стратегия?
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Ответ. У игрока $A$.
Решение. Приведем стратегию игрока $A$, по которой он может выиграть. Первым своим ходом он называет число 30. Тогда $B$ не может назвать четные числа, числа делящиеся на 3 и на 5. Поэтому $B$ может назвать только одно число из множества $\{1,7,11,13,17,19,23,29\}$. Заметим, что все эти числа попарно взаимно просты. Поэтому игроки $A$ и $B$ будут выбирать числа только из этого множества, не препятствуя выбору других чисел из этого множества. Так как в этом множестве 8 чисел, то игрок $A$ возьмет последнее число.