Эйлер атындағы олимпиада, 2019-2020 оқу жылы, аймақтық кезеңнің 2 туры

Бір жолда 1999 натурал сандар жазылған. Осы жолдағы әр екі көрші санның астына олардың ең үлкен ортақ бөлгішін жазып шығып, екінші жолды алған. Дәл сол сияқты, үшінші, төртінші, $\ldots$ жолдардын алған. 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, которые, в силу доказанного, не могут стоять ни в каком порядке, так как любые два из них делятся на простое число, на которое не делится третье.