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

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

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

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

База индукции верна, поскольку после первого хода доска имеет вид прямоугольника причем следующих ход будет совершен Сергеем в нижнюю левую клетку.

Докажем переход. Пусть после некоторого хода Федора доска имеет вид причем Сергей совершит ход в одну из угловых клеток и делает несколько ходов по горизонтали, после чего из этой клетки Федор вновь совершает максимальное количество ходов по вертикали. После этого хода Сергей может сделать ход либо вправо, либо влево. Если в каждой из этих случаев доска будет иметь вид то Федор сделает последний ход и победит. Иначе одном из случаев доска будет иметь вид прямоугольника в другом причем если и а значит и что доказывает переход

Заметим, что каждая пара ходов Федора и Сергея уменьшает сумму количества столбцов и строк доски по крайней мере на 1, а значит, не позже, чем через ходов, доска придет к виду где Следующим ходом Сергей встанет на самую верхнюю или нижнюю клетку доски, после чего Федор пройдется по всем оставшемся ее клеткам и завершит игру.