Задача
№ 15449
НОД и НОК, алгоритм Евклида
Ур. 6
Всероссийская олимпиада школьников по математике, 11 класс, заключительный этап, 2025, задача 5; также: ВОШ 10 кл. ЗЭ 2025 №5
Дано натуральное число $n$. Натуральные числа $1, 2, \ldots, n$ выписывают на доске в строчку в некотором порядке. У каждых двух стоящих рядом чисел вычисляют их НОД (наибольший общий делитель) и записывают этот НОД на листке. Какое наибольшее количество различных чисел может быть среди всех $n-1$ выписанных на листке чисел?
Ответ:
Решение: