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