ВсОШ 2026, 11 класс, задача 8

Ответ: .

Решение 1. Все рисунки в решении иллюстрируют сказанное при , .

Сперва докажем, что заявленное в ответе значение (обозначим его через ) удовлетворяет условию. В каждой салфетке правую верхнюю клетку назовём базовой. Непокрытую клетку назовём дыркой.

Рассмотрим произвольную салфетку; введём систему координат (пронумеруем строки и столбцы) так, что её базовая клетка имеет координаты . Согласно условию задачи, при параллельном переносе на вектор конфигурация переходит в себя. Тогда клетка покрыта нижней левой клеткой -образа этой салфетки.

Рассмотрим прямоугольник с левой нижней клеткой и правой верхней клеткой . Раскрасим его клетки в шахматном порядке так, чтобы все угловые клетки были черными (это возможно, поскольку и нечётны); чёрных клеток окажется на одну больше, чем белых. Нетрудно видеть, что каждая салфетка покрывает в не меньше чёрных клеток, чем белых. При этом рассмотренная выше салфетка и её образ покрывают больше чёрных клеток, чем белых. Поскольку каждая клетка покрыта не более чем по одному разу, какая-то белая клетка в этом прямоугольнике — дырка. Сопоставим одну из таких дырок рассмотренной салфетке.

Выясним, скольким салфеткам может быть сопоставлена одна и та же дырка. Введём координаты иначе, чтобы у дырки они были . Тогда базовые клетки салфеток, которым она соответствует — по-прежнему белые клетки прямоугольника (в новых координатах). При этом все эти белые клетки, кроме верхних клеток левого столбца, можно разбить на пары соседних по диагонали (левая верхняя–правая нижняя); из каждой такой пары не более чем одна клетка может быть базовой. Таким образом, базовых клеток (и, тем самым, сопоставленных салфеток) не больше, чем

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

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

Итого

Воспользуемся тем, что (напомним, что ), и перейдём к пределу в неравенстве — получится, что . Значит, действительно для любого найдётся квадрат , в котором покрыто не более, чем клеток.

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

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

Эта оценка должна выполняться при каждом натуральном . Переходя к пределу при в правом неравенстве, мы получаем, что

что и требовалось доказать.

Решение 2. Приведём другое доказательство того, что удовлетворяет требованиям. Мы будем пользоваться терминологией из первого решения. Введём систему координат на плоскости.

Рассмотрим фигуру , содержащую при каждом столбец от клетки до клетки , а также столбец клеток от до ; всего эта фигура содержит клеток.

Лемма. Любой параллельный перенос этой фигуры (на вектор с целыми координатами) содержит дырку.

Доказательство. Ясно, что достаточно доказать утверждение леммы для исходной фигуры .

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

Предположим, что имеет ту же чётность, что и (а тогда и имеют ту же чётность, что и ). Пусть — верхняя клетка в ; тогда он содержит и клетку , а тогда содержит клетку . Кроме того, содержит клетки и . Заметим, что числа и имеют одинаковую чётность. Мы докажем, что строка между клетками и содержит дырку. Это даст требуемое противоречие, ибо эта строка полностью содержится в объединении столбцов .

Действительно, чётность салфетки, накрывающей , совпадает с чётностью числа , то есть ордината её базовой клетки равна . Тогда её абсцисса равна , иначе она бы накрывала , то есть задевала бы и , и . Таким образом, левые две клетки в накрыты одной салфеткой. Аналогично, базовая клетка салфетки, накрывающей , имеет координаты , то есть она накрывает и клетку под . Значит, её не накрывает салфетка, накрывающая , то есть эта салфетка имеет базовую клетку . Поэтому и является базовой клеткой некоторой салфетки, накрывающей правые две клетки в . Но тогда строка , состоящая из нечётного числа клеток, не может быть полностью покрыта салфетками.

Если имеет ту же чётность, что и (а — ту же чётность, что и ), рассуждения аналогичны. Вводя те же клетки, мы получаем, что базовая клетка салфетки, покрывающей , имеет координаты , поэтому базовая клетка салфетки, покрывающей , имеет координаты , и эта салфетка покрывает левые две клетки строки . С другой стороны, базовая клетка салфетки, покрывающей , имеет координаты , а тогда её перенос на накрывает правые две клетки в . Лемма доказана.

Теперь несложно завершить оценку. Заметим, что вся плоскость разбивается на сдвиги фигуры на векторы, кратные и . Рассмотрим любой квадрат . Каждая его клетка, отстоящая от границы квадрата хотя бы на , покрыта одним из этих сдвигов, целиком содержащимся в квадрате. Значит, сдвигов из разбиения, целиком содержащихся в квадрате, не меньше, чем , и каждый содержит дырку. Поэтому количество салфеток, полностью содержащихся в квадрате, не превосходит

Теперь для любого натурального выберем наименьшее такое, что некоторый квадрат содержит салфеток. Тогда в любом квадрате при содержится не менее салфеток, то есть

Переходя к пределу при , получаем .