|
|
 |
Условие
На доске написано число 1. Если на доске написано число а, его можно заменить любым числом вида a + d, где d взаимно просто с а и 10 ≤ d ≤ 20.
Можно ли через несколько таких операций получить на доске число 18! ?
Решение 1
Заметим, что число 18! – 19 оканчивается на 1. Будем прибавлять к числу на доске 10. При этом каждый раз будет получаться число, оканчивающееся на 1, и, следовательно, взаимно простое с числом 10, так что операция возможна. В конце концов на доске появится число
18! – 19. Мы прибавим к нему 19 и получим 18!.
Решение 2
18! – 19 ≡ 17 (mod 18). Поэтому достаточно на первом шаге получить 17 = 1 + 16 и далее прибавлять по 18, пока не получится 18! – 19. Теперь можно прибавить 19.
Решение 3
По теореме Вильсона (см. задачу 60719) 18! ≡ 18 (mod 19). Поэтому достаточно на первом шаге получить 18 = 1 + 17, а далее прибавлять по 19.
