XVI олимпиада по математике и криптографии 3 декабря 2006 г. - презентация

1 XVI олимпиада по математике и криптографии 3 декабря 2006 г.

2 Число участников

3 Задача 1 Каждая буква фрагмента известного стихотворения Ф.И. Тютчева заменена некоторой буквой так, что разным буквам соответствуют разные буквы, а одинаковым - одинаковые. Пробелы и знаки препинания сохранены. Восстановите этот фрагмент стихотворения: Гьюь Фюббшн эй яюэовл, Пфзшэюь юришь эй шчьйфшвл: Г эйщ юбюрйээпо бвпвл Г эйщ юбюрйээпо бвпвл С Фюббшн ьюцэю вюылъю сйфшвл.

4 Задача 1 Гьюь Фюббшн эй яюэовл, Пфзшэюь юришь эй шчьйфшвл: Г эйщ юбюрйээпо бвпвл Г эйщ юбюрйээпо бвпвл С Фюббшн ьюцэю вюылъю сйфшвл.

5 Задача 1 (ответ) Умом Россию не понять, Аршином общим не измерить: У ней особенная стать – В Россию можно только верить.

6 Задача 2 Криптоша изобрел устройство, которое позволяет вычислить среднее арифметическое любых 9 чисел или любых 223 чисел. Криптоша изобрел устройство, которое позволяет вычислить среднее арифметическое любых 9 чисел или любых 223 чисел.

7 Задача 2 (продолжение) Как правильно использовать это устройство, чтобы найти среднее арифметическое любых 2006 чисел. При необходимости можно дополни- тельно провести одно деление и одно умножение.

8 Задача 2 (решение) Добавим к числам еще одно, равное нулю. Тогда

9 Задача 2 (решение)

10 Задача 2 (ответ)

11 Задача 3 Для зашифрования сообщения на английском языке составляются две таблицы размера 5 x 5. В клетки каждой таблицы в неизвестном порядке вписаны буквы укороченного английского алфавита (v и w отождествлены), так что каждая буква алфавита встречается в каждой таблице один раз.

12 Задача 3 Букву, расположенную в i -ой строке и j -м столбце первой таблицы обозначим через а i j, а букву второй таблицы через b i j. При зашифровании сообщение разбивается на пары подряд идущих букв.

13 Задача 3 Пара вида а ij b lm заменяется: при i l парой b im a lj ; при i = l парой b lj a im. при i = l парой b lj a im.

14 Задача 3 В результате зашифрования сообщения c r y p t o g r a p h i c a l g o r i t h m был получен один из следующих шифртекстов: p a b d g l i u r c a v t h o t u e a d s p, d s z q u p h s b q i j d b m h p s j u i n. Определите, какой именно?

15 Задача 3 (решение) Способ зашифрования текста обладает свойством: Если пара ab заменяется на пару cd, то пара dc перейдет в пару ba. a c db

16 Задача 3 (решение) ОТКРЫТЫЙ ТЕКСТ сr yp to gr ap hi ca lg or it hm рa bd gl iu rc av th ot ue ad sp ПЕРВЫЙ ШИФРТЕКСТ противоречащих свойству пар нет

17 Задача 3 (решение) ОТКРЫТЫЙ ТЕКСТ сr yp to gr ap hi ca lg or it hm ds zq up hs bq ij db mh ps ju ds zq up hs bq ij db mh ps ju in ВТОРОЙ ШИФРТЕКСТ есть противоречащие свойству пары

18 Задача 4 Пусть a 1, a 2, a 3, … и b 1, b 2, b 3, … последовательности периодов 16 и 2006 соответственно. Найдите период последовательности a 1, b 1, a 2, b 2, a 3, b 3, … a 1, b 1, a 2, b 2, a 3, b 3, … Периодом x 1, x 2, … называется наимень- шее натуральное число T, что для всех натуральных n верно равенство x n+T = x n x n+T = x n

19 Задача 4 (решение) Разобьём последовательность {x n } на пары (х 1,х 2 ), (х 3,х 4 ), … (a 1,b 1 ), (a 2,b 2 ), … Период этой последовательности пар равен c =НОК(16,2006)=16048.

20 Задача 4 (решение) При всех натуральных n верно равенство x n =x n+2с

21 Задача 4 (решение) При всех натуральных n верно равенство x n =x n+2с Покажем, что 2с – наименьшее число с таким условием.

22 Задача 4 (решение) При всех натуральных n верно равенство x n =x n+2с Покажем, что 2с – наименьшее число с таким условием. Пусть период последовательности {x} равен t. Тогда число 2c должно делиться на число t. Пусть период последовательности {x n } равен t. Тогда число 2c должно делиться на число t.

23 Задача 4 (решение) Случай 1. Пусть t нечетно. Тогда первая последовательность является «сдвигом» второй, что противоречит различию длин их периодов.

24 Задача 4 (решение) Случай 2. Пусть t четно, t =2k. Случай 2. Пусть t четно, t =2k. Тогда для всех m выполнено Тогда для всех m выполнено x 2m-1+t = x 2m-1 x 2m+t = x 2m Отсюда a m+k =a m b m+k =b m

25 Задача 4 (решение) Таким образом, k делится на НОК периодов исходных последователь- ностей. Отсюда t = 2НОК(16, 2006) =

26 Задача 5 Бильярдные шары плотно уложены в правильный треугольник с основа- нием из 2006 шаров. На каждом шаре написано число. Сумма трех чисел на шарах при вершинах исход- ного треугольника, а также любых треугольников со сторонами, парал- лельными исходному треугольнику, равна 0. Какие числа могут быть написаны на шарах?

27 Задача 5 (решение)

28 Задача 6 Заполните неокрашенные клетки таблицы числами от 1 до 9. При этом, сумма цифр в каждой горизонтальной неокрашенной цепочке должна совпадать с числом, указанным слева от цепочки, а в каждой вертикальной неокрашенной цепочке - с числом, указанным сверху от цепочки. В каждой цепочке ни одна цифра не должна повторяться.

29 Задача 6

30 Задача 6 (решение) Единственно возможное заполнение таблицы

31 Задача 6 (решение)

32 С задачами прошедших олимпиад и их решениями можно познакомиться: на сайте Академии на сайте Академии на сайте (раздел занимательная криптография) на сайте (раздел занимательная криптография) в книге «Введение в криптографию» МЦНМО, в книге «Введение в криптографию» МЦНМО, в книге «Олимпиады по криптографии и математике для школьников» в книге «Олимпиады по криптографии и математике для школьников» МЦНМО, 2006.

33 Связаться с оргкомитетом олимпиад можно по электронной почте academy.fsb.ru Подписку на рассылку информации оргкомитета можно оформить, отправив на этот адрес письмо с темой SUBSCRIBE. Тел

34 Мероприятия для школьников в 2007 году Окружной тур олимпиады по математике 28 января (воскресенье) Окружной тур олимпиады по физике 3 февраля (суббота) Региональная олимпиада по математике 25 февраля (воскресенье)

35 Мероприятия для школьников в 2007 году Победителям этих олимпиад предоставляются льготы при поступлении в ИКСИ и ряд других вузов.

36 Мероприятия для школьников в 2007 году Собеседования (для школьников 10 класса) (для школьников 10 класса) март, май по предварительной записи

37 Мероприятия для школьников в 2007 году Письменные работы по математике и физике октябрь

38 Мероприятия для школьников в 2007 году XVII Олимпиада по математике и криптографии XVII Олимпиада по математике и криптографии в конце ноября или начале декабря

39