Четвёртая открытая интернет-олимпиада по математике

======= 133 ========
ММ133 (3 балла)

На столе лежит N спичек. Петя и Вася поочерёдно берут оттуда от 1 до 5 спичек, однако нельзя повторять число, взятое соперником на предыдущем ходу. Выигрывает тот, кто забирает последнюю спичку. Начинает Петя, своим первым ходом может взять любое количество от 1 до 5. Найдите общий вид чисел N, при которых партию выиграет Вася.
====================================

Решение

Эта игра отличается от классической игры Баше тем, что позицию в ней можно однозначно определить не одинм, а парой чисел: (N, M), где N - число спичек, оставшееся на столе, а M - число спичек, взятое на предыдущем ходу. Тогда из позиции (N, M) игрок своим ходом может получить все позиции вида (N-K, K), для которых .

Построим и начнём заполнять таблицу выигрышных/проигрышных позиций:


Т.к. тот игрок, чья очередь хода наступит, когда стол опустел, проиграл, то весь нулевой столбец состоит из проигрышных позиций.

Найдём позиции, из которых можно одним ходом поставить противника в проигрышную позицию:


Выигрышными будут все позиции столбцов 1-5, кроме позиций вида (N,N).

Далее, из позиции (1,1) сделать ход согласно правилам невозможно, и она проигрышна. Тогда позиция (2,2) - выигрышна, т.к. из неё можно, взяв одну спичку, попасть в (1,1) и заставить проиграть соперника. Остальные позиции этой диагонали - проигрышные, т.к. все ходы из них ведут в ввыигрышные позиции.


Продолжая поочерёдно находить выигрышные и проигрышные позиции определяем, что в столбце 6 проигрышна только (6,3), а в столбце 7 - все позиции проигрышны, т.е., при старте с 7 спичек второй игрок выиграет. Далее получаем такую картину:


Замечаем, что столбцы 22-26 повторяют столбцы 9-13. Т.к. значение, стоящее в ячейке полностью определяется значениями ячеек в предыдущих пяти столбцах, то сформировался период и полностью из нулей будут состоять столбцы вида 13k и 13k+7 Обсуждение

Здесь иллюстрируются общие принципы, которыми лично я руководствуюсь при решении основной части задач на математические игры. Как оказалось, среди участников трое применяют аналогичный подход, остальтные успешно использовали математическую индукцию.

Некоторым участникам помешало набрать максимальное количество баллов то, что они заметили периодичность, но неверно определили её характер.

Награды
За правильное решение задачи Сергей Половинкин, Анатолий Казмерчук, Алексей Волошин, Владислав Франк, Евгений Гужавин и Александр Ларин получают по 3 призовых балла.
Дмитрий Пашуткин и Николай Дерюгин получают по 1 призовому баллу.

Эстетическая оценка задачи 4.6 баллов ====================================
Разбор задачи ММ133 подготовил Алексей Извалов.