Главная | Обратная связь

P a b d g l i u r c a v t h o t u e a d s p

Замен пар, противоречащих рассматриваемому свойству в этом случае нет. Для второго текста свойство не выполняется. Действительно, пара lg переходит вmh, но при этом hm переходит в in:

C r y p t o g r a p h i c a l g o r i t h m

D s z q u p h s b q i j d b m h p s j u i n

Таким образом, первый шифртекст является единственным кандидатом на ответ.

Задача 5.Криптоша изобрел устройство, которое позволяет вычислить среднее арифметическое любых 9 чисел или любых 223 чисел. Как правильно использовать это устройство, чтобы найти среднее арифметическое любых 2006 чисел. При необходимости Криптоша может дополнительно провести одно деление и одно умножение.

Решение

Заметим, что 2007 = 223 · 9. Поэтому, используя данное устройство, можно было бы легко найти среднее арифметическое не 2006-ти, а 2007-ми чисел. Действительно, обозначим эти 2007 чисел как a₁,…,a₂₀₀₇, а их среднее арифметическое как A₂₀₀₇. Разобьем их на 9 групп по 223 числа в каждой: первая группа: a₁,…,a₂₂₃, вторая группа: a₂₂₄,…,a₄₄₆, ..., девятая группа:a₁₇₈₅,…,a₂₀₀₇. Для каждой из 9 групп найдем среднее арифметическое, входящих в нее чисел. Затем вычисляем среднее арифметическое найденных девяти средних арифметических. Это и будет среднее арифметическое 2007 чисел, потому что

A₂₀₀₇ = (a₁ + ... + a₂₀₀₇) : 2007 =
((a₁ + ... + a₂₂₃) : 9 + (a₂₂₄ + ... + a₄₄₇) : 9 + ... + (a₁₇₈₅ + ...+ a₂₀₀₇) : 9) : 223

Итак, среднее арифметическое любых 2007-ми чисел мы находить умеем. Покажем теперь как найти среднее арифметическое A₂₀₀₆ от 2006-ти чиселa₁,…,a₂₀₀₆. Добавим к этим числам еще одно число a₂₀₀₇, равное нулю, и вычислим среднее арифметическое A₂₀₀₇ теперь уже 2007-ми чисел. Воспользовавшись тем, что мы можем выполнить одно умножение и одно деление, находим

A₂₀₀₆ = A₂₀₀₇ : 2007 · 2006,

так как

A₂₀₀₆ = (a₁ + ... + a₂₀₀₆) : 2006 =
= ((a₁ + ... + a₂₀₀₆ + ... + a₂₀₀₇) : 2006 =
= ((a₁ + ... + a₂₀₀₆ + ... + a₂₀₀₇) : 2007 · 2007 : 2006 =
= A₂₀₀₇ · 2007 : 2006

Задача решена.

Отметим в заключение, что если разбить данные числа на несколько групп, найти среднее арифметическое каждой группы и затем взять среднее арифметическое полученных значений, то результат, вообще говоря, не будет средним арифметическим исходных чисел и вот простой пример:

		1 + 2		3 + 4 +5
———	+	————
1 + 2 + 3 + 4 + 5
———————	≠	————————

Тем не менее, таким способом среднее арифметическое вычислять можно, если разбивать исходные числа на группы, состоящие из одинакового количества чисел.

Задача 6.Каждая буква фрагмента известного стихотворения Ф.И. Тютчева заменена некоторой буквой так, что разным буквам соответствуют разные буквы, а одинаковым - одинаковые. Пробелы и знаки препинания сохранены. Восстановите этот фрагмент стихотворения:

Гьюь Фюббшн эй яюэовл,
Пфзшэюь юришь эй шчьйфшвл:
Г эйщ юбюрйээпо бвпвл -
С Фюббшн ьюцэю вюылъю сйфшвл.
Решение

1. Рассмотрим фрагменты эй и эйщ; это — слова из 2 и 3 букв. Одно из слов имеет суффикс йээ. Весьма вероятно, что э заменяет букву н, а й — одна из гласных: о, а, и, е. Тогда возможными вариантами окончания слова юбюрйээпоявляются следующие: онная, онные, енные, енная, инная, инные. Вариант окончания ные не подходит, так как при этом п заменяет ы, и с буквы ыначинается слово пфзшэюь. Поэтому п заменяет либо а, либо о.

2. Можно попытаться угадать слово бвпвл. В нем в — согласная. Комбинация вида xоx, где x — согласная, вряд ли возможна. Из вариантов xаx, где x — согласная, подходит, разве что тат. Проверим гипотезу: в заменяет т.

3. Замечаем, что 4 окончания слов — овл, швл, пвл, швл образуют рифму. С учетом шага 2, «напрашиваются» варианты окончаний ать, ить, ять.

4. ю часто встречается, скорее всего, это — гласная. Имеется фрагмент ..юбб.. Так как буква н уже занята, удвоение бб — это, скорее всего, замена для сс, июбб — это асс, осс, есс или исс. Возвращаясь к шагу 2, устанавливаем, чтобвпвл — это стать.

5. Учитывая шаг 4, а также то, что с большой буквы начинается имя собственное, попытаемся угадать слово Фюббшн. «Напрашивается» вариантРоссия, Россию, откуда находим, что ю заменяет о, а ш заменяет и.

6. Первое слово — Гьюь. Ясно, что ь — согласная. Возможны следующие слова из 4 букв: удод, скок, умом. Отсюда получаем первое предложение: Умом Россию не понять. Дальше легко догадаться.

Гг

Задача 1.На кодовом замке имеется круглый диск с риской. Вокруг диска нанесены числа от 0 до 99 по часовой стрелке. Для управления замком служат две кнопки: «вправо» и «влево». При нажатии на кнопку «вправо» диск вращается на 43 деления по часовой стрелке, при нажатии на кнопку «влево» – на 20 делений против часовой стрелки. Каждая из этих операций выполняется за 1 секунду. Изначально замок установлен на число 0. Замок открывается при его установке на число 50 – ключ замка.

А. За какое наименьшее время можно открыть замок при данном ключе 50?

Б. Доказать, что замок можно открыть при любом ключе (ключ – число от 1 до 99).

В. За какое наименьшее время можно гарантированно открыть замок при любом ключе?

Решение

А. При нажатии u раз на кнопку «вправо» и v раз на кнопку «влево» замок установится на деление с номером r₁₀₀(43u - 20v), где r₁₀₀ означает остаток от деления на 100. Таким образом, нужно подобрать числа u, v такие, что r₁₀₀(43u - 20v)=50.

Далее, понятно, что достаточно подобрать число u, для которого r₁₀₀(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 такие, что r¹⁰⁰(43u - 20v)=k, где k - ключ. Если u≥20, то можно уменьшить u на 20 следующим образом: 43u-20v=43(u-20)-20(v-43). Следовательно, кнопку «вправо» имеет смысл жать не более 19 раз. При этом получим все остатки от деления на 20, как видно и из перебора, сделанного в п.2. Затем кнопку «влево» жмем не более 4 раз, так как 5·20=100 и за 5 раз диск сделает полный оборот. Таким образом, в выражении r₁₀₀(43u - 20v)=k числа u, v заключены в пределах 0≤u≤19, 0≤v≤4. Итого 19+4=23 секунды.

Задача 2.Делится ли число 4^{22008+32009+1991}-1 на 385?

Решение

385=5*7*11.

Делится, т.к. число 4^k-1 делится на 5 тогда и только тогда, когда k кратно 2, на 7 - тогда и только тогда, когда k кратно 3, на 11 - тогда и только тогда, когда k кратно 5; показатель степени, очевидно, четен.

Далее, число 2²⁰⁰⁸+3²⁰⁰⁹+1991=2²⁰⁰⁸-1+3²⁰⁰⁹+1992 делится на 3, поскольку 2^k-1 делится на 3 при четных k и 1992 делится на 3 по известному признаку делимости.

Числа 3²⁰⁰⁹ и 2²⁰⁰⁸ в десятичной записи оканчиваются на 3 и 6 соответственно, поэтому 2²⁰⁰⁸+3²⁰⁰⁹+1991 оканчивается на 0, т.е. делится на 5.

Задача 3.Для зашифрования сообщения на русском языке его записывают в одну строку без пробелов и знаков препинания. Заглавные буквы заменяются на строчные. В получившейся цепочке буквы нумеруются слева направо 1,2,...,L. Зашифрование происходит путем перестановки букв исходной цепочки по следующему правилу. Фиксируем два натуральных числа a и b. Буква с номером n в исходной цепочке должна в зашифрованной цепочке иметь номер, равный остатку от деления числа a·n+b на L (с одним исключением: если a·n+bнацело делится на L, то остаток полагается равным L). Например, если длина цепочки L=25 и a=9,b=11, то третья буква исходной цепочки будет тринадцатой в зашифрованной цепочке (т.к. 9·13+11=38, а число 38 дает остаток 13 при делении на 25). Известно, что в результате применения этого метода зашифрования к цепочке из 43 букв