ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109557
Темы:    [ Шахматные доски и шахматные фигуры ]
[ Симметричная стратегия ]
[ Шахматная раскраска ]
[ Доказательство от противного ]
Сложность: 5
Классы: 7,8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Перлин А.

Игроки A и B по очереди ходят конем на шахматной доске 1994×1994. Игрок A может делать только горизонтальные ходы, то есть такие, при которых конь перемещается на соседнюю горизонталь. Игроку B разрешены только вертикальные ходы, при которых конь перемещается на соседнюю вертикаль. Игрок A ставит коня на поле, с которого начинается игра, и делает первый ход. При этом каждому игроку запрещено ставить коня на то поле, на котором он уже побывал в данной игре. Проигравшим считается игрок, которому некуда ходить. Докажите, что для игрока A существует выигрышная стратегия.


Решение

Так как игра заканчивается не более, чем через 1994² ходов, то один из двух игроков обязательно имеет выигрышную стратегию. Если у игрока A нет выигрышной стратегии, то игрок B, правильно играя, выигрывает при любом первом ходе игрока A. Докажем, что это невозможно. Для этого организуем две игры на двух досках (на второй доске A будет делать только вертикальные ходы, а B – только горизонтальные; заметим, что если повернуть доску на 90°, то игра происходит в точности по правилам условия задачи). На первой доске A делает произвольный первый ход с поля x на поле y. На второй доске A ставит коня на поле y и ждёт ответного хода B на первой доске. После чего в точности повторяет ход B на второй доске в качестве своего хода. Далее игрок B делает горизонтальный ход на второй доске, который повторяется игроком A на первой доске в качестве своего хода, и т.д. Заметим, что игрок B не может на второй доске попасть на поле x, так как B всегда ходит на поле цвета, отличного от цвета x. В этой двойной игре A всегда имеет возможность сделать очередной ход, если B имеет такую возможность. Поэтому на одной из двух досок проиграет B вопреки предположению, что у него есть выигрышная стратегия.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1994
Этап
Вариант 5
класс
Класс 11
задача
Номер 94.5.11.8

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .