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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. На клетчатой плоскости закрашено клеток. Тогда есть не более квадратов содержащих хотя бы две отмеченные клетки.

Доказательство. Докажем лемму индукцией по числу строк, которые занимают отмеченные клетки.

База. Все клеток в одной строке. Если они стоят подряд, то есть в точности квадратов. А если не подряд, то ещё меньше.

Переход. Пусть строк хотя бы Рассмотрим самую верхнюю, разобъем её на блоки подряд идущих клеток. Если в блоке клеток закрашено, то есть не более квадрата содержащих две закрашенные клетки этого блока и лежащих в рассматриваемой строке и строке на выше. И есть не более квадрата, лежащих в рассматриваемой строке и строке ниже. Итого, не более квадратов, которые добавляет блок размера поэтому можно сделать индукционный переход.

_________________________________________________________________________________________________________________________________________________________________________________

Предположим, что цветов не менее Тогда по лемме есть не более квадратов содержащих две отмеченные клетки одного из цветов. Но всего в квадрате есть квадрат Противоречие.