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

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

Условие

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


Решение 1

  Пусть первый поставил на доску первую шашку. Заметим, что от перестановки горизонталей доски ничего не изменяется. То же относится и к перестановке вертикалей. Поэтому будем считать, что второму игроку дополнительно разрешается менять местами любые горизонтали и вертикали.
  После первого хода первого игрока второй игрок переставит горизонтали и вертикали так, чтобы первая шашка оказалась в средней вертикали, но не в центре доски.
Далее он делает ходы симметрично ходам первого игрока относительно центра доски. В частности, вторая шашка тоже окажется в средней вертикали, и первый не сможет занять центральную клетку. Легко проверить, что второй всегда сможет сделать симметричный ход (отдельно следует рассмотреть случай хода в среднюю горизонталь).


Решение 2

  Опишем эту игру по-другому. Есть два ряда по 65 точек в каждом (точки одного ряда обозначают горизонтали доски, точки другого – вертикали).
  Постановке шашки на пересечение горизонтали и вертикали соответствует проведение отрезка, соединяющего точки, которые обозначают эти горизонталь и вертикаль.
  Таким образом, правила запрещают проводить из одной точки больше двух отрезков.
  Второй игрок должен играть (за исключением последнего хода) так, чтобы после каждого его хода проведённые отрезки образовывали незамкнутую ломаную (возможно самопересекающуюся). Тогда после k-го хода второго игрока ломаная будет состоять из 2k звеньев и проходить через  2k + 1  точку (k точек одного ряда и  k + 1  – другого). Поэтому первые 64 хода второй игрок всегда сможет продолжить ломаную или соединить её с отдельным отрезком, проведённым первым на предыдущем ходе. Последним, 65-м ходом, второй игрок должен соединить отрезком начало и конец ломаной, превращая её в замкнутую ломаную, проходящую через все 130 точек. После этого первый игрок не сможет сделать ход.


Ответ

Второй.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 65
Год 2002
вариант
Класс 8
задача
Номер 4

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

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