Метод спуска, индукция и последовательное конструирование в ТЧ

Назовём множество положительных целых чисел хорошим, если ни один его элемент не является суммой двух других различных элементов Заметим, что если — три различных элемента хорошего множества причём то Иначе, поскольку мы имели бы

Докажем более сильное утверждение.

Пусть — хорошее множество из положительных целых чисел. Тогда элементы можно упорядочить в последовательность так, что и для всех

Назовём упорядочение крутым, если оно удовлетворяет требуемому свойству.

Будем вести доказательство индукцией по Базовый случай тривиален, так как ограничений на упорядочение нет.

Для шага индукции предположим, что Пусть и По предположению индукции найдём крутое упорядочение множества Покажем, что можно вставить в эту последовательность так, чтобы получить крутое упорядочение Иными словами, покажем, что существует для которого упорядочение

является крутым.

Предположим, что для некоторого упорядочение не является крутым, то есть некоторый элемент в нём делит либо сумму, либо разность двух соседних элементов. Поскольку в упорядочении такого не происходило, (если не существует, то аналогичное соглашение применяется и к Но случай невозможен: не может делить так как

и не может делить Следовательно, В этом случае сопоставим элементу индекс

Предположим теперь, что ни одно не является крутым. Поскольку имеется возможных индексов и лишь элементов в один из этих элементов (скажем, ) сопоставлен двум различным индексам, которые должны равняться и Это означает, что делит числа и для некоторых знаков Но тогда

и, следовательно,

что означает, что упорядочение не было крутым. Это противоречие завершает шаг индукции.