ВсОШ 2025, 11 класс, задача 5

Дано натуральное число . Натуральные числа , , ..., выписывают на доске в строчку в некотором порядке. У каждых двух стоящих рядом чисел вычисляют их НОД (наибольший общий делитель) и записывают этот НОД на листке. Какое наибольшее количество различных чисел может быть среди всех выписанных на листке чисел?

Ответ

Ответ. .

Решение.

Оценка. Предположим, что какое-то из выписанных на листке чисел больше , скажем, . Тогда наибольшее из чисел , не меньше , что больше — противоречие. Значит, каждый из написанных НОДов не превосходит , потому количество различных НОДов не может превышать .

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

Похожие задачи

ВсОШ 2022, 11 класс, задача 1

(20 баллов) Назовём главными делителями составного числа n два наибольших его натуральных делителя, отличных от n. Составные натуральные числа a и b таковы, что главные делители числа a совпадают с главными делителями числа b. Докажите, что a=b. (А.С. Голованов)

Очень сложная

Теория чисел

ВсОШ 2025, 11 класс, задача 3

Пару многочленов F(x,y) и G(x,y) с целыми коэффициентами назовём важной, если из делимости на 100 обеих разностей F(a,b)-F(c,d) и G(a,b)-G(c,d), где a, b, c, d — целые, следует, что числа a-c и b-d делятся на 100. Существует ли такая важная пара многочленов P(x,y), Q(x,y), что пара многочленов P(x,y

Очень сложная

Алгебра

Теория чисел

ВсОШ 2021, 11 класс, задача 6

В тетраэдре SABC длины всех шести ребер различны. Точка A' в плоскости SBC симметрична точке S относительно серединного перпендикуляра к отрезку BC. Точка B' в плоскости SAC и точка C' в плоскости SAB определяются аналогично. Докажите, что плоскости AB'C', A'BC', A'B'C и ABC имеют общую точку. (А. К

Очень сложная

Комбинаторика

ВсОШ 2023, 10 класс, задача 3

(20 баллов) Даны натуральные числа a и b такие, что age 2b. Существует ли многочлен P(x) степени больше 0 с коэффициентами из множества {0,1,2,ldots,b-1} такой, что P(a) делится на P(b)? (Т. Коротченко)

Очень сложная

Алгебра

Теория чисел