Задание №178062: Турнир Ломоносова 2008

1. «Конфеты». На примерах, приводимых в пунктах «а» – «г» участ
никам предлагалось попробовать поиграть, перебрать варианты ходов и
нащупать закономерности игры. Мы же представим себе, что этот пред
варительный этап пройден и приведём решение сразу для пункта «д».
Ответ: если количество конфет на столе равно 6k + 1 или 6k + 2
для k = 0, 1, 2, 3,..., то победит Фрекен Бок, иначе — Малыш.
Это решение нетрудно получить, пользуясь так называемым «мето
дом выигрышных и проигрышных позиций» или «анализом игры с
конца». В самом деле, пусть игра началась с какого-то большого числа
конфет. Чем она закончилась? Тем, что у игрока нет хода. Это бывает,
когда конфет ему досталось 1 или 2. Эти позиции проигрышные для
того, кому они достались — обозначим их буквой «П» («проигрышная»).
Позиция 3 — выигрышная. Имея три конфеты, игрок делит их на
три «кучки» по конфете, и соперник, оставив одну из них, не сможет
её поделить.
Это же можно сделать и при 4, 5 и 6 конфетах. Разумеется, делить
на кучки надо с умом. Так, деля 6 конфет на 1 + 1 + 4, мы позво
лим сопернику оставить кучку в 4 конфеты и поделить её; разложив
же 6 = 2 + 2 + 2, мы его этой возможности лишим. Значит, помечаем
позиции 3, 4, 5 и 6 буквой «В» («выигрышная»). Теперь рассмотрим
7 конфет. При любом делении найдётся кучка из по крайней мере трёх
конфет, которую соперник оставит себе для деления, а значит побе
дит. Стало быть, 7 — проигрышная позиция. И постепенно расставляем
буквы «В» (выигрышная) и «П» (проигрышная) против позиций, запол
няя табличку:
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
П П В В В В П П В В В В П ...
Сама по себе табличка достаточно красноречиво убеждает в верно
сти ответа, но мы приведём теперь и строгое его доказательство мето
дом математической индукции. Индукция ведётся по k — параметру,
который мы использовали для записи ответа.
База (k = 0) нами разобрана.
Пусть теперь (шаг индукции) для всех k < m ответ доказан. Рас
смотрим k = m. Числа 6m + 1 и 6m + 2 невозможно разбить на три
слагаемых, дающих при делении на 6 остатки 1 или 2. Это проверяется

34

перебором всех возможных троек остатков:
1 + 1 + 1 = 3
1 + 1 + 2 = 4

1 + 2 + 2 = 5
2 + 2 + 2 = 6
Значит, как бы ходящий не разбил 6m + 1 или 6m + 2 на три кучки,
соперник оставит из них для дальнейшего деления кучку, дающую оста
ток, больший 2, при делении на 6. Тем самым, 6m + 1 и 6m + 2 — про
игрышные позиции.
Напротив, числа 6m + 3, 6m + 4, 6m + 5 и 6m + 6 можно разбить на
«плохие» для соперника кучки:

6m + 3 = (6m + 1) + 1 + 1
6m + 4 = (6m + 1) + 1 + 2
6m + 5 = (6m + 1) + 2 + 2
6m + 3 = (6m + 2) + 2 + 2

То есть, это позиции выигрышные. Доказательство завершено.
Критерии проверки. За решение пункта «а» давалось 2 балла,
за решение каждого следующего пункта (вплоть до «г») — на 1 балл
больше предыдущего. Решение пункта «д» оценивалось 20-ю баллами,
если решающий не забывал указать верные ответы предыдущих пунк
тов (если ответы не были указаны, то тогда 18 баллов). Кроме этого
укажем, что за «голые» ответы в пунктах «а»–«г» не ставилось ничего,
а в пункте «д» 1 балл; за указание проигрышных позиций без страте
гии в «д» ставилось 2 балла, а при наличии ответа — 3 балла. Не более
1 балла ставилось в пунктах «а»–«г» за неполный перебор, ошибки в
переборе, ссылку на неверно разобранный предыдущий пункт.