...к задачам второй олимпиады

Next: ...к задачам третьей олимпиады Up: 7.6. Указания и решения Previous: ...к задачам первой олимпиады Contents: Содержание

...к задачам второй олимпиады

2.1. Рассмотрим один виток ленты на развертке цилиндра (разрез по горизонтальной линии). По условию высота , опущенная на сторону , равна . Угол равен $(90-\alpha)^\circ$ . Отсюда равно $d/\cos\alpha$ . Так как высота строки равна , то всего на одном витке $n=d/(h\cdot\cos\alpha)$ букв.

Рис. 15.

$\epsfbox{cript.2}$

Ответ: чтобы прочитать текст, надо разрезать ленту на участки по $n=d/(h\cdot\cos\alpha)$ букв и сложить их рядом.

2.2. Согласно условию, исходное сообщение состоит из двух пятерок цифр: и . Пусть - последние две цифры суммы чисел, изображенных этими пятерками. Через $a\oplus b$ обозначим последнюю цифру суммы чисел и . Пусть обозначает цифру переноса (цифру десятков) суммы . По условию имеем, что $A_5\oplus B_5=C_2$ и $(A_4\oplus B_4)\oplus D=C_1$ .

Пусть $\Gamma_1$ - первый член, а - разность арифметической прогрессии, которую коммерсант использовал при шифровании. Тогда из условия получаем:
$\begin{align} & A_1 \oplus \Gamma_1 = 4, \\ & A_2 \oplus (\Gamma_1+X) = 2, \\ ... ...\Gamma_1+10X) = 1, \\ & (A_5 \oplus B_5) \oplus (\Gamma_1+11X) = 3. \end{align}$

Обозначим символом $A\equiv B$ равенство остатков от деления на 10 чисел и . Тогда записи $A\oplus B=C$ и $(A+B)\equiv C$ имеют одинаковый смысл. Если $A\equiv B$ и $C\equiv D$ , то $A+B\equiv C+D$ , $A-B\equiv C-D$ . Bсегда $A\equiv A$ , так как остаток от деления единствен.

Из соотношений (4), (5), (9) и (10) находим соответственно:
$\begin{align} & A_4 \equiv 4-(\Gamma_1+3X), \\ & A_5 \equiv 6-(\Gamma_1+4X), \\ & B_4 \equiv 5-(\Gamma_1+8X), \\ & B_5 \equiv 3-(\Gamma_1+9X). \end{align}$
Подставляя эти значения в равенства (11) и (12), получим следующие равенства: $9+D-\Gamma-X\equiv 1$ и $9- \Gamma-2X\equiv 3$ . Отсюда следует, что
$\begin{align} & X \equiv (-2-D), \\ & \Gamma_1 \equiv 2D. \end{align}$
Подставив из (17) и $\Gamma_1$ из (18) в (1), (2),(3), (13), (14), (6), (7), (8), (15), (16), найдем выражения для цифр исходного сообщения:
$\begin{align*} &A_1 \equiv 4-2D, A_2 \equiv 4-D, A_3 \equiv 7, A_4 \equiv D, A_... ...uiv 6+4D, B_3 \equiv 4+5D, B_4 \equiv 1+6D,\\ & B_5 \equiv 1+7D. \end{align*}$
Найденные выражения дают два варианта исходных сообщений:

4470416411 (при ), 2371640978 (при ).

2.3. Ответ: - любое, - не должно делиться на 2 и на 5.

Указание. Обозначим через - остаток от деления значения многочлена на 10. Для однозначного расшифрования необходимо и достаточно, чтобы разным значениям соответствовали разные значения . Поэтому , , ..., принимают все значения от 0 до 9. Найдем эти значения:
$\begin{align*} & f(0)= r_{10}(b(a+0)) & &f(1)= r_{10}(b(a+1))\\ & f(2)= r_{10... ...r_{10}(b(a+7))\\ & f(8)= r_{10}(b(a+4)) & &f(9)= r_{10}(b(a+3)), \end{align*}$
где $r_{10}(y)$ - остаток от деления числа на 10.

Отсюда, пользуясь свойствами остатков, замечаем, что должно быть нечетным (иначе будут только четные числа) и не должно делиться на 5 (иначе будут только 0 и 5). Непосредственной проверкой можно убедиться, что при любом и при всех , удовлетворяющим приведенным условиям, гарантируется однозначность расшифрования.

2.4. Обозначим через остаток от деления на 26 суммы чисел, которые соответствуют первым буквам алфавита ( $n=1,2,\dots,26$ ) $0\leq S(n)\leq25$ .

Если среди чисел $S(1), S(2), \dots, S(26)$ есть нуль: , то искомой ключевой комбинацией является цепочка первых букв алфавита.

Если среди чисел $S(1), S(2), \dots, S(26)$ нет нуля, то обязательно найдутся два одинаковых числа: (считаем, что ). Тогда искомой ключевой комбинацией является участок алфавита, начинающийся с -й и заканчивающийся -й буквой.

2.5. Если две буквы с порядковыми номерами и зашифрованы в буквы с порядковыми номерами и с помощью одной и той же буквы, то остатки от деления чисел и на 30 равны между собой и совпадают с порядковым номером шифрующей буквы (порядковым номером буквы удобно считать число 0). Тогда, с учетом соглашения о порядковом номере буквы , справедливо, что равен остатку от деления числа на 30, а, вместе с тем, равен остатку от деления числа на 30. Если каждое из выражений в скобках заменить соответствующим остатком от деления на 30, то упомянутая связь не нарушится.

Представим в виде набора порядковых номеров известные шифрованные сообщения (обозначим их соответственно ш. с. 1 и ш. с. 2) и слово КОРАБЛИ:

слово К О Р А Б Л И

10 14 16 1 2 11 9

ш.с.1 Ю П Т Ц А Р Г Ш А Л Ж Ж Е В Ц Щ Ы Р В У У

29 15 18 22 1 16 4 24 1 11 7 7 6 3 22 25 27 16 3 19 19

ш.с.2 Ю П Я Т Б Н Щ М С Д Т Л Ж Г П С Г Х С Ц Ц

29 15 0 18 2 13 25 12 17 5 18 11 7 4 15 17 4 21 17 22 22

Возможны 15 вариантов (номер варианта обозначим буквой ) расположения слова КОРАБЛИ в каждом из двух исходных сообщений (и. с. 1, и. с. 2).

Вначале для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 1 найдем соответствующий участок и. с. 2. Имеем:

0 0 12 26 1 27 21 18 16 24 11 4 1 1 23 22 7 5 14 3 3

10 14 16 1 2 11 9

$Т_{21}$ $Т_{22}$ $Т_{23}$ $Т_{24}$ $Т_{25}$ $Т_{26}$ $Т_{27}$

Поэтому для участка и. с. 2 получаем следующие 15 вариантов:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

$Т_{21}$ 10 10 22 6 11 7 1 28 26 4 21 14 11 11 3

$Т_{22}$ 14 26 10 15 11 5 2 0 8 25 18 15 15 7 6

$Т_{23}$ 28 12 17 13 7 4 2 10 27 20 17 17 9 8 23

$Т_{24}$ 27 2 28 22 19 17 25 12 5 2 2 24 23 8 6

$Т_{25}$ 3 29 23 20 18 26 13 6 3 3 25 24 9 7 16

$Т_{26}$ 28 2 29 27 5 22 15 12 12 4 3 18 16 25 14

$Т_{27}$ 0 27 25 3 20 13 10 10 2 1 16 14 23 12 12

Теперь для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 2 найдем соответствующий участок и. с. 1. Имеем:

0 0 18 4 29 3 9 12 14 6 19 26 29 29 7 8 23 25 16 27 27

10 14 16 1 2 11 9

$Т_{11}$ $Т_{12}$ $Т_{13}$ $Т_{14}$ $Т_{15}$ $Т_{16}$ $Т_{17}$

Поэтому для участка и. с. 1 получаем следующие 15 вариантов:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

$Т_{11}$ 10 10 28 14 9 13 19 22 24 16 29 6 9 9 17

$Т_{12}$ 14 2 18 13 17 23 26 28 20 3 10 13 13 21 22

$Т_{13}$ 4 20 15 19 25 28 0 22 5 12 15 15 23 24 9

$Т_{14}$ 5 0 4 10 13 15 7 20 27 0 0 8 9 24 26

$Т_{15}$ 1 5 11 14 16 8 21 28 1 1 9 10 25 27 18

$Т_{16}$ 14 20 23 25 17 0 7 10 10 18 19 4 6 27 8

$Т_{17}$ 18 21 23 15 28 5 8 8 16 17 2 4 25 6 6

Заменим порядковые номера в найденных вариантах участков и. с. 1 и и. с. 2 на буквы русского алфавита. Получаем следующие таблицы:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

К К Ц Е Л Ж А Э Ь Г Х О Л Л В

О Ь К П Л Д Б Я З Щ Т П П Ж Е

участок Э М С Н Ж Г Б К Ы Ф С С И З Ч

и.с.2 Ы Б Э Ц У С Щ М Д Б Б Ш Ч З Е

В Ю Ч Ф Т Ь Н Е В В Щ Ш И Ж Р

Э Б Ю Ы Д Ц П М М Г В Т Р Щ О

Я Ы Щ В Ф Н К К Б А Р О Ч М М

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

К К Э О И Н У Ц Ш Р Ю Е И И С

О Б Т Н С Ч Ь Э Ф В К Н Н Х Ц

участок Г Ф П У Щ Э Я Ц Д М П П Ч Ш И

и.с.1 Д Я Г К Н П Ж Ф Ы Я Я З И Ш Ь

А Д Л О Р З Х Э А А И К Щ Ы Т

О Ф Ч Щ С Я Ж К К Т У Г Е Ы З

Т Х Ч П Э Д З З Р С Б Г Щ Е Е

Из таблиц видно, что осмысленными являются варианты:

и.с.1 = К О Г Д А О Т . . . . . . . К О Р А Б Л И

и.с.2 = К О Р А Б Л И . . . . . . . В Е Ч Е Р О М

Естественно предположить, что в первом исходном сообщении речь идет об отплытии кораблей. Предположив, что неизвестным участком первого исходного сообщения является подходящая по смыслу часть слова ОТПЛЫВАЮТ, находим неизвестную часть второго исходного сообщения: слово ОТХОДЯТ.

2.6. Каждую букву шифрованного сообщения расшифруем в трех вариантах, предполагая последовательно, что соответствующая буква шифрующей последовательности есть буква А, Б или буква В:

шифрованное сообщение Р Б Ь Н П Т С И Т С Р Р Е З О Х

вариант А П А Щ М О С Р З С Р П П Д Ж Н Ф

вариант Б О Я Ш Л Н Р П Ж Р П О О Г Е М У

вариант В Н Ю Ч К М П О Е П О Н Н В Д Л Т

Выбирая из каждой колонки полученной таблицы ровно по одной букве, находим осмысленное сообщение НАШКОРРЕСПОНДЕНТ, которое и является искомым.

Замечание. Из полученной таблицы можно было найти такое исходное сообщение как

НАШ МОРОЗ ПОПОВ ЕМУ

которое представляется не менее осмысленным, чем приведенное выше. А если предположить одно искажение в шифрованном сообщении (скажем, в качестве 11-й буквы была бы принята не буква Р, а буква П), то, наряду с правильным вариантом, можно получить и такой:

НАШ МОРОЗ ПОМОГ ЕМУ

Число всех различных вариантов исходных сообщений без ограничений на осмысленность равно $3^{16}$ или 43046721, т.е. более 40 миллионов!