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

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

Условие

Двое играют на треугольной доске (см. рис.), закрашивая по очереди на ней треугольные клеточки. Одна клетка (начальная) уже закрашена перед началом игры.
Первым ходом закрашивается клеточка, граничащая (по стороне) с начальной, а каждым следующим ходом — клетка, граничащая с только что закрашенной. Повторно клетки красить нельзя. Тот, кто не может сделать ход, проигрывает. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр?
Рассмотрите случаи:
а) Начальная клетка — угловая, поле любого размера;
б) Поле и начальная клетка как на рисунке к этому заданию;
в) Общий случай: поле любого размера, и начальная клетка в нём произвольная.
г) Дополнительное задание. Можно подумать, что начальная клетка определяет исход партии независимо от действий игроков. Нарисуйте, однако, на каком-нибудь поле примеры таких двух партий с одной и той же начальной клеткой, чтобы в первой побеждал начинающий, а во второй — его партнёр. Для удобства нумеруйте клетки: начальная — 0, первым ходом красится клетка 1, вторым — 2 и т. д.



Решение

В пункте "а" побеждает второй игрок. После хода первого игрока (единственно возможного), ему следует закрасить клетку, примыкающую к стороне. Ход первого вынужден, второй снова красит клетку у стороны и в конце концов побеждает, крася угловую клетку.
Нетрудно понять, что в пункте "б", наоборот, победит первый игрок. Не приводя специально решения пункта "б", разберём общий случай.
в) То, кто будет победителем зависит от начальной клетки. Раскрасим клетки как на рисунке 1, в шахматном порядке, так, чтобы клетки вида Δ были белыми, а клетки вида  — чёрными.
Покажем, что если начальная клетка чёрная, начинающий побеждает. Разделим поле на "слои" (см. рис. 2). Начинающий должен всегда закрашивать клетку, оставаясь в текущем слое. При этом соперник либо тоже будет оставаться в этом слое (и тогда они вскоре доберутся до угла слоя), либо уйдёт во внешний слой. (Из угла он в любом случае уходит во внешний слой.) В конце концов первый игрок закрасит угловую клетку поля и победит.






Решение дополнительного задания показано на рисунках 3 и 4. Поле и начальная клетка взяты как в пункте "б". Согласно теории, победить должен первый игрок, что и проиллюстрировано рисунком 3. Последний, седьмой ход в угол делает первый игрок. Но если бы первый игрок играл "как попало", он мог бы и проиграть: на правом рисунке после 10-го хода второго первый терпит поражение.





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

олимпиада
Название Турнир им.Ломоносова
номер/год
Название конкурс по математическим играм
Год 2009
задача
Номер 2

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

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