Задача 107812

Темы:    [ Шахматные доски и шахматные фигуры ] [ Теория игр (прочее) ] [ Доказательство от противного ] [ Принцип крайнего (прочее) ]

Сложность: 4 Классы: 8,9,10

Условие

Автор: Бегун Б.И.

В углу шахматной доски размером m×n полей стоит ладья. Двое по очереди передвигают её по вертикали или по горизонтали на любое число полей; при этом не разрешается, чтобы ладья стала на поле или прошла через поле, на котором она уже побывала (или через которое уже проходила). Проигрывает тот, кому некуда ходить. Кто из играющих может обеспечить себе победу: начинающий или его партнер, и как ему следует играть?

Решение

  Случай  m = n = 1  очевиден (первому некуда ходить).
  Далее будем считать, что  m ≤ n,  n > 1,  а ладья вначале стоит в левом верхнем углу.
  Оказывается, первому достаточно все время делать наиболее длинные ходы. Докажем правильность этой стратегии от противного. Предположим, что существует доска, на которой эта стратегия не приводит к выигрышу, и рассмотрим среди них доску m×n наименьшей площади. Очевидно,  m > 1.
  Первый ходит по длинной стороне (горизонтали) до конца. Второй вынужден сделать ход в перпендикулярном направлении. Рассмотрим три случая.
  1) Второй пошёл на одну клетку. Тогда игра сводится к аналогичной для доски  (m–1)×n  (рис. слева). Поскольку  m ≥ 2,  доска 1×1 не получится.

  2) Второй пошёл до конца. Если  m = n = 2,  то первый сразу выигрывает. В противном случае игра будет происходить так же, как если бы первый начал игру на доске  (m–1)×(n–1)  (рис. в центре).
  3) Второй пошёл на k клеток,  1 < k < m – 1.  Тогда  m ≥ 3.  Первый пойдёт до конца по горизонтали. Если второй после этого пойдет вверх, то вся дальнейшая игра будет происходить, как на доске  k×(m–1),  где уже сделано два первых хода. Доска 1×1 не получится, так как  n – 1 ≥ 2  (рис. справа).
  Если второй пойдет вниз, то вся дальнейшая игра будет происходить, как на доске  (m–k)×n,  где уже сделано два первых хода.
  В любом случае игра будет идти, как если бы она началась двумя ходами позже на меньшей доске, отличной от 1×1. Но на этой доске стратегия верна. Значит, она верна и на исходной доске. Противоречие.

Ответ

Начинающий (на всех досках, кроме 1×1).

Замечания

1. 5 баллов.

2. В Задачнике "Кванта" игра велась на квадратной доске.

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

журнал
Название	"Квант"
год
Год	1996
выпуск
Номер	4
Задача
Номер	М1558
олимпиада
Название	Турнир городов
Турнир
Дата	1995/1996
Номер	17
вариант
Вариант	весенний тур, основной вариант, 8-9 класс
Задача
Номер	4
олимпиада
Название	Московская математическая олимпиада
год
Номер	59
Год	1996
вариант
Класс	10
задача
Номер	4