Задача 30439

Тема:    [ Игры-шутки ]

Сложность: 3 Классы: 7,8,9

Условие

Дана клетчатая доска размерами

а) 9 × 10;     б) 10 × 12;     в) 9 × 11.

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

Решение

Эта игра - не совсем шутка. В ней выигрывающий, допустив ошибку, может проиграть. Эта ошибка состоит в том, что он после своего хода оставляет невычеркнутые клетки только в одном столбце или только в одной строке, предоставляя противнику возможность выиграть в один ход. Проигравшим в этой игре является, тем самым, тот, кто сделает этот роковой ход. Заметим, что оставшуюся после вычеркивания горизонтали часть клетчатой доски m × n можно представить себе как доску (m - 1) × n. Аналогично, после вычеркивания вертикали остается доска m × (n - 1). Ситуация, в которой каждый ход является "роковым", только одна - это доска 2 × 2. Таким образом, выигрывает игрок, после хода которого она возникла. Однако, как мы видели, при каждом ходе суммарное количество горизонталей и вертикалей на доске уменьшается на 1. Поэтому четность этой суммы в начале игры определяет победителя. В пункте а) выигрывает первый игрок, а в пунктах б) и в) - второй. Заметим, что в пункте б) решающим соображением может быть и симметричная стратегия второго игрока.

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

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	8
Название	Игры
Тема	Теория игр
задача
Номер	007