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

Презентация:



Advertisements
Похожие презентации
Очерк «История криптографии» на примерах задач олимпиад.
Advertisements

Очерк на примерах задач олимпиад по криптографии.
§2. Определители 1. Вспомогательные определения ОПРЕДЕЛЕНИЕ. Пусть n – натуральное число. Факториалом числа n (обозначают: n!) называют произведение натуральных.
Матрицы Элементарные преобразования и действия над матрицами made by aspirin.
§2. Определители 1. Вспомогательные определения ОПРЕДЕЛЕНИЕ. Пусть n – натуральное число. Факториалом числа n (обозначают: n!) называют произведение натуральных.
МАГИЧЕСКИЙ КВАДРАТ Ученица 7а класса Шахова Анна.
1 2. Матрицы. 2.1 Матрицы и их виды. Действия над матрицами. Джеймс Джозеф Сильвестр.
Обзорный интернет-семинар Олимпиадная математика 8 класс.
§2. Определители 1. Вспомогательные определения ОПРЕДЕЛЕНИЕ. Пусть n – натуральное число. Факториалом числа n (обозначают: n!) называют произведение натуральных.
КРИПТОГРАММЫ. Криптогра́фия (от др.-греч. κρυπτός скрытый и γράφω пишу) наука о методах обеспечения конфиденциальности (невозможности прочтения информации.
Линейная алгебра Матрицы. Основные понятия. Действия над матрицами Метод обратной матрицы решения систем линейных уравнений.
К. Поляков, Программирование на алгоритмическом языке Тема 4. Циклы.
§1 МАТРИЦЫ И ОПРЕДЕЛИТЕЛИ 1.1 Матрицы и их свойства Матрицей размера m n называется совокупность mn чисел, расположенных в виде таблицы из m строк и n.
Задачи Задачи к лекции 1 Задание 1. Идет К-ая секунда суток. Определите, сколько полных часов (Н) и полных минут (М) прошло к этому моменту. (Например,
Равносоставленность Две фигуры называются равносоставленными, если они могут быть разрезаны на одинаковое число попарно равных фигур. Из свойств площади.
Двумерные массивы. В математике часто используют многомерные массивы, т.е. массивы массивов. Особенно широкое распространение получили двумерные массивы.
1. МАТРИЦЫ И СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ 1.1. Матрицы. Действия с матрицами Определение 1.1. Таблица вида: (1.1) в которой все – заданные числа, называется.
1 Измерение информации: алфавитный подход Информация и информационные процессы.
Матрицы лекция 2. Определение Матрицей размера называется прямоугольная таблица из чисел, где,, состоящая из строк и столбцов.
Мультимедийные презентации для уроков математики..
Транксрипт:

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 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 db

Задача 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 ds zq up hs bq ij db mh ps ju in ВТОРОЙ ШИФРТЕКСТ есть противоречащие свойству пары

Задача 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

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

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

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

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

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

Задача 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

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

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

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

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

Задача 6

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

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

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

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

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

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

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

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

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