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

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

База для и очевидна. Докажем переход от к Рассмотрим число Пусть рядом с ним стоят числа и Тогда сумма делится на но меньше так как и меньше Значит, Выкинув число из круга, получим расстановку, удовлетворяющую условию (для всех чисел, кроме и условия не сломались, а суммы соседних чисел у и уменьшились на и соответственно, а значит, делимости сохранились).

Если — нечётное, то после выкидывания числа по предположению индукции числа должны быть выписаны подряд от 1 до но тогда можно вставить только между двумя числами, дающими в сумме то есть между 1 и или между и Итого, два способа, переход доказан.

Если же — чётное, то после выкидывания числа по предположению индукции числа должны быть или выписаны подряд от 1 до тогда можно вставить только между 1 и или выписаны подряд числа от 1 до но между и стоит число Во втором случае число некуда вставить, так как суммы соседних чисел никак не могут равняться при Итого, один способ, переход доказан.