Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, I тур дистанционного этапа

Натурал $n$ саны берілген. Қандай да бір натурал санға сол санды $n$-ге бөлгенде шығатын қалдықты қосу операциясын $n$-операция деп атайық. 1-ден үлкен қандай $n$ сандары үшін кез келген натурал саннан бірнеше $n$-операция арқылы $n$-ге бөлінетін сан ала аламыз? ( А. Голованов )

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

При n = 2^k где к натуральное число.

Решение. Заметим, что если m = an + r, то разность чисел m + r = an + 2r и 2m = 2an + 2r делится на n, и потому остатки от деления этих чисел на n одинаковы. По-этому с точки зрения делимости на п, означающей равенство 0 остатка от деления на n, вместо n-операции можно рассматривать операцию умножения числа на 2. После к таких операций мы из числа m получим число 2^km. Если n = 2^k то это число будет делиться на n. Значит, все степени двойки нам подходят. С другой стороны, из m = 1 будут получаться только степени двойки, и делимости ни на какие другие числа не будет.