Processing math: 100%

Олимпиада имени Леонарда Эйлера 2019-2020 учебный год, II тур регионального этапа


В строку выписано 1999 натуральных чисел. Во вторую строку под каждыми двумя соседними числами выписали их наибольший общий делитель. Аналогичным образом получили третью, четвёртую и т. д. строки. Может ли 1000-я строка состоять из 1000 последовательных чисел в некотором порядке? ( С. Берлов )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.    
Ответ. Не может.
Решение. Назовем число a из таблицы предком числа b, если от a до b можно добраться сверху вниз по цепочке описанных в условии наибольших общих делителей (НОД). Двигаясь по строкам снизу вверх, нетрудно убедиться, что у каждого числа a из 1000-ой строки 1000 предок из первой строки, все эти предки идут в строке подряд, и a равно их НОД. Пусть числа a и b из 1000-ой строки делятся на простое число p. Тогда делятся на p и все предки каждого из них. Если число c записано в 1000-ой строке между a и b, то каждый его предок является также предком либо a, либо b. Поэтому c также делится на p. Но среди 1000 последовательных чисел найдутся числа, дающие при делении на 30 остатки 6, 10 и 15, которые, в силу доказанного, не могут стоять ни в каком порядке, так как любые два из них делятся на простое число, на которое не делится третье.