Олимпиада имени Леонарда Эйлера 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, которые, в силу доказанного, не могут стоять ни в каком порядке, так как любые два из них делятся на простое число, на которое не делится третье.