Олимпиада имени Леонарда Эйлера2010-2011 учебный год, II тур регионального этапа

На доске написано число 1. Если на доске написано число $a$, его можно заменить любым числом вида $a+d$, где $d$ взаимно просто с $a$ и $10 \leq d \leq 20$. Можно ли через несколько таких операций получить на доске число $18! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot 18$? ( И. Рубанов )

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

Комментарии от администратора Комментарии от администратора №1.     Решение 1. Заметим, что число $18!-19$ оканчивается на 1. Будем прибавлять к числу на доске 10. При этом каждый раз будет получаться число, оканчивающееся на 1, и, следовательно, взаимно простое с числом 10, так что операция возможна. В конце концов на доске появится число $18!-19$. Мы прибавим к нему 19 и получим 18!.

Комментарии от администратора Комментарии от администратора №2.     Решение 2. Ясно, что 18! не делится на 19. Тогда и $18! - 19k$ не делится на 19 при любом натуральном $k$. Теперь, если мы научимся получать числа, имеющие все возможные ненулевые остатки от деления на 19, то, прибавляя по 19 к одному из них, мы сумеем получить 18!. (В частности, достаточно было бы уметь получать какие-то 19 последовательных чисел.) Научимся это делать. Числа от 11 до 21 получаются одной операцией. Числа вида $22+n$ при $0 < n < 10$ получаются как $1+10+(11+n)$. Число 22 получить не удаётся, зато получается число 41 того же остатка, например, $41 = 1+10+16+14$.

Комментарии от администратора Комментарии от администратора №3.     Решение 3. По теореме Вильсона $18! \equiv 18 \pmod {19}$. Поэтому достаточно на первом шаге получить $18 = 1 + 17$, а далее прибавлять по 19.

Комментарии от администратора Комментарии от администратора №4.     Решение 4.$18! - 19 \equiv 17 \pmod {18}$. Поэтому достаточно на первом шаге получить $17 = 1+16$ и далее прибавлять по 18, пока не получится $18! - 19$. Теперь можно прибавить 19.