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

Тақтаға 1-ден 1000-ға дейінгі натурал сандар бір реттен жазылған. Вася кез келген екі санды өшіріп, олардың орнына олардың ең үлкен ортақ бөлгішін немесе ең кіші ортақ еселігін жаза алады. Осындай 999 операциядан кейін тақтада 10-ның натурал дәрежесі болатын бір натурал сан қалған. Сол сан қандай ең үлкен мәнді қабылдай алады? ( С. Берлов )

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

Заметим, что если взять числа $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$