Решение задачи 435

Условие:

Можно ли замостить доску 12x12 уголками из трех клеток так, чтобы любой вертикальный столбец и любая горизонтальная строка пересекали одинаковое число уголков?

Решение:

Давайте посмотрим на самую верхнюю строку (назовем ее первой) и на строку, находящуюся под ней (назовем ее второй). Легко понять, что любой уголок, который пересекается первой строкой пересекается также и второй (синий уголок на рисунке снизу). Значит в разбиении не может быть уголка, который пересекается второй строкой и при этом не пересекается первой (красный уголок на рисунке снизу), т.к. в этом случае вторая строка будет пересекать больше уголков, чем первая.

Выходит, что прямоугольник, состоящий из двух верхних строк должен быть заполнен уголками, которые полностью находятся внутри этого прямоугольника.

Совершенно аналогичные рассуждения можно провести и для крайнего правого столбца доски и соседнего с ним.

Осталось заметить, что по такой логике, квадрат (фиолетовый квадрат на рисунке снизу), находящийся в пересецении двух первых строк и двух правых столбцов должен быть заполнен уголками, не выходящими за пределы этого квадрата. Что, очевдно, невозможно.

Полученное противоречие доказывает невозможность такого разбиения.

Ответ: нет, нельзя.

Источник: всероссийская олимпиада по математике, региональный этап.