|
|
 |
Условие
Даны натуральные числа a и b, причём a < b < 2a. На клетчатой плоскости отмечены некоторые клетки так, что в каждом клетчатом прямоугольнике a×b или b×a есть хотя бы одна отмеченная клетка. При каком наибольшем α можно утверждать, что для любого натурального N найдётся клетчатый квадрат N×N, в котором отмечено хотя бы αN² клеток?
Решение
Введём на плоскости систему координат так, чтобы центры клеток, и только они, имели целые координаты. Будем говорить, что клетка имеет те же координаты, что и её центр. Назовём прямоугольник a×b вертикальным или горизонтальным, если его сторона длины b вертикальна или горизонтальна, соответственно.
1. Положим D = a² + (b – a)² = 2a² – 2ab + b². Отметим на плоскости клетку (0, 0) и все клетки, полученные из неё сдвигами на целые кратные векторов (a, b – a) и (b – a, – a); на рисунке слева приведён пример такой разметки при a = 3, b = 5. Центры этих клеток находятся в вершинах квадратной сетки со стороной при этом клетки (D, 0) = (a² + (b – a)², (b – a)a – a(b – a)) и (0, D) отмечены. Значит, при горизонтальном или вертикальном сдвиге на D отмеченная клетка переходит в отмеченную. Отсюда нетрудно получить, что в каждом квадрате D×D ровно D отмеченных клеток.
Покажем, что такая разметка удовлетворяет условию; отсюда будет следовать, что α ≤ D : D² = 1/D. Действительно, рассмотрим любую полосу из b
последовательных горизонталей. Ясно, что в ней есть хотя бы одна отмеченная клетка. Если (x, y) – координаты любой отмеченной клетки в ней, то одна из двух клеток (x + a, y + (b – a)) или (x + (b – a), y – a) также находится в этой полосе и смещена относительно предыдущей не более, чем на a вправо. Значит, в любых a вертикалях нашей полосы найдётся отмеченная клетка.
Доказательство для горизонтальных прямоугольников аналогично.
2. Осталось показать, что α = 1/D подходит. Рассмотрим произвольную разметку, удовлетворяющую условию. Каждому вертикальному прямоугольнику сопоставим любую из самых верхних отмеченных в нём клеток. Оценим, какому количеству прямоугольников может быть сопоставлена одна отмеченная клетка A; пусть её координаты (0, 0). Её содержат ab вертикальных прямоугольников.
Рассмотрим горизонтальную полосу из клеток, ординаты которых не меньше 1 и не больше a. Пусть B – отмеченная клетка в этой полосе с наименьшей неотрицательной абсциссой, а C – отмеченная клетка в этой полосе с наибольшей отрицательной абсциссой (рис. справа). Тогда между B и C расположено не более b – 1 вертикали, в противном случае в нашей полосе между этими клетками нашёлся бы горизонтальный прямоугольник без отмеченных клеток.
Рассмотрим теперь все a(b – a) вертикальных прямоугольников, содержащих A и пересекающих хотя бы a горизонталей сверху от A. Каждый из них содержит B или C, за исключением тех, которые расположены строго между B и C; таковых по доказанному выше не более (b – a)2. Значит, хотя бы a(b – a) –
(b – a)² = (2a – b)(b – a) прямоугольников, содержащих A, содержат также B или C, и A им не сопоставлена. Итого, клетка A сопоставлена не более чем ab – (2a – b)(b – a) = D вертикальным прямоугольникам.
Пусть теперь N – произвольное число. Положим K = (a + b)N² и рассмотрим произвольный квадрат K×K; пусть в нём s отмеченных клеток. В этом квадрате расположено не меньше (K – a)(K – b) вертикальных прямоугольников; каждому из них сопоставлена одна из s отмеченных клеток. По доказанному, получаем
Разделив наш квадрат K×K на (a + b)²N² квадратов размера N×N, получаем, что в одном из них больше чем отмеченных клеток; значит, их не меньше чем
что и требовалось.
Ответ
