ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65066
Темы:    [ Теория игр (прочее) ]
[ Четность и нечетность ]
[ Принцип крайнего (прочее) ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

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


Решение 1

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


Решение 2

Приведём другую выигрывающую стратегию. Пусть каждым ходом первый берёт орех из самой маленькой кучки. Тогда после 15-го хода первого исчезнут не менее пяти кучек. После ответного хода второго останется 15 орехов и не более пяти кучек. Если кучек ровно пять, то в наименьшей не больше трёх орехов. Поэтому ещё через три хода первого и второго останется девять орехов и не более четырёх кучек. Если кучек ровно четыре, то в наименьшей – не более двух орехов. Ещё через два хода останется пять орехов и не более трёх кучек. Если кучек ровно три, то в наименьшей – один орех. Взяв его, первый оставит всего две кучки и выиграет.


Ответ

Первый.

Источники и прецеденты использования

олимпиада
Название Олимпиада имени Леонарда Эйлера (для 8 классов)
год/номер
Номер 1 (2009 год)
тур
задача
Номер 7

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .