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

список всех олимпиад по криптографии и математике

Задача 15.1.

Докажите, что десятичная запись квадрата натурального числа не может состоять из одинаковых цифр.

Задача 15.2.

Для зашифрования текстов каждую букву заменяли парой цифр.
При этом разные буквы текста заменялись разными парами, а одинаковые - одинаковыми. Даны два зашифрованных текста:

79 92 38 98 95 91 34 95 73 77 96 92 78 95 73 98 92 96 92 72 98
96 77 72 92 34 77 96 75 90 76 95 38 98 92 70 33 90 96 79 90 96
77 98 95 90 38 77 70 70 90 98 74 92 96 98 96 77 72 92 34 77 96
75 73 77 96 92 98 74 92 79 96 90 79 92 96 98 94 90 76 98 74 92
95 96 96 92 73 79 92 33 98 95 32 92 90 93 38 92 96 73 94 90 91
96 91 73 92 98 74 95 73 33 72 96 90 34 95 73 73 91 36 71 92 33
98 98 90 77 38 92 38 72 91 73 92 96 70 95 33 92 38 33 92

71 75 74 39 74 73 74 72 30 73 74 78 33 79 98 94 78 36 79 97 72
29 78 74 96 74 92 30 38 79 70 72 94 78 79 22 92 92 79 98 37 70
92 74 94 77 74 93 31 78 74 70 39 79 71 75 94 98 70 39 97 92 72
22 23 39 78 94 70 74 76 78 94 78 78 30 77 39 94 74 75 94 39 79
38 94 70 73 79 77 79 78 39 94 75 94 70 73 75 74 76 94 39 74 96
74 76 78 74 96 79 94 39 79 71 30 27 39 79 32 71 75 74 39 74 73
74 72 74 92 71 75 94 98 35 22 92 72 22 23 39

Известно, что один из них соответствует сообщению на русском языке, а другой - на английском (в текстах строчные и заглавные буквы не различались, а пробелы и знаки препинания опускались). Определите, какой шифрованный текст соответствует сообщению на русском языке.

Задача 15.3.

При зашифровании текста на русском языке (в текстах строчные и заглавные буквы не различались, а пробелы и знаки препинания опускались) каждую букву заменяли парой цифр. При этом разные буквы текста заменялись разными парами, а одинаковые -одинаковыми. Найдите все возможные места расположения слова ПОДЪЕЗД в исходном тексте по шифрованному тексту:
92 97 36 72 97 92 70 73 97 90 97 72 38 39 74 76
97 34 79 78 97 70 76 74 72 74 73 74 76 70 70 97
76 74 96 74 37 39 75 97 70 39 74 79 39 37 71 74
98 35 94 90 98 97 94 96 74 98 74 76 97

Задача 15.4.

Центральный замок автомобиля открывается и закрывается с помощью брелка. При получении сигнала брелка замок открывается (если был закрыт) или закрывается (если был открыт). В брелке и замке имеются счетчики (назовем их СБ и СЗ), на которых изначально было выставлено одно и то же число. Пусть N - текущее значение СБ.
При нажатии на кнопку брелка СБ меняет значение на N+1, старое же значение N в зашифрованном виде передается замку. Микрокомпьютер замка расшифровывает полученный сигнал и находит число, переданное брелком. Если это число равно или превосходит значение СЗ, то замок срабатывает, а значение СЗ становится N + 1. Если это число оказывается меньше или при расшифровании обнаруживается ошибка, то замок остается в прежнем состоянии. Злоумышленник способен а) запоминать сигналы брелка, б) поставив помеху, искажать сигналы брелка (при этом сам злоумышленник получает сигнал без искажений), в) посылать замку ранее запомненные сигналы. Как злоумышленнику открыть замок? Алгоритмы шифрования и расшифрования ему неизвестны.

Задача 15.5.

Для всех $p\in(0;1)$ найдите минимальное значение выражения $(x_1+x_2)\cdot p+x_3\cdot(1-p)$ при условии, что 1) $0<x_1<1;0<x_2<1;0<x_3<1$ , 2) $x_1+x_2+x_3=1$ , 3) $x_1\le x_2;x_3\le x_2;x_2\cdot(1-p)\le x_1\cdot p$ .