ВсОШ 2023, 10 класс, задача 6
( баллов) Квадрат разбит на квадраты . Потом его разбивают на доминошки (прямоугольники и ). Какое наименьшее количество доминошек могло оказаться внутри квадратов разбиения? (С. Берлов)
Ответ. .
Решение. Пример. Верхнюю и нижнюю горизонтали разобьём на горизонтальные доминошки - они окажутся в квадратах . Остальной прямоугольник разобьём на вертикальные доминошки - они не окажутся в квадратах .
Оценка. Рассмотрим квадраты размеров , у которых левый нижний угол совпадает с левым нижним углом исходного квадрата . Для каждого из квадратов () найдётся доминошка , пересекающая его сторону (поскольку квадраты нечётной площади не разбиваются на доминошки). Легко видеть, что лежит внутри квадратика из разбиения.
Аналогично, рассматривая квадраты размеров , у которых правый верхний угол совпадает с правым верхним углом исходного квадрата , находим ещё нужных нам доминошек (). Это завершает решение (очевидно, что все доминошки различны).
Замечание. Приведем схему несколько другого доказательства оценки.
Пусть внутри квадратов оказалось не более доминошек.
Проведём вертикальных линий сетки так, что отделяет столбцов слева. Легко видеть, что любая доминошка, пересекаемая одной из линий , нам подходит. Каждая вертикальная линия пересекает чётное количество доминошек, так как слева от этой линии чётное количество клеток. Значит, среди линий есть линия , не пересекающая доминошек, иначе мы уже нашли хотя бы нужных нам доминошек. Проведём аналогичное рассуждение для горизонтальных линий сетки и найдём среди них линию , не пересекающую доминошек. Но и делят доску на области с нечётным количеством клеток, поэтому хотя бы одна из этих двух линий обязана пересекать доминошку. Противоречие.