Олимпиадные задачи из источника «Сайт "Криптография" (cryptography.ru)» для 10 класса - сложность 1-5 с решениями

Для передачи сообщений по телеграфу каждая буква русского алфавита (Е и Ё отождествлены) представляется в виде пятизначной комбинации из нулей и единиц, соответствующих двоичной записи номера данной буквы в алфавите (нумерация букв начинается с нуля). Например, буква А представляется в виде 00000, буква Б - 00001, буква Ч – 10111, буква Я – 11111. Передача пятизначной комбинации производится по кабелю, содержащему пять проводов. Каждый двоичный разряд передается по отдельному проводу. При приеме сообщения Криптоша перепутал провода, поэтому вместо переданного слова получен набор букв ЭАВЩОЩИ. Найдите переданное слово.

В древнем шифре, известном под названием "Сцитала", использовалась полоска папируса, которая наматывалась на круглый стержень виток к витку без просветов и нахлестов. Далее, при горизонтальном положении стержня, на папирус построчно записывался текст сообщения. После этого полоска папируса с записанным на ней текстом посылалась адресату, имеющему точно такой же стержень, что позволяло ему прочитать сообщение. В наш адрес поступило сообщение, зашифрованное с помощью шифра "Сцитала". Однако его автор, заботясь о том, чтобы строчки были ровные, во время письма проводил горизонтальные линии, которые остались на полоске в виде черточек между буквами. Угол наклона этих черточек к краю ленты равен α, ширина полоски равна <i>d</i>, а ширина каждой строки равна &...

Комбинация  (<i>x, y, z</i>)  трёх натуральных чисел, лежащих в диапазоне от 10 до 20 включительно, является отпирающей для кодового замка, если  3<i>x</i>² – <i>y</i>² – 7<i>z</i> = 99.  Найдите все отпирающие комбинации.

Цифры 0, 1, ..., 9 разбиты на несколько непересекающихся групп. Из цифр каждой группы составляются всевозможные числа, для записи каждого из которых все цифры группы используются ровно один раз (учитываются и записи, начинающиеся с нуля). Все полученные числа расположили в порядке возрастания и <i>k</i>-му числу поставили в соответствие <i>k</i>-ю букву алфавита АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ. Оказалось, что каждой букве соответствует число и каждому числу соответствует некоторая буква. Шифрование сообщения осуществляется заменой каждой буквы соответствующим ей числом. Если ненулевое число начинается с нуля, то при шифровании этот нуль не выписывается. Восстановите сообщение 873146507381 и укажите таблицу замены букв числами.

Исходное сообщение, состоящее из букв русского алфавита и знака пробела (-) между словами, преобразуется в цифровое сообщение заменой каждого его символа парой цифр согласно следующей таблице:<img src="/storage/problem-media/35742/problem_35742_img_2.gif" border="0" alt="\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline А & Б & В & Г & Д & Е & Ж & З & И & К & Л & М & Н & О & П \ \hline 01 & 02 & 03 & 04 & 05 & 06 & 07 & 08 & 09 & 10 & 11 & 12 & 13 & 14 & 15 \ \hline \end{tabular}" width="497" height="43"> <img src="/storage/problem-media/35742/problem_35742_img_3.gif" border="0" alt="\b...

Каждую букву исходного сообщения заменили её двузначным порядковым номером в русском алфавите согласно таблице:<div align="center"><img src="/storage/problem-media/35741/problem_35741_img_2.gif"><img src="/storage/problem-media/35741/problem_35741_img_3.gif"></div>Полученную цифровую последовательность разбили (справа налево) на трёхзначные цифровые группы без пересечений и пропусков. Затем каждое из полученных трёхзначных чисел умножили на 77 и оставили только три последние цифры произведения. В результате получилась следующая последовательность цифр:  317564404970017677550547850355.  Восстановите исходное сообщение.

Для проверки телетайпа, печатающего буквами русского алфавита АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ передан набор из 9 слов, содержащий все 33 буквы алфавита. В результате неисправности телетайпа на приемном конце получены слова ГЪЙ АЭЁ БПРК ЕЖЩЮ НМЬЧ СЫЛЗ ШДУ ЦХОТ ЯФВИ Восстановите исходный текст, если известно, что характер неисправности таков, что каждая буква заменяется буквой, отстоящей от нее в указанном алфавите не дальше, чем на две буквы. Например, буква Б может перейти в одну из букв А, Б, В, Г.

(Задача с сайта<a href="http://www.cryptography.ru">www.cryptography.ru</a>.)

Суммой двух букв назовём букву, порядковый номер которой в алфавите имеет тот же остаток от деления на число букв в алфавите, что и сумма порядковых номеров исходных двух букв. Суммой двух буквенных последовательностей одинаковой длины назовём буквенную последовательность той же длины, полученную сложением букв исходных последовательностей, стоящих на одинаковых местах. Докажите, что сумма любой последовательности из 26 различных букв английского алфавита с последовательностью букв, представляющей собой сам этот алфавит, содержит не менее двух одинаковых букв.

Суммой двух букв назовём букву, порядковый номер которой в алфавите имеет тот же остаток от деления на число букв в алфавите, что и сумма порядковых номеров исходных двух букв. Суммой двух буквенных последовательностей одинаковой длины назовём буквенную последовательность той же длины, полученную сложением букв исходных последовательностей, стоящих на одинаковых местах. Докажите, что существует последовательность из 33 различных букв русского алфавита, сумма которой с последовательностью букв, представляющей собой сам этот алфавит, не содержит одинаковых букв.

Шифрпреобразование простой замены в алфавите  <i>A</i> = {<i>a</i>₁, <i>a</i>₂, ..., <i>a_n</i>},  состоящем из <i>n</i> различных букв, заключается в замене каждой буквы шифруемого текста буквой того же алфавита, причём разные буквы заменяются разными. Ключом шифра простой замены называется таблица, в которой указано, какой буквой надо заменить каждую букву алфавита <i>A</i>. Если слово СРОЧНО зашифровать простой заменой с помощью ключа: <div align="center"><img src="/storage/problem-media/35699/problem_35699_img_2.gif"></div>то получится слово ВЗДАБД. Зашифровав полученное слово с помощью того же ключа еще раз,...

При передаче сообщений используется некоторый шифр. Пусть известно, что каждому из трех шифрованных текстов ЙМЫВОТСЬЛКЪГВЦАЯЯ УКМАПОЧСРКЩВЗАХ ШМФЭОГЧСЙЪКФЬВЫЕАКК соответствовало исходное сообщение МОСКВА. Попробуйте расшифровать три текста ТПЕОИРВНТМОЛАРГЕИАНВИЛЕДНМТААГТДЬТКУБЧКГЕИШНЕИАЯРЯ ЛСИЕМГОРТКРОМИТВАВКНОПКРАСЕОГНАЬЕП РТПАИОМВСВТИЕОБПРОЕННИГЬКЕЕАМТАЛВТДЬСОУМЧШСЕОНШЬИАЯК при условии, что двум из них соответствует одно и то же сообщение. Сообщениями являются известные крылатые фразы. (Задача с сайта<a href="http://www.cryptography.ru">www.cryptography.ru</a>.)

Сообщение, зашифрованное в пункте А шифром простой замены в алфавите из букв русского языка и знака пробела (–) между словами, передается в пункт Б отрезками по 12 символов. При передаче очередного отрезка сначала передаются символы, стоящие на чётных местах в порядке возрастания их номеров, начиная со второго, а затем – символы, стоящие на нечётных местах (также в порядке возрастания их номеров), начиная с первого. В пункте Б полученное шифрованное сообщение дополнительно шифруется с помощью некоторого другого шифра простой замены в том же алфавите, а затем таким же образом, как и из пункта А, передается в пункт В. По перехваченным в пункте В отрезкам:

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

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

    –Е–ПФПУБ–ЮОБ

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

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

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

восстановите исх...

Некоторый текст зашифровали, поставив в соответствие каждой букве некоторую (возможно, ту же самую букву) букву так, что текст можно однозначно расшифровать. Докажите, что найдется такое число N, что после N-кратного применения шифрования заведомо получится исходный текст. Найдите из всех таких значений N наименьшее, годящееся для всех шифров (при условии, что в алфавите 33 буквы). (Задача с сайта<a href="http://www.cryptography.ru">www.cryptography.ru</a>.)

При установке кодового замка каждой из 26 латинских букв, расположенных на его клавиатуре, сопоставляется произвольное натуральное число, известное лишь обладателю замка. Разным буквам сопоставляются не обязательно разные числа. После набора произвольной комбинации попарно различных букв происходит суммирование числовых значений, соответствующих набранным буквам. Замок открывается, если сумма делится на 26. Докажите, что для любых числовых значений букв существует комбинация, открывающая замок.

Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?