Олимпиадная задача по комбинаторной геометрии: разбивка доски 12×12 на уголки
Можно ли разбить клетчатую доску 12×12 на уголки из трёх соседних клеток так, чтобы каждый горизонтальный и каждый вертикальный ряд клеток доски пересекал одно и то же количество уголков? (Ряд пересекает уголок, если содержит хотя бы одну его клетку.)
Показать ответ
Нельзя.
Разобрать решение
Предположим, что такое разбиение нашлось. Рассмотрим первую и вторую снизу горизонтали доски; обозначим их H1 и H2. Каждый уголок на доске пересекается с двумя соседними горизонталями. Значит, если уголок пересекается с H1, то он пересекается и с H2. Теперь, если горизонталь H2 пересекает какой-то уголок, не пересекающийся с H1, то она пересекает больше уголков, чем H1, что невозможно. Итак, все уголки, пересекающиеся с первой или второй горизонталями, не выходят за их пределы и образуют вместе горизонтальную полосу H размера 2×12.
Аналогично все уголки, пересекающиеся с первой или второй слева вертикалями V1 и V2, образуют вместе вертикальную полосу V размера 12×2. В таком случае все уголки, пересекающиеся с левым нижним квадратом 2×2, должны лежать как в H, так и в V, то есть должны лежать в этом квадрате. Но тогда квадрат 2×2 должен разбиться на трёхклеточные уголки, что невозможно. Противоречие.
Обсуждение
0Комментариев пока нет.