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

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

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

3.1. Если каждый из 993 абонентов связан с 99 абонентами, то для этого потребуется $993\cdot99/2$ линий связи, которое не может быть целым числом.

Ответ: нельзя.

3.2. Несложно заметить, что рассматриваемый шифр обладает тем свойством, что при зашифровании разные буквы заменяются разными. Следовательно, при зашифровании разных слов получаются разные слова. С другой стороны, одинаковые буквы заменяются на одинаковые независимо от цикла шифрования, так как используется один и тот же ключ. Следовательно, при зашифровании одинаковых слов получаются одинаковые слова. Таким образом, число различных слов, которые можно получить в указанном процессе шифрования с начальным словом СРОЧНО, совпадает с наименьшим номером цикла шифрования, дающем это начальное слово.

Так как буква С повторяется в каждом цикле шифрования, номер которого кратен 5, а буквы Р, О, Ч, Н - в каждом цикле, номера которых кратны 13, 7, 2 и 3 соответственно, то слово СРОЧНО появится впервые в цикле с номером, равным $НОК(2,3,5,7,13)=\linebreak =2\cdot3\cdot5\cdot7\cdot13=2730.$

Ответ: 2730.

3.3. Если символы одного отрезка занумеровать последовательно числами от 1 до 12, то после передачи его из А в Б символы расположатся в порядке (2,4,6,8,10,12,1,3,5,7,9,11), а после передачи этого отрезка (замена символов не меняет порядка) из Б в В - в порядке (4,8,12,3,7,11,2,6,10,1,5,9). Переставим символы перехваченных отрезков в соответствии с их номерами до передачи из пункта А. Получим отрезки вида:

Л П Г С Ж Н Ж О О Б Т -

Е С К Р У П Д С Б Х К Т

Ю У П - О Б Ф Е Б - П -

Л Ж Е С Ж У О П Л У К -

Щ К Х С П Г Б М Ы О Э Ц

Л К Л У Ж Н - Л Г Т И К

Поскольку в пунктах А и Б одинаковые буквы заменялись одинаковыми, а разные - разными, то найденные отрезки можно рассматривать как замену одинаковых символов исходного текста одинаковыми, а разных - разными. Сравнивая места одинаковых букв слова КРИПТОГРАФИЯ и места одинаковых символов в отрезках, находим, что слово КРИПТОГРАФИЯ зашифровано во втором отрезке. Это дает возможность найти исходное сообщение, используя гипотезы о частых буквах русского языка и смысле исходного сообщения.

Ответ:

С О В Р Е М Е Н Н А Я -

К Р И П Т О Г Р А Ф И Я

Э Т О - Н А У К А - О -

С Е К Р Е Т Н О С Т И -

Ш И Ф Р О В А Л Ь Н Ы Х

С И С Т Е М - С В Я З И

3.4. Докажем, что 20 является периодом рассматриваемой последовательности. Заметим, что у двух натуральных чисел и совпадают цифры единиц тогда и только тогда, когда их разность делится на 10. Таким образом, мы достигнем цели, если докажем, что разность $(n+20)^{n+20}-n^n$ делится на 10 для всех натуральных значений . Исходя из того, что делится на , получаем, что $(n+20)^{n+20}-n^{n+20}$ делится на . Кроме того, $n^{n+20}-n^n=n^n(n^{20}- 1)=n^n((n^4)^5-1)$ делится на для всех . Вместе с тем,
$\begin{gather*} n(n^4-1)=n(n-1)(n+1)(n^2+1)=n(n-1)((n+2)(n-2)+5)=\\ =(n-2)(n-1)n(n+1)(n+2)+5(n-1)n(n+1), \end{gather*}$
где каждое из слагаемых делится на 2 (так как содержит произведение ) и делится на 5 (поскольку первое слагаемое есть произведение пяти последовательных чисел, а второе содержит множитель 5). Следовательно, $n^{n+20}-n^n$ делится на 10. Число

$\begin{displaymath} (n+20)^{n+20}-n^n=\left((n+20)^{n+20}-n^{n+20}\right)+(n^{n+20}-n^n) \end{displaymath}$

делится на 10, так как каждое из слагаемых делится на 10.

Проверим, что 20 является наименьшим периодом. Выписывая первые 20 значений последовательности , , ...

1 4 7 6 5 3 6 9 0 1 6 3 6 5 6 7 4 9 0

легко убедиться, что она не имеет периода меньшей длины.

3.5. Для того, чтобы найти исходное сообщение, найдем сначала цифровое сообщение, полученное из него с помощью таблицы замены. Согласно этой таблице на нечетных местах цифрового образа исходного сообщения могут быть только цифры 0, 1, 2 и 3. Последовательно рассматривая эти значения для каждого нечетного места цифрового сообщения с использованием соответствующей цифры шифрованного сообщения, найдем соответствующие варианты значений цифр шифрующего отрезка. Для этого вычислим остатки от деления разностей цифр шифрованного и варианта цифрового сообщений:

порядковый номер места 1 3 5 7 9 11 13 15 17 19 21 23 25 27

шифрованное сообщение 2 3 8 7 1 4 8 6 6 0 1 3 5 8

вариант 0 для 2 3 8 7 1 4 8 6 6 0 1 3 5 8

вариант 1 для $\Gamma_k$ 1 2 7 6 0 3 7 5 5 9 0 2 4 7

вариант 2 для $\Gamma_k$ 0 1 6 5 9 2 6 4 4 8 9 1 3 6

вариант 3 для $\Gamma_k$ 9 0 5 4 8 1 5 3 3 7 8 0 2 5

По задаче 3.4 последовательность, из которой выбран шифрующий отрезок, является периодической с периодом 20. Из таблицы вариантов значений цифр шифрующего отрезка видим, что 5-я его цифра может быть равна 5, 6, 7 или 8, а его 25-я цифра - 2, 3, 4 или 5. Отсюда получаем, что $\Gamma_5 = \Gamma_{25} = 5$ . На периоде последовательности, из которой выбран шифрующий отрезок, есть две цифры 5: и $С_{15}$ . Поэтому рассмотрим два случая. Если $\Gamma_5 = С_5$ , то $\Gamma_7=С_7=3$ . Это противоречит таблице вариантов значений цифр шифрующего отрезка, в которой $\Gamma_7$ может быть равна 4, 5, 6 или 7. Если же $\Gamma_5 = С_{15}$ , то соответствующий шифрующий отрезок: 1636567490147656369016365674 хорошо согласуется с таблицей вариантов значений его цифр. Вычитая цифры найденного отрезка из соответствующих цифр шифрованного сообщения и заменяя разности их остатками от деления на 10, получим по таблице замены пар цифр на буквы исходное сообщение:

шифрованное сообщение 23 39 86 72 16 45 81 60 67 06 17 31 55 88

шифрующийотрезок 16 36 56 74 90 14 76 56 36 90 16 36 56 74

цифровоесообщение 17 03 30 08 26 31 15 14 31 16 01 05 09 14

исходноесообщение С В Я З Ь - П О - Р А Д И О

Рис. 16.

$\epsfbox{cript.11}$

3.6. Обозначения понятны из рис. 16.
1) центрально симметричен относительно .
2) центрально симметричен относительно .
3) (параллельный перенос).
4) - квадрат.
5) $MT\perp AC$ , $NS\perp AC$ .
6) (, , $\angle T=\angle S=90^\circ$ ).
7) Без ограничения общности .
8) , $AP=\dfrac{1}{4}\mp x$ , $PQ=\dfrac{1}{2}$ , $QC=\dfrac14\pm x$ .
9) (, $\angle M {=}\angle Q$ , $\angle K{=}\angle L{=}90^\circ$ ) $\Rightarrow$ .
10) .
11) Площадь $ABC=\dfrac{\sqrt3}{4}$ равна площади , $y=\dfrac{\sqrt[4]3}{2}$ .
12) $MT=\dfrac{\sqrt3}{4}$ (половина высоты ).
13) $QT=PQ-PT=\dfrac{1}{2}\mp x$ .
14) (теорема Пифагора), т.е.
$\begin{align*} \left(\dfrac{\sqrt[4]{3}}{2}\right)^2 =& \left(\dfrac{\sqrt3}{4}... ...vert \Iff\\ &\Iff\ x=\dfrac{1}{2}-\dfrac{1}{4}\sqrt{4\sqrt3-3}. \end{align*}$
15) $AP:PQ:QC = \dfrac14\left(\sqrt{4\sqrt3-3}-1\right): \dfrac12: \dfrac14\left... ...PQ:QC} = \left(\sqrt{4\sqrt3-3}-1\right):2:\left(3-\sqrt{4\sqrt3-3}\right).$