Анализ позиций

Решение 1. Проанализируем выигрышные и проигрышные позиции. Понятно, что все числа от 1 до 10 — выигрышные.

Число 11 — проигрышное, так как из нее можно попасть только в выигрышные позиции 1–10. Позиции 12–21 — выигрышные, ведь из них можно попасть в 11. Число 22 — проигрышное, и так далее.

Легко видеть, что все позиции, кратные 11, являются проигрышными, а остальные — выигрышными.

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

Еще раз хочется обратить внимание на то, как мы определяем, является ли позиция выигрышной или проигрышной: для того, чтобы позиция была выигрышной, достаточно ОДНОГО хода, ведущего в проигрышную позиция, а вот чтобы позиция была проигрышной, ВСЕ ходы должны вести в выигрышные. И во время решения мы ровно это и определяем.

Другой подход — дополнение хода соперника до определенного значения.

Решение 2. При количестве спичек, кратном 11, будем играть за второго игрока, дополняя количество спичек, взятых на предыдущем ходу первым игроком, до 11. Другими словами, если первый игрок только что взял спичек, то мы берем . Сразу отметим, что количество спичек, которое мы должны брать в ответ на ход первого, также от 1 до 10, то есть с этим проблем не возникает. Кроме того, после нашего хода количество спичек после пары ходов — соперника и нашего — кратно 11, поэтому последнюю спичку заберет именно второй игрок.

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