Разделы 
Дополнительно
Задача по математике - 2057
2019-01-23 
Клетчатый квадрат $100 \times 100$ разрезан на доминошки: прямоугольники $1 \times 2$. Двое играют в игру. Каждым ходом игрок склеивает две соседних по стороне клетки, между которыми был проведен разрез. Игрок проигрывает, если после его хода фигура получилась связной, т. е. весь квадрат можно поднять со стола, держа его за одну клетку. Кто выиграет при правильной игре - начинающий или его соперник?
Решение:
Приведем выигрышную стратегию для второго. Первыми несколькими ходами он склеивает каждую клетку, примыкающую к границе квадрата со всеми ее соседями. На это потребуется не более $8 \cdot 99$ ходов, т. е. после этого будет склеено всего $16 \cdot 99$ пар сторон и, как следствие, не более $2 \cdot 16 \cdot 99 < \frac{10000}{2}$ доминошек окажутся склеенными с чем-нибудь еще. Следовательно, после этого еще останутся отдельные доминошки, и фигура не будет связной. Далее второй будет действовать произвольным образом, следя только за тем, чтобы не проиграть прямо нынешним ходом.
Пусть в некоторый момент ему не удастся сделать этого. Тогда все доминошки распадаются на две связных фигуры, причем все несклеенные отрезки - это граница между этими фигурами, так как любой другой
отрезок можно склеить. При этом одна из этих фигур содержит все граничные клетки квадрата.
В границе внутренней фигуры четное число отрезков (если мы обойдем эту ломаную, то отрезков, по которым мы шли вверх и вниз, будет поровну; то же с отрезками вправо и влево). Подсчитаем изначальное число разрезанных сторон отрезков. Оно равно суммарному периметру всех доминошек, уменьшенному на периметр квадрата и деленному на 2 (так как каждый из остальных отрезков считался по два раза), т. е. $6 \cdot 5000 - 400$ - четному числу. Значит, к данному моменту склеено также четное число сторон, и ходить должен первый. Противоречие.
Ответ. Выигрывает игрок, делающий второй ход.
Клетчатый квадрат $100 \times 100$ разрезан на доминошки: прямоугольники $1 \times 2$. Двое играют в игру. Каждым ходом игрок склеивает две соседних по стороне клетки, между которыми был проведен разрез. Игрок проигрывает, если после его хода фигура получилась связной, т. е. весь квадрат можно поднять со стола, держа его за одну клетку. Кто выиграет при правильной игре - начинающий или его соперник?
Решение:
Приведем выигрышную стратегию для второго. Первыми несколькими ходами он склеивает каждую клетку, примыкающую к границе квадрата со всеми ее соседями. На это потребуется не более $8 \cdot 99$ ходов, т. е. после этого будет склеено всего $16 \cdot 99$ пар сторон и, как следствие, не более $2 \cdot 16 \cdot 99 < \frac{10000}{2}$ доминошек окажутся склеенными с чем-нибудь еще. Следовательно, после этого еще останутся отдельные доминошки, и фигура не будет связной. Далее второй будет действовать произвольным образом, следя только за тем, чтобы не проиграть прямо нынешним ходом.
Пусть в некоторый момент ему не удастся сделать этого. Тогда все доминошки распадаются на две связных фигуры, причем все несклеенные отрезки - это граница между этими фигурами, так как любой другой
отрезок можно склеить. При этом одна из этих фигур содержит все граничные клетки квадрата.
В границе внутренней фигуры четное число отрезков (если мы обойдем эту ломаную, то отрезков, по которым мы шли вверх и вниз, будет поровну; то же с отрезками вправо и влево). Подсчитаем изначальное число разрезанных сторон отрезков. Оно равно суммарному периметру всех доминошек, уменьшенному на периметр квадрата и деленному на 2 (так как каждый из остальных отрезков считался по два раза), т. е. $6 \cdot 5000 - 400$ - четному числу. Значит, к данному моменту склеено также четное число сторон, и ходить должен первый. Противоречие.
Ответ. Выигрывает игрок, делающий второй ход.
