Комбинаторика на БИБНе

Рассмотрим в нашем квадрате квадратов

Назовём их выделенными.

Заметим, что если одна клетка некоторого диполя принадлежит какому-то выделенному квадрату, то другая клетка этого диполя принадлежит (соседнему) выделенному квадрату.

На рисунке отмечены номерами клетки в выделенных квадратах, так что у любого диполя обе клетки должны иметь один и тот же номер. Но клеток с данным номером (например, с номером ) девять, и поэтому при “распределении” клеток с номером по диполям по меньшей мере одна клетка окажется нераспределённой (лишней). Таким образом, для каждого из четырех номеров остаётся нераспределённой минимум одна клетка среди выделенных квадратов, а значит, всего имеется минимум нераспределенные клетки.

Получаем оценку: максимальное число непересекающихся диполей во всём квадрате не больше

Построим теперь пример на диполей. Для этого “отрежем” левый нижний выделенный квадрат. Останется клетчатая фигура из клеток, которая разбивается на квадрат и два прямоугольника и Эта фигура полностью разбивается на диполи, поскольку любые последовательные клеток строки или столбца, очевидно, разбиваются на три диполя.

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

Таким образом, приходим к такой задаче: на числовой прямой есть попарно пересекающиеся отрезки и требуется доказать, что у них имеется общая точка. Опытные олимпиадники могут сразу сослаться на теорему Хелли. Мы же приведём её доказательство, чтобы не оставлять у неопытных читателей чувство неловкости.

Пусть – наибольшее значение среди левых концов отрезков, т.е. и аналогично, пусть — наименьшее значение среди правых концов отрезков. Тогда так как в противном случае для некоторых и а значит, -ый и -ый отрезки не пересекаются. Отсюда следует, что любая точка отрезка будет общей для всех наших отрезков. Итак, пусть точка принадлежит проекциям на ось Ох всех параллелепипедов. Точно так же мы можем найти общие точки и проекций на оси Oy и Oz. Тогда точка с координатами будет принадлежать всем параллелепипедам.

(a) Начертим граф возможных соседей. Рассмотрим три пары вершин в четырехугольниках на графе (они отмечены жирными точками), а именно: (2, 10), (1, 9) и (3, 11) – это вершины с наименьшей степенью (количеством соседей), равной 2. Предположим, от противного, что есть простой путь на графе (т.е. без повторения вершин), проходящий через все вершины. Тогда найдется такая пара вершин среди трех указанных пар, что путь не начинается и не кончается в вершинах из этой пары (такая пара есть, т.к. концов у пути – два, а пар – три). Таким образом, обе вершины этой пары – “проходны”, но если впервые будет пройдена одна вершина из этой пары, то вторая вершина станет изолированной («отрезанной»: в неё нельзя будет попасть потом). Противоречие.

(b) Пример перестановки: 2, 5, 10, 7, 12, 9, 4, 1, 6, 3, 8, 11. Граф (см. рисунок) помогает построить подобный пример.

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

Рассмотрим сначала случай, когда и не взаимно просты. Тогда НОД( В этом случае рассмотрим на стороне промежуточные точки где Проведём через точки прямые, параллельные стороне Они пересекут сторону в точках где

Таким образом, точки и имеют целочисленные координаты и тем самым, прямые разбивают прямоугольник на прямоугольников с целочисленными вершинами. Назовем это разбиением первого типа.

Аналогично, если и не взаимно просты, то прямыми, параллельными стороне разобьем на меньшие прямоугольники с целочисленными вершинами. Назовем это разбиением второго типа; прямые этого разбиения проходят через промежуточные точки на стороне где а — наибольший общий делитель и Заметим, что в случае, когда одновременно и прямые первого и второго разбиений разбивают прямоугольник на равных прямоугольников с вершинами в точках где т.е. все вершины имеют целочисленные координаты.

Итак, приходим к случаю, когда координаты каждого из векторов взаимно просты. Но тогда из равенства получим, что (действительно, из этого равенства следует, что делится на и, в то же время, делится на значит, аналогично, с учетом знака в данном равенстве). В этом случае стороны прямоугольника равны: и наш прямоугольник квадрат.