XVI олимпиадапо математике и криптографии

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

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

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

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

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

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

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

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

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

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

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

Задача № 3
Пара вида аij blm заменяется:
при i ≠ l парой bim alj ;
при i = l парой blj aim .

Задача № 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.
Определите, какой именно?

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

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

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

Задача № 4
Пусть a1, a2, a3, … и b1, b2, b3, … последовательности периодов 16 и 2006 соответственно. Найдите период последовательности
a1, b1, a2, b2, a3, b3, …
Периодом x1, x2,… называется наимень-шее натуральное число T, что для всех натуральных n верно равенство
xn+T = xn

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

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

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

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

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

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

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

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

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

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

Задача № 6

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

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

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

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

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

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

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

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

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