На кодовом замке имеется круглый диск с риской. Вокруг диска нанесены числа от 0 до 99 по часовой стрелке. Для управления замком служат две кнопки: «вправо» и «влево». При нажатии на кнопку «вправо» диск вращается на 43 деления по часовой стрелке, при нажатии на кнопку «влево» – на 20 делений против часовой стрелки. Каждая из этих операций выполняется за 1 секунду. Изначально замок установлен на число 0. Замок открывается при его установке на число 50 – ключ замка.
Далее, понятно, что достаточно подобрать число u, для которого r100(43u)= 10, 30, 50, 70, 90, так как после этого замок можно установить на ключ 50, вычитая 20 несколько раз.
Будем действовать перебором: 43, 86, 129, 172, 215, 258, 301, 344, 387, 430. Значит 10 вправо, 4 влево, итого 14 секунд. Как видно из сделанного перебора, меньше чем за 14 секунд не получится.
Б. Продолжим перебор, показывающий, на какие деления можно установить замок только кнопкой «вправо»: 0, 43, 86, 129, 172, 215, 258, 301, 344, 387, 430, 473, 516, 559, 602, 645, 688, 731, 774, 817, 860.
Далее кнопкой «влево» можно уменьшать эти числа на 20. Поэтому чтобы можно было открыть замок при любом ключе, достаточно, чтобы среди перечисленных чисел встречались все остатки от деления на 20. Непосредственно видно, что это так. Следовательно, замок можно открыть при любом ключе.
В. Нужно найти u, v такие, что r100(43u - 20v)=k, где k - ключ. Если u≥20, то можно уменьшить u на 20 следующим образом: 43u-20v=43(u-20)-20(v-43). Следовательно, кнопку «вправо» имеет смысл жать не более 19 раз. При этом получим все остатки от деления на 20, как видно и из перебора, сделанного в п.2. Затем кнопку «влево» жмем не более 4 раз, так как 5·20=100 и за 5 раз диск сделает полный оборот. Таким образом, в выражении r100(43u - 20v)=k числа u, v заключены в пределах 0≤u≤19, 0≤v≤4. Итого 19+4=23 секунды.
A. 14 секунд
В. 23 секунды