Всесиб 2022, 9 класс, задача 3
( баллов) Рассматриваются всевозможные разбиения шахматной доски на на домино из двух соседних по стороне клеток. Определить максимальное натуральное такое, что для любого разбиения доски на на домино можно найти некоторый прямоугольник, составленный из клеток доски, не содержащий ни одного домино целиком. Длины сторон прямоугольника в клетках могут равняться любым натуральным числам, начиная с единицы.
Ответ
Ответ. .
Решение. ) Докажем, что . Рассмотрим следующее разбиение шахматной доски на на домино. Разобьём доску на квадраты на клетки, окрасим каждый из них в красный и синий цвета в шахматном относительно доски на порядке и разобьём красные квадраты на пары горизонтальных домино, а синие - на пары вертикальных домино. Любой прямоугольник площади больше либо содержит в себе прямоугольник на клеток, либо прямоугольник на клетки. Легко убедиться в том, что для рассматриваемого разбиения прямоугольник на клеток либо на клетки в любом месте доски содержит целиком хотя бы одно домино.
) Докажем, что для произвольного разбиения доски на на домино можно найти некоторый прямоугольник площади , составленный из клеток, не содержащий ни одного домино целиком. Рассмотрим домино разбиения, содержащее клетку , можно, повернув при необходимости доску, считать его горизонтальным. Подробно разберём случай, когда оно состоит из клеток , ; второй случай, когда оно состоит из клеток , , аналогичен. Рассмотрим клетки , и , . Если хотя бы одна из этих клеток, скажем (остальные случаи аналогичны), лежит в горизонтальном домино разбиения, то вертикальный прямоугольник , , , не содержит целиком ни одного домино разбиения. Если все эти клетки лежат в вертикальных домино разбиения, то домино, содержащие и , вертикальны, поэтому прямоугольник , , , не содержит целиком ни одного домино разбиения. Заметим, что за счёт выбора клетки для начала рассуждений обеспечивается невозможность выхода выбираемой полоски на за пределы доски.