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

Условие задачи
В двух коробках лежат спички.

Два игрока делают ходы по очереди. За один ход можно:

а) забрать одну спичку из первой коробки, или
б) забрать по одной спичке из обеих коробок, или
в) забрать две спички из второй коробки, или
г) переложить одну спичку из второй коробки в первую.

Выигрывает тот, кто оставляет обе коробки пустыми.

Кто (игрок, начинающий игру, или его соперник) выиграет, если игроки не делают ошибок и вначале в первой коробке 20 спичек, а во второй десять?

Решение
Позицию в игре можно описать парой чисел (x,y), где x – количество спичек в первой коробке, а y –во второй.

Правила игры позволяют сделать следующие ходы:
а) (x,y) –> (x-1,y), при x>0;
б) (x,y) –> (x-1,y-1), при x>0 и y>0;
в) (x,y) –> (x,y-2), при y>1;
г) (x,y) –> (x+1,y-1), при y>0.

Цель игры – своим ходом оставить другому позицию (0,0). Тот игрок, чья очередь хода из этой позиции – проиграл.

Начертим таблицу 21х11 ячеек и поставим в ячейку (0,0) букву П. Далее, аналогично анализу Баше-подобных игр, найдём в этой игре выигрышные и проигрышные позиций. Напомним, что выигрышные позиции – это те, из которых одним из ходов можно попасть в проигрышную, а проигрышные позиции – такие, из которых все ходы ведут в выигрышные.

В результате получим такую таблицу:

Отсюда мы видим, что позиция (20,10) – выигрышная и первому необходимо первым ходом брать спичку из первой коробки или по одной спичке из обеих.

<К условиям задач олимпиады | 2. Пять квадратов>