Условие
Клетчатая прямоугольная доска покрыта доминошками $1\times2$ в два слоя (каждая половинка доминошки расположена над одной клеткой доски).
Назовём доминошку верхнего слоя
особой, если её половинки лежат на двух доминошках разных направлений. Обязательно ли количество особых доминошек чётно?
Решение 1
Окрасим горизонтальные доминошки нижнего слоя в белый цвет, а вертикальные – в чёрный. Клетки доминошек верхнего слоя окрасим в цвета клеток под ними. Особые доминошки и только они будут двухцветными. Общее число белых клеток верхнего слоя чётно (их в два раза больше, чем горизонтальных доминошек в нижнем слое). Значит, и количество белых клеток на двухцветных доминошках чётно, а это и есть количество особых доминошек.
Решение 2
Заметим, что от любого разбиения доски на доминошки можно перейти к любому другому последовательностью замен такого вида (будем называть их флипами): находим две доминошки, образующие квадрат $2\times2$ и у обеих меняем направление (см., например, статью Е. Карпова и К. Кохася «Разбиения на домино и функции высоты» в « »Кванте» № 6 за 2010 год.). В случае, когда оба слоя, покрывающие доску, одинаковы, задача очевидна — особых доминошек нет, то есть их 0 — чётное число. Осталось проверить, что после любого флипа в нижнем слое количество особых доминошек не меняется. Заметим, что если доминошка целиком лежит на
рассматриваемом квадрате $2\times2$, то она неособая и останется таковой после флипа. Если же доминошка залезает на такой квадрат одной клеткой, то после флипа её статус меняется — особая становится неособой, и наоборот. Но таких залезающих доминошек либо четыре, либо две, либо ни одной, поэтому чётность числа особых доминошек при флипе не меняется.
Ответ
Обязательно.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Турнир городов |
|
год/номер |
|
Номер |
47 |
|
Дата |
2025/2026 |
|
вариант |
|
Вариант |
осенний тур, базовый вариант, 8-9 класс |
|
задача |
|
Номер |
3 |
