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

Проект МЦНМО
при участии
школы 57
Задача 109856
Темы:    [ Замощения костями домино и плитками ]
[ Геометрия на клетчатой бумаге ]
[ Связность. Связные множества ]
[ Теория игр (прочее) ]
[ Четность и нечетность ]
Сложность: 4+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Клетчатый квадрат 100×100 разрезан на доминошки. Двое играют в игру. Каждым ходом игрок склеивает две соседних по стороне клетки, между которыми был проведён разрез. Игрок проигрывает, если после его хода фигура получилась связной, то есть весь квадрат можно поднять со стола, держа его за одну клетку. Кто выиграет при правильной игре – начинающий или его соперник?


Решение

  Приведём выигрышную стратегию для второго игрока. Первыми несколькими ходами он склеивает каждую клетку, примыкающую к границе квадрата со всеми её соседями. На это потребуется не более 8·99 ходов, то есть после этого будет склеено всего 16·99 пар сторон и, как следствие, не более
2·16·99 < 5000  доминошек окажутся склеенными с чем-нибудь ещё. Следовательно, после этого ещё останутся отдельные доминошки, и фигура не будет связной.
  Далее второй будет действовать произвольным образом, следя только за тем, чтобы не проиграть очередным ходом.
  Пусть в некоторый момент ему не удастся сделать этого. Тогда все доминошки распадаются на две связных фигуры, причём все несклеенные отрезки – это граница между этими фигурами, так как любой другой отрезок можно склеить. При этом одна из этих фигур содержит все граничные клетки квадрата.
  Граница внутренней фигуры содержит чётное число отрезков (см. задачу 30932). Подсчитаем изначальное число разрезанных сторон отрезков. Оно равно суммарному периметру всех доминошек, уменьшенному на периметр квадрата и делённому на 2 (так как каждый из остальных отрезков считался по два раза), то есть  (6·5000 – 400) : 2  – чётному числу. Значит, к данному моменту склеено также чётное число сторон, и ходить должен первый. Противоречие.


Ответ

Соперник.

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

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

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

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