Олимпиада имени Леонарда Эйлера 2022-2023 учебный год, I тур заключительного этапа

На доске написаны натуральные числа от 1 до 1000, по одному разу каждое. Вася может стереть любые два числа и записать вместо них одно: их наибольший общий делитель или их наименьшее общее кратное. Через 999 таких операций на доске осталось одно число, равное натуральной степени десятки. Какое наибольшее значение она может принимать? ( С. Берлов )

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

Заметим, что если взять числа $a$ и $b$, то их НОД и НОК максимум выдаст максимальную степень $5$ из этих двоих. Получается, по инварианту у нас число которое будет получаться каждый раз, максимум поделится на $5^4$ $(625)$, и максимум мы получим $10^4$.

Пример:Берём $1$ и любое другое число не равное $16$ и $625$, у нас по НОДу всегда получится $1$, значит мы можем так делать пока не останется $1$, $16$, $625$. НОК$(1,16)=16$, и потом НОК$(16,625)=10^4$

Понятно что все числа которые имеют в себе простой делитель $p$ отличающийся от $2$ и $5$ сократить до $1$ по сколько иначе оно не будет являтся степенью $10$

Тогда у нас остаются числа вида $$2^k, 2^k5^l, 5^l$$

Максимальная степень $5$ которая встречается во всех числах это $4$ то есть число $625$

Ясно что степень $5$ нельзя увеличить из чего доходим до ответа $10^4$