Отзывы пользователей

гдз

Олимпиадная задача по математике из коллекции задач Московской Математической Олимпиады на темы: Шахматные доски и шахматные фигуры, Выигрышные и проигрышные позиции.

Условие

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

Решение

  Случай m = n = 1 очевиден (первому некуда ходить). Для определенности будем считать, что доска состоит из m вертикалей и n горизонталей, причем mn, а ладья, вначале, стоит в левом верхнем углу.

Оказывается, первому достаточно все время делать наиболее длинные ходы. Докажем правильность этой стратегии от противного. Рассмотрим среди досок, для которых эта стратегия не приводит к выигрышу, доску наименьшей площади. Для доски 1×n утверждение очевидно, поэтому будем считать, что mn2.

Первый ходит по длинной стороне (горизонтали) до конца. Второй вынужден сделать ход в перпендикулярном направлении. Рассмотрим 3 случая:

а) Второй пошел на одну клетку. Тогда первый пойдет по горизонтали до конца, и игра сводится к аналогичной для доски m×(n - 1) (рис., a). Заметим, что m2, поэтому доска 1×1 не получится.

б) Второй пошел до конца. Тогда первый пойдет по горизонтали до конца. Если m = n = 2, то первый сразу выигрывает. В противном случае игра будет происходить так же, как если бы первый начал игру на доске (m - 1)×(n - 1) (рис. б).

в) Пусть второй пошел на k клеток, k1, kn - 1. Тогда m3. Первый пойдет до конца по горизонтали. Если второй после этого пойдет вверх, то вся дальнейшая игра будет происходить, как на доске (m - 1)×k. Доска 1×1 не получится, так как (m - 1)2 (рис., в).

Если второй пойдет вниз, то вся дальнейшая игра будет происходить, как на доске m×(n - k).

В любом случае игра будет идти, как если бы она началась ходом позже на меньшей доске, отличной от 1×1. Но, по предположению, на этой доске стратегия верна. Значит, она верна и на исходной доске. Мы пришли к противоречию.

 
Поделиться: