X Олимпиада по криптографии и математике
список всех олимпиад по криптографии и математике
Задача 10.1.
Для изображения портрета Криптоши в квадратной таблице размера 15 × 15 каждую ее клетку покрасили белой или черной краской. Назовем подряд идущие клетки одного цвета строки или столбца таблицы полосой, а число клеток в полосе – ее длиной.
Восстановите изображение Криптоши по известным длинам полос черного цвета в каждой строке и в каждом столбце (следующих соответственно сверху вниз и слева направо). По строкам: 9; 11; 1, 1; 2, 3, 3, 2; 2, 2; 2, 1, 1, 1, 2; 2, 1, 2; 2, 2; 1, 5, 1; 2, 3, 2; 2, 2; 7; 1, 1; 6, 6; 1, 4, 1, 4, 1. По столбцам: 1; 5, 1; 9, 2; 2, 2, 2; 2, 1, 2, 2; 2, 1, 1, 1, 1, 2; 2, 1, 2, 3; 2, 2, 2, 1, 1; 2, 1, 2, 3; 2, 1, 1, 1, 1, 2; 2, 1, 2, 2; 2, 2, 2; 9, 2; 5, 1; 1. При этом полосы черного цвета одной строки или одного столбца не соприкасаются.
Задача 10.2.
Решите уравнение \(x^2+y^2+z^2+xy-yz+xz-5=u^2+v^2+w^2+uv-vw+uw+2u-2v+2w\), если каждое неизвестное может принимать любое из двух значений, указанных в таблице
| x | y | z | u | v | w |
| 0 | -1 | 1 | -1 | 0 | 0 |
| 1 | 2 | 2 | 0 | 3 | 1 |
Задача 10.3.
Буквы алфавита английского языка (I и J отождествлены)
ABCDEFGHIKLMNOPQRSTUVWXYZ
вписаны в клетки таблицы 5 × 5 построчно слева направо, начиная с верхней строки. При этом сначала вписано слово английского языка из 6 попарно различных букв, которое назовем ключевым словом. Затем последовательно вписаны буквы, не вошедшие в ключевое слово, в их алфавитном порядке. Для зашифрования некоторого слова с помощью этой таблицы каждую его букву заменим парой цифр. Первая цифра – номер строки, а вторая – номер столбца таблицы, содержащих эту букву. Полученную цифровую последовательность запишем в обратном порядке, а затем каждую пару цифр (слева направо) последовательно заменим буквой по той же таблице. Найдите ключевое слово, если слово HANDWRITING (почерк) зашифровано в PVMTMEDWVAH.
Задача 10.4.
www.itmathrepetitor.ru Каждое число вида xn = 1 + 2 + 3 + … + n, n ∈ N, заменим последней цифрой sn в его десятичной записи. Из последовательности s1, s2, s3, … выпишем единицу и следующие за ней цифры до тех пор, пока не встретится уже выписанная цифра. Если при этом окажется, что выписаны не все десять цифр, то все отсутствующие допишем в порядке возрастания. Полученный отрезок из 10 различных цифр назовем перестановкой. Обозначим перестановку символом pk, если ее первая цифра является k-ой по счету единицей в последовательности s1, s2, s3, …
а) Докажите, что цифровая последовательность s1, s2, s3, … является периодической, и найдите ее наименьший период.
б) Докажите, что последовательность перестановок p1, p2, p3, … является периодической, и найдите ее наименьший период.
Задача 10.5.
С целью зашифрования разобьем текст на последовательные отрезки по 10 букв. Изменим порядок букв каждого отрезка с помощью перестановок из задачи 10.4. При этом для перестановки букв в k-ом отрезке используется перестановка pk. Например, из отрезка АБВГДЕЖЗИК с помощью перестановки 1 3 4 0 5 9 6 7 8 2 получим отрезок БГДАЕКЖЗИВ.
Восстановите отрывок из книги Л. Кэррола, если после его зашифрования данным методом получен текст:
ООСХОРШКАЗЛЭНИАКОТАТТООНАРЗИСЧЗЕПОСТЕПЕНОАННИНЧАЯ
СОВАККНЧИХОТОСНИАКЧАЯЛУЫБКОЙКОТРЯЕОЩАЕБЫЛВКНААИДН
ЕООВТРОРЕЕМЯ
Задача 10.6.
Докажите, что уравнение \(x^5+5x^3+5x-1=0\) имеет один действительный корень и найдите его.