Условия про НОД и НОК

Пример. Возьмём числа и расставим их в следующем порядке:

Тогда НОДы будут

Оценка. Здесь и далее — это НОД Прежде всего отметим, что:

То есть НОД двух соседних чисел не превосходит модуля их разности. Но модуль разности любых двух из последовательных натуральных чисел принимает значения от до Всего Петя получит как раз пару соседних чисел. Значит, в качестве НОДов должны встретиться все числа от до по одному разу.

Докажем, что четные числа могут стоять только подряд.

1.

Пусть четно: Тогда произвольная пара чисел отличается на величину от до то есть всего четных разностей а самих четных чисел — Значит они должны стоять подряд.

2.

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

Заметим, что НОД двух различных нечётных чисел не больше половины от их разности, поскольку разность чётная делит НОД, при этом сам НОД нечётный.

Теперь снова рассмотрим случаи в зависимости от чётности

1.

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

2.

Без ограничения общности будем считать чётным. Рядом с должно стоять чтобы получить НОД Аналогично, другим крайним элементом последовательности чётных будет или в зависимости от чётности Тогда снова попробуем получить НОД Для двух нечётных он снова не более С крайним чётным числом разность не более ведь максимальное нечётное уже занято с другой стороны, а наименьшее нечётное Для получаем противоречие.