Закл (финал) 9 класс

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

Пусть и — хорошие пара и тройка элементов последовательности. Тогда НОД НОД

Доказательство проведём индукцией по наибольшему индексу среди и Если утверждение тривиально. Для перехода предположим, что Число лежит либо только в паре либо только в тройке либо в обеих.

Случай Пусть — только элемент пары; скажем, Тогда, поскольку число делится на то есть НОД НОД НОД по предположению индукции.

Случай Пусть — только элемент тройки; скажем, Аналогично, делится на так что НОД НОД по предположению индукции.

Случай Пусть — элемент и пары, и тройки; скажем, Тогда делится на так что НОД НОД НОД НОД по предположению индукции. Переход индукции доказан.