Первая серия задач
1.1. Укажите 2004 подряд идущих натуральных числа, среди которых нет ни одного простого.
1.2. 64 буквы открытого текста последовательно вписываются в клетки шахматной доски по ходу коня, начиная с некоторой его позиции. Криптограмма получается построчным выписыванием букв. Таким образом, секретным ключом является пара (начальная клетка, маршрут коня). Какова комбинаторная сложность этого шифра? (Комбинаторная сложность шифра - это количество всевозможных связанных с ним ключей).
1.3. Цифры 32-ичной системы счисления обозначены буквами русского алфавита: а заменяет ноль, б - единицу, ... (буквы е и ё отождествляются). Шифрование текста (без пробелов, с обязательным начальным указателем Ъ) осуществляется его переводом как 32-ичного числа в десятичную систему счисления. Найдите криптограмму для
ЪОЛИМПИАДАПОКРИПТОГРАФИИ
Расшифруйте криптограмму 28058256.
1.4. (Алфавитная перестановка). 32 буквы русского алфавита (е и ё отождествляются) расположите в порядке их встречаемости в тексте романа А.С. Пушкина "Евгений Онегин" (в современной орфографии). В какой строфе вы завершили этот процесс? (Начало: "Мой дядя ...")
1.5. (Гамильтонова цепь). В игре без ничьих проведен турнир, в котором любые два участника встретились один раз. Докажите, что все участники турнира могут быть перечислены так, чтобы каждый (кроме последнего) оказался победителем непосредственно следующего за ним по списку.
Вторая серия задач
2.1. Шестизначное число называется счастливым, если сумма трех его первых цифр равна сумме трех последних. Докажите, что сумма всех счастливых чисел делится на 13.
2.2. Каждому сотруднику Управления выдан металлический каркас правильного семиугольника, вершины которого последовательно окрашены в цвета спектра, а каждая сторона - в белый или черный цвет. Личным идентификатором является система окраски сторон. Оцените возможное количество сотрудников Управления.
2.3. (Узел замены). Тридцати двум буквам русского алфавита а, б, в, г, д, е, ж, ... , ъ, ы, ь, э, ю, я последовательно присвоены числовые значения 0, 1, 2, ... , 31. Шифрование записанного в цифровом виде текста производится с помощью таблицы
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 4 | 10 | 9 | 2 | 13 | 8 | 0 | 14 | 6 | 11 | 1 | 12 | 7 | 15 | 5 | 3 |
Результат выдается в буквенном виде. Расшифруйте криптограмму КЮЯЩНХЫПЙЩЪФТТКФ.
2.4. Русское существительное в принципе может иметь 12 падежных форм - по 6 в единственном и множественном числе. У конкретного слова некоторые формы могут совпадать. Попытайтесь для каждого k, 1<=k<=12, указать существительное, имеющее точно k различных падежных форм. Сделайте вывод.
2.5. (Теорема о лидере). Докажите, что в турнире из задачи 1.5 есть участник A такой, что если B любой другой участник, то либо A выиграл у B, либо A выиграл у некоторого X, выигравшего у B.
Третья серия задач
3.1. В последовательности 31, 331, 3331, ... найдите первое не простое число.
3.2. (см задачу 2.2). Личным идентификатором сотрудника Отдела является цепочка из шести звеньев, каждое из которых окрашено в белый или черный цвет. Оцените возможное количество сотрудников Отдела.
3.3. Из текста сначала выписываются в порядке встречаемости все гласные буквы, а затем все согласные. Восстановите исходные тексты по криптограммам:
1) еееееееееееттрвпрлтлчрзврск,
2) аоеэоеоеаауаиеглвнтнпбдчст,
3) eaieiaeouaiewlllvnyllwsbmrn.
3.4. (Столбцовая перестановка). Исходный текст длины mn построчно заносится в таблицу с m строками и n столбцами. Под таблицей подписывается пароль - панграмма (все буквы разные) длины n. Криптограмма получается последовательным выписыванием букв по столбцам, упорядоченным алфавитным порядком стоящих под ними букв пароля. Напишите программу восстановления исходного текста по известным паролю и криптограмме. Например, если паролем является слово ЮПИТЕР, а криптограммой строка ЗААТИТАПРЕРНЖВГЬЕЗВЯПАТО, то исходным текстом было ПРИЕЗЖАЕТЗАВТРАВАГОНПЯТЬ.
3.5. (Минимальное отказоустойчивое расширение сети). Компьютерная сеть состоит из шести компьютеров, соединенных в кольцо. Предложите схему соединения такую, чтобы при поломке любого из них среди оставшихся можно было выделить конфигурацию исходной сети. Построенная схема должна использовать минимально возможное число дополнительных компьютеров и соединений.
Четвертая серия задач
4.1. Среди 13 шаров 2 радиоактивных. Если в дозиметр поместить произвольное число шаров, он сообщит, есть в этом наборе хотя бы один радиоактивный шар или нет. Как за 7 включений дозиметра найти оба радиоактивных шара?
4.2. Двоичные шестизначные числа записаны подряд от 000000 до 111111. Эта последовательность разбивается на четырехбитовые блоки, которые заменяются соответствующими десятичными числами - от 0000=0 до 1111=15. Какое число встретится чаще всего? Выскажите общую гипотезу.
4.3. Примитивной пифагоровой тройкой называется тройка взаимно простых натуральных чисел (x,y,z), являющаяся решением уравнения Пифагора x2+y2=z2. Напишите программу, которая для заданного n<=106 определяет число примитивных пифагоровых троек таких, что z<=n.
4.4. (Периодический шифр Виженера). Открытое сообщение разбивается на блоки по k букв в каждом (при необходимости к нему приписывается нужное число букв). Секретным ключом является вектор (a1, a2, ..., ak) с натуральными компонентами. При шифровании i-я буква каждого блока заменяется буквой, стоящей в алфавите на ai позиции правее нее (сдвиг циклический). Зная, что k=3, и что в открытом тексте самые высокие частоты встречаемости имеют буквы О, Е, А, расшифруйте криптограмму:
Ийббзвуздк жсмйс ншчйьял
Пслуъ уктж тсеутжт явхял
Ут пжбппц гкы на юж цььъсмн
Юж жмму ижхгас гбпяк фцшеьй
4.5. В правильном 1001-угольнике проведены все диагонали. Докажите, что если в нем удалить некоторые стороны и диагонали числом менее 1000, то по оставшимся отрезкам можно пройти из любой вершины в любую другую.
