Индукция в комбинаторике

Пусть фигура где — точка плоскости. Обозначим за минимальное значение стороны квадрата иp точек, в котором точно найдётся фигура гомотетичная при раскраске в цветов.

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

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

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

______________________________________________________________________________________________________________________________________________________

Лемма. Пусть мы провели сжатие фигуры или образа(далее фигуры). Тогда, если до сжатия была фигура то фигура заданная множеством будет гомотетична

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

_________________________________________________________________________________________________________________________________________________________________________________

Построим конструкцию по индукции по числу сжатий. Далее верхний индекс - цвет фигуры. База строим фигуру из точки, — конечная. Переход: пусть проведено сжатие и точка — конечная для фигур

Из построения будет видно, что точка ого цвета после ого сжатия единственная.

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