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

Тақтада 1 саны жазылған. Егер тақтада $a$ саны жазылса, онда оны $a+d$ түріндегі кез келген санмен алмастыруға болады, мұндағы $d$ саны $a$ санымен өзара жай және $10 \leq d \leq 20$. Тақтада осындай бірнеше операция қолданып $18!=1 \cdot 2 \cdot 3 \cdot \ldots \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.