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

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

Условие

Коля и Витя играют в следующую игру. На столе лежит куча из 31 камня. Мальчики делают ходы поочерёдно, а начинает Коля. Делая ход, играющий делит каждую кучку, в которой больше одного камня, на две меньшие кучки. Выигрывает тот, кто после своего хода оставляет кучки по одному камню в каждой. Сможет ли Коля сделать так, чтобы выиграть при любой игре Вити?
Также доступны документы в формате TeX

Решение

Ответ: нет. Достаточно проследить за наибольшей кучкой. Пусть перед ходом игрока A в наибольшей кучке лежит 2n - 1 камней. Тогда после его хода в наибольшей кучке лежит от 2n - 1 до 2n - 2 камней. Поэтому игрок B всегда может добиться, чтобы в наибольшей кучке лежало 2n - 1 - 1 камней. В таком случае игрок B выигрывает. Итак, если число камней в исходной игре имеет вид 2n - 1, то Витя сможет выиграть. Если же число камней в исходной игре не равно 2n - 1, то оно заключено между 2n и 2n+1 - 2 для некоторого n. В таком случае Коля первым ходом добивается, чтобы число камней в наибольшей кучке было равно 2n - 1. После этого он всегда может выиграть.
Также доступны документы в формате TeX

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

олимпиада
Название Московская математическая олимпиада
год
Номер 38
Год 1975
вариант
Класс 7
Тур 2
задача
Номер 3

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

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