Олимпиада имени Леонарда Эйлера2008-2009 учебный год, II тур заключительного этапа

На столе лежит 10 кучек с 1, 2, 3, 4, 5, 6, 7, 8, 9 и 10 орехами. Двое играющих берут по очереди по одному ореху. Игра заканчивается, когда на столе останется 3 ореха. Если это — три кучки по одному ореху, выигрывает тот, кто ходил вторым, иначе — его соперник. Кто из игроков может выигрывать, как бы не играл соперник? ( И. Рубанов, А. Шаповалов )

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

Комментарии от администратора Комментарии от администратора №1.     Решение 1. Назовем кучки из одного ореха единицами, а из двух — двойками. Первый должен придерживаться следующих правил: 1) если на доске есть единицы — убрать одну из них; 2) не брать из двоек. В остальном ходы первого могут быть любыми. Заметим, что число орехов в начале игры нечетно, значит, оно нечетно и перед любым ходом первого. Поэтому перед его ходом на доске всегда будет хотя бы одна нечетная кучка, то есть первый всегда сможет сделать ход, не нарушая описанных правил. Теперь заметим, после первого хода первого на доске нет единиц. После хода второго может появиться не более одной новой единицы, которую первый заберет. Значит, и после следующих ходов первого единиц на доске не будет, а после любого хода второго на доске будет не больше одной единицы. В частности, так будет и в конце игры, то есть первый выиграет.

Комментарии от администратора Комментарии от администратора №2.     Решение 2. Выигрывает первый. Каждым ходом он берет орех из самой маленькой кучки. Тогда после 15-го хода первого исчезнут не менее 5 кучек. Итак после ответного хода второго останется 15 орехов и не более 5 кучек. Если кучек ровно 5, то в наименьшей не больше 3 орехов. Поэтому еще через 3 хода первого и второго останется 9 орехов и не более 4 кучек. Если кучек ровно 4, то в наименьшей не более 2 орехов. Еще через 2 хода останется 5 орехов и не более 3 кучек. Если кучек ровно 3, то в наименьшей 1 орех. Взяв его, первый оставит всего 2 кучки и выиграет.