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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

(a) Начертим граф возможных соседей. Рассмотрим три пары вершин в четырехугольниках на графе (они отмечены жирными точками), а именно: (2, 10), (1, 9) и (3, 11) — это вершины с наименьшей степенью (количеством соседей), равной 2.

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

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

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

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

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

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

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

Сначала покажем, что найдется игрок, одержавший не менее семи побед. Действительно, в противном случае общее число побед всех игроков было бы не более . Но общее число побед равно числу всех сыгранных партий, то есть равно — противоречие.

Выберем теннисиста, скажем, , одержавшего не менее 7 побед. Удалим (временно из рассмотрения) и семерых, проигравших ему. Останется группа из 6 теннисистов. Рассуждая аналогично, в этой группе найдем игрока , который выиграл не менее трёх партий у игроков из этой группы. Если убрать из рассмотрения и троих, проигравших ему, останутся два теннисиста. Из этих двоих выберем того, скажем, , кто победил другого. Тогда тройка игроков будет искомой по построению (первые семеро, удаленные из рассмотрения, проиграли , удаленная группа из троих проиграла , и последний проиграл ).