Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: ...к задачам третьей олимпиады Up: 7.6. Указания и решения Previous: ...к задачам первой олимпиады Contents: Содержание

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

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

Рис. 15.

\epsfbox{cript.2}

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

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

Пусть $ \Gamma_1$ - первый член, а $ X$ - разность арифметической прогрессии, которую коммерсант использовал при шифровании. Тогда из условия получаем:
\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$ и $ B$. Тогда записи $ 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}
Подставив $ X$ из (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 (при $ D=0$), 2371640978 (при $ D=1$).

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

Указание. Обозначим через $ f(x)$ - остаток от деления значения многочлена $ F(x)$ на 10. Для однозначного расшифрования необходимо и достаточно, чтобы разным значениям $ x$ соответствовали разные значения $ f(x)$. Поэтому $ f(0)$, $ f(1)$, ..., $ f(9)$ принимают все значения от 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)$ - остаток от деления числа $ y$ на 10.

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

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

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

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

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

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

слово К О Р А Б Л И
$ Т$ 10 14 16 1 2 11 9


ш.с.1 Ю П Т Ц А Р Г Ш А Л Ж Ж Е В Ц Щ Ы Р В У У
$ С_1$ 29 15 18 22 1 16 4 24 1 11 7 7 6 3 22 25 27 16 3 19 19


ш.с.2 Ю П Я Т Б Н Щ М С Д Т Л Ж Г П С Г Х С Ц Ц
$ С_2$ 29 15 0 18 2 13 25 12 17 5 18 11 7 4 15 17 4 21 17 22 22


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

Вначале для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 1 найдем соответствующий участок и. с. 2. Имеем:
$ С_2-С_1$ 0 0 12 26 1 27 21 18 16 24 11 4 1 1 23 22 7 5 14 3 3

$ Т_1$ 10 14 16 1 2 11 9
$ Т_2$ $ Т_{21}$ $ Т_{22}$ $ Т_{23}$ $ Т_{24}$ $ Т_{25}$ $ Т_{26}$ $ Т_{27}$

Поэтому для участка и. с. 2 получаем следующие 15 вариантов:
$ k$ 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. Имеем:
$ С_1-С_2$ 0 0 18 4 29 3 9 12 14 6 19 26 29 29 7 8 23 25 16 27 27

$ Т_2$ 10 14 16 1 2 11 9
$ Т_1$ $ Т_{11}$ $ Т_{12}$ $ Т_{13}$ $ Т_{14}$ $ Т_{15}$ $ Т_{16}$ $ Т_{17}$


Поэтому для участка и. с. 1 получаем следующие 15 вариантов:
$ k$ 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 на буквы русского алфавита. Получаем следующие таблицы:
$ k$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
К К Ц Е Л Ж А Э Ь Г Х О Л Л В
О Ь К П Л Д Б Я З Щ Т П П Ж Е
участок Э М С Н Ж Г Б К Ы Ф С С И З Ч
и.с.2 Ы Б Э Ц У С Щ М Д Б Б Ш Ч З Е
В Ю Ч Ф Т Ь Н Е В В Щ Ш И Ж Р
Э Б Ю Ы Д Ц П М М Г В Т Р Щ О
Я Ы Щ В Ф Н К К Б А Р О Ч М М

$ k$ 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 миллионов!

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

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100