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

Мы будем доказывать более сильное утверждение, что для любых и существует такое натуральное что при любой раскраске чисел в цветов найдется одноцветная арифметическая прогрессия длины Докажем индукцией по что для любого существует число База для верна: достаточно взять Предположим, что существует для всех докажем для Зафиксируем Предположим, что требуемой прогрессии не существует. Будем строить последовательность фигур Определим как любую арифметическую прогрессию из точек. Разобьем наши натуральные числа на блоки по Цвет каждого блока определяется цветом его вершин. То есть всего различных цветов блоков не более Тогда по предположению индукции найдутся блоков, образующих арифметическую прогрессию, покрашенные одинаково. Причем в каждом блоке на одном и том же месте найдется одноцветная фигура Заметим, что точки, лежащее левее каждой и дополняющие до арифметический прогрессий уже не могут быть покрашены в тот же цвет (пусть первый, иначе мы уже найдем нужную арифметическую прогрессию). Тогда назовем такое множество фигур фигурой Причем мы поняли, что для достаточно большого отрезка найдется одноцветная фигура типа Аналогично разбив натуральные числа на блоки соответствующей длины, найдем одноцветную арифметическую прогрессию из чисел. И определим как такое множество одноцветных фигур То есть является арифметической прогрессией из фигур Тогда рассмотрим одноцветную фигуру которую мы находим по алгоритму, описанному ранее. Рассмотрим все одноцветные фигуры из нашей фигуры. Заметим, что для каждой такой прогрессии точки, лежащие левее и дополняющие ее до арифметической прогрессии длины покрашены в один цвет, причем не в цвет фигур Основная мысль состоит в том, что такие точки образую фигуру типа Тогда опять смотрим на дополнения прогрессий, они образуют фигуру типа причем они не могут быть покрашены ни в цвет ни в цвет и так далее. В конце мы придем к точке, которая не может быть покрашена ни в один из цветов — противоречие.