ВсОШ 2025, 11 класс, задача 5
Дано натуральное число . Натуральные числа , , ..., выписывают на доске в строчку в некотором порядке. У каждых двух стоящих рядом чисел вычисляют их НОД (наибольший общий делитель) и записывают этот НОД на листке. Какое наибольшее количество различных чисел может быть среди всех выписанных на листке чисел?
Ответ. .
Решение.
Оценка. Предположим, что какое-то из выписанных на листке чисел больше , скажем, . Тогда наибольшее из чисел , не меньше , что больше — противоречие. Значит, каждый из написанных НОДов не превосходит , потому количество различных НОДов не может превышать .
Пример. Разобьём все числа от до на цепочки вида , , , , ..., , где — нечётное число, не превосходящее . Выпишем в строчку цепочки одну за другой. Тогда для любого натурального найдётся цепочка, в которой встречается , а следующее за число будет . Видим, что каждое натуральное будет выписано на листке.