XVII Межрегиональная олимпиада по математике и криптографии 18 ноября 2007 г. - презентация

1 XVII Межрегиональная олимпиада по математике и криптографии 18 ноября 2007 г.

2 Задача 1 Сообщение на русском языке состоит из 6 строк. В каждой строке кроме последней ровно 18 букв (буквы в строках стоят точно друг под другом). Для зашифрования сообщения каждую его букву заменили парой цифр в соответствии с ее порядковым номером в алфавите (А – на 01, Б – на 02, …, Я –на 33). В результате получилась таблица цифр, в которой 36 столбцов. Затем эту таблицу разделили на вертикальные полосы: по три столбца в каждой. После чего полосы переставили в неизвестном порядке Сообщение на русском языке состоит из 6 строк. В каждой строке кроме последней ровно 18 букв (буквы в строках стоят точно друг под другом). Для зашифрования сообщения каждую его букву заменили парой цифр в соответствии с ее порядковым номером в алфавите (А – на 01, Б – на 02, …, Я –на 33). В результате получилась таблица цифр, в которой 36 столбцов. Затем эту таблицу разделили на вертикальные полосы: по три столбца в каждой. После чего полосы переставили в неизвестном порядке

3 Задача 1 (продолжение) Получили вот что: Какой текст был зашифрован?

4 Задача 1(решение) На четных местах – 1,2,4,9,11,12 столбцы; на нечетных – 3,5,6,7,8,10 столбцы. С учетом числа строк в каждом столбце, получаем что последними были 10,2,7,4 или 10,4,7,2. Подходит только второй вариант.

5 Задача 1(решение) Преобразуя пары цифр в буквы, получим: Преобразуя пары цифр в буквы, получим:ЛИМПИАКЕИКРИВЯЩЕНААЯКОВЛО

6 Задача 1(решение) Подбирая по принципу «читаемости» фрагментов слов, восстанавливаем расположение остальных столбцов. Подбирая по принципу «читаемости» фрагментов слов, восстанавливаем расположение остальных столбцов. Ответ: Семнадцатая олимпиада по математике и криптографии посвящена столетию Ивана Яковлевича Верченко. Ответ: Семнадцатая олимпиада по математике и криптографии посвящена столетию Ивана Яковлевича Верченко.

7 Задача 2 Пусть C n (a,b) = abab…ab – целое число, десятичная запись которого образована n–кратным повторением пары цифр a и b, где a0. Пусть C n (a,b) = abab…ab – целое число, десятичная запись которого образована n–кратным повторением пары цифр a и b, где a0. Выясните, при каких n число C n (a,b) делится на 21 при любых значениях a и b. Выясните, при каких n число C n (a,b) делится на 21 при любых значениях a и b.

8 Задача 2 (решение) abab…ab = ab 0101…01 abab…ab = ab 0101…01 a, b – любые, поэтому n должно быть таким, что делится на 21 a, b – любые, поэтому n должно быть таким, что делится на делится на 3 n делится на делится на 3 n делится на 3 Делимость на 7 обеспечена, т.к =71443 Делимость на 7 обеспечена, т.к =71443 Ответ: n=3k, kN. Ответ: n=3k, kN.

9 Задача 3 Сообщение зашифровано следующим образом. Над буквами сообщения надписывается числовая после- довательность, образованная периоди- ческим повторением шести цифр, образующих дату. Например, шестерка отвечает дате 18 ноября 2007 года. После этого буквы сообщения заменяются буквой алфавита, циклически отстоящей от нее справа на число букв, указанное цифрой над ней. Сообщение зашифровано следующим образом. Над буквами сообщения надписывается числовая после- довательность, образованная периоди- ческим повторением шести цифр, образующих дату. Например, шестерка отвечает дате 18 ноября 2007 года. После этого буквы сообщения заменяются буквой алфавита, циклически отстоящей от нее справа на число букв, указанное цифрой над ней.

10 Задача 3 (пример) ОЛИМПИАДА… …ПТЙНППБЛБ…

11 Задача 3 (продолжение) Можно ли прочитать зашифрованное таким образом сообщение Т П И Ё Р Ж Е М А А С Ф С Г Ь О Г Х Ж П Н, если неизвестна дата его написания?

12 Задача 3 (решение) В дате первая цифра – 0,1,2 или 3 В дате первая цифра – 0,1,2 или 3 Третья – 0 или 1 Третья – 0 или 1 Выпишем возможные буквы

13 Задача 3(решение) Т П И Ё Р Ж Е М А А С Ф С Г Ь О Г Х Ж П Н С О З Е П Ё Д Л Я Я Р У Н В Ы Н В Ф Ё О М Р Н Д О Е Г К Ю П Т П Б М Б У Е Н П М Г Н Д В Й Э О С О А Л А Т Д М Л В М Г И Ь Н Р Я К Я С Л Л В М Г И Ь Н Р Я К Я С Л К Б Л В З Ы М П Ю Й Ю Р К К Б Л В З Ы М П Ю Й Ю Р К Й А К Б Ж Ъ Л О Э И Э П Й Й А К Б Ж Ъ Л О Э И Э П Й И Я Й А Ё Щ К Н Ь З Ь О И И Я Й А Ё Щ К Н Ь З Ь О И З Ю Ч Я Е Ш Й М Ы Ж Ы Н З З Ю Ч Я Е Ш Й М Ы Ж Ы Н З Ж Э З Ю Д Ч И Л Ъ Ё Ъ М И Ж Э З Ю Д Ч И Л Ъ Ё Ъ М И

14 Задача 4 Сообщение на русском языке, состоящем из 63 букв и восклицательного знака, зашифровано с использованием так называемой «поворотной решетки», которая представляет собой трафарет, изготовленный из квадратного листа клетчатой бумаги 8 на 8. В трафарете вырезаны 16 клеток. Одна сторона трафарета помечена. При наложении трафарета на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причем каждая клетка оказывается под вырезом ровно один раз.

15 Задача 4 (продолжение) Буквы сообщения построчно сверху вниз и слева направо вписываются в вырезы трафарета (пробелы между словами игнорируются). После заполнения всех вырезов буквами сообщения трафарет располагается в следующем положении и т.д. Результат зашифрования сообщения представлен на рисунке. Найдите исходное сообщение Буквы сообщения построчно сверху вниз и слева направо вписываются в вырезы трафарета (пробелы между словами игнорируются). После заполнения всех вырезов буквами сообщения трафарет располагается в следующем положении и т.д. Результат зашифрования сообщения представлен на рисунке. Найдите исходное сообщение

16 Задача 4 (продолжение)

17 Задача 4 (решение)

18 Задача 4 (ответ) смещениетрафарет смещениетрафарет авшифреповоротна авшифреповоротна ярешеткапозволяе ярешеткапозволяе тпрочитатьтекст! тпрочитатьтекст! Смещение трафарета в шифре поворотная решетка позволяет прочитать текст! Смещение трафарета в шифре поворотная решетка позволяет прочитать текст!

19 Задача 5 В здании находится восемь серверов. Они расположены в вершинах куба. Эти серверы объединены в сеть, причем два сервера соединены линией связи "напрямую" в том и только том случае, когда они соответствуют двум соседним вершинам куба. Кроме того, два из этих серверов соединены дополнительно по радиоканалу. В здании находится восемь серверов. Они расположены в вершинах куба. Эти серверы объединены в сеть, причем два сервера соединены линией связи "напрямую" в том и только том случае, когда они соответствуют двум соседним вершинам куба. Кроме того, два из этих серверов соединены дополнительно по радиоканалу.

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

21 Задача 5 (решение) Удаление ребер должно «разбить» сеть на три компоненты. Удаление ребер должно «разбить» сеть на три компоненты. Удалив 5 ребер, это легко сделать. Удалив 5 ребер, это легко сделать. Обоснование, что 4 ребрами обойтись нельзя проводится перебором по минимальному числу вершин в компоненте. Оно равно 1 или 2. Обоснование, что 4 ребрами обойтись нельзя проводится перебором по минимальному числу вершин в компоненте. Оно равно 1 или 2.

22 Задача 6 Разложить на простые множители число , если известно, что оно делится на 167. Разложить на простые множители число , если известно, что оно делится на 167.

23 Задача 6 (решение) x=3 4 x=3 4 x 5 +x+1= x 5 +x+1+x 4 -x 4 +x 3 -x 3 +x 2 -x 2 = x 5 +x+1= x 5 +x+1+x 4 -x 4 +x 3 -x 3 +x 2 -x 2 = =x 5 +x 4 +x 3 +x 2 +x+1-x 4 -x 3 -x 2 = =x 3 (x 2 +x+1)+x 2 +x+1-x 2 (x 2 +x+1)= =(x 2 +x+1)(x 3 -x 2 +1) x 2 +x+1= = = x 2 +x+1= = = =(3 4 +1) =9173=71373

24 Задача 6 (решение) x 3 -x 2 +1=x(x 2 +x+1)+x+3 x 3 -x 2 +1=x(x 2 +x+1)+x+3 x+3=84=712 x+3=84=712 x 2 +x+1 на 7 делится x 2 +x+1 на 7 делится x 3 -x 2 +1=x = x 3 -x 2 +1=x = =7( )= Ответ:

25