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

Пример. Отметим в третьей, шестой, девятой, , 48 строках все клетки в столбцах, номера которых не дают остаток 1 при делении на 3. Тогда в каждой из этих 16 строк отмечено по 33 клетки — всего клеток.

Оценка. Докажем методом математической индукции, что на доске меньше клеток отметить нельзя. База для очевидна.

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