Задача 64632

Темы:    [ НОД и НОК. Взаимная простота ] [ Четность и нечетность ] [ Принцип крайнего (прочее) ]

Сложность: 4- Классы: 10,11

Условие

Автор: Берлов С.Л.

По кругу стоят 10¹⁰⁰⁰ натуральных чисел. Между каждыми двумя соседними числами записали их наименьшее общее кратное.
Могут ли эти наименьшие общие кратные образовать 10¹⁰⁰⁰ последовательных чисел (расположенных в каком-то порядке)?

Решение

  Пусть  n = 10¹⁰⁰⁰.  Обозначим исходные числа (в порядке обхода) через  a₁, ..., a_n; мы будем считать, что  a_n+1 = a₁.  Положим  b_i = НОК(a_i, a_i+1).  Предположим что  b₁, ..., b_n  – это n подряд идущих натуральных чисел.
  Рассмотрим наибольшую степень двойки 2^m, на которую делится хотя бы одно из чисел a_i. Заметим, что ни одно из чисел  b₁, ..., b_n не делится на 2^m+1. Пусть для определённости a₁ делится на 2^m; тогда b₁ и b_n кратны 2^m:  b₁ = 2^mx,  b_n = 2^my  при некоторых нечётных x и y. Без ограничения общности можно считать, что  x < y.  Тогда среди n последовательных чисел  b₁, ..., b_n  должно быть и число  2^m(x + 1)  (поскольку  2^mx < 2^m(x + 1) < 2^my).  Но это число делится на 2^m+1 (так как  x + 1  чётно), что невозможно. Противоречие.

Ответ

Не могут.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2013-2014
этап
	1
Вариант	4
класс
Класс	10
задача
Номер	10.7