Задача
По кругу стоят 101000 натуральных чисел. Между каждыми двумя соседними числами записали их наименьшее общее кратное.
Могут ли эти наименьшие общие кратные образовать 101000 последовательных чисел (расположенных в каком-то порядке)?
Решение
Пусть n = 101000. Обозначим исходные числа (в порядке обхода) через a1, ..., an; мы будем считать, что an+1 = a1. Положим bi = НОК(ai, ai+1). Предположим что b1, ..., bn – это n подряд идущих натуральных чисел.
Рассмотрим наибольшую степень двойки 2m, на которую делится хотя бы одно из чисел ai. Заметим, что ни одно из чисел b1, ..., bn не делится на 2m+1. Пусть для определённости a1 делится на 2m; тогда b1 и bn кратны 2m: b1 = 2mx, bn = 2my при некоторых нечётных x и y. Без ограничения общности можно считать, что x < y. Тогда среди n последовательных чисел b1, ..., bn должно быть и число 2m(x + 1) (поскольку 2mx < 2m(x + 1) < 2my). Но это число делится на 2m+1 (так как x + 1 чётно), что невозможно. Противоречие.
Ответ
Не могут.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь