Главная страница «Первого сентября» • Главная страница журнала «Математика» • Содержание №8/2009

XVIII Межрегиональная олимпиада школьников по математике и криптографии

XVIII Межрегиональная олимпиада школьников по математике и криптографии прошла 23 ноября 2008 г. на базе Института криптографии, связи и информатики (г. Москва), Донского государственного технического университета (г. Ростов-на-Дону), Железногорского филиала Сибирского государственного аэрокосмического университета, Нижегородского государственного университета, Новосибирского государственного университета экономики и управления, Озерского технологического института, Пермского государственного университета, Самарского государственного университета, Северо-Кавказского государственного технического университета (г. Ставрополь), Северской государственной технологической академии, Сибирского государственного аэрокосмического университета (г. Красноярск), Сибирского федерального университета (г. Красноярск), Томского государственного университета систем управления и радиоэлектроники, Томского государственного университета, Уральского государственного университета (г. Екатеринбург).

Участие в олимпиаде приняли 1512 школьников. Проверка работ проводилась централизованно, по единым критериям. Всего дипломами награждены 66 участников, а еще 36 школьников отмечены поощрительными грамотами за успешное выступление на олимпиаде.

Задания олимпиады были подготовлены для каждой возрастной категории в нескольких равноценных вариантах. Ниже приводятся условия и решения задач — по одной каждого вида.

Все задачи олимпиады были решены кем-либо из участников. В категории 9-х и 11-х классов победителями были решены все предложенные задачи.

Очередную олимпиаду по математике и криптографии планируется провести в ноябре 2009 г. С задачами всех прошедших олимпиад и их решениями можно ознакомиться:

на сайте www.cryptolymp.ru;
в книге «Введение в криптографию», 3-е либо 4-е издания (М.: МЦНМО, 2000, 2002);
в книге «Олимпиады по криптографии и математике для школьников» (М.: МЦНМО, 2006).

Условия и решения задач

Задача 1. (8–9-е классы.) Цепочка ПТИУААМДЛ получена перестановкой букв в некотором слове. Имеется последовательность цифр, задающая порядок, в котором надо выписать буквы цепочки для получения исходного слова. Каждая цифра записывалась в прямоугольный шаблон размера 5 на 3 пикселей по образцу:

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

Восстановите исходное слово и перехваченную перестановку.

Решение. Исходя из характера стертых пикселей, нетрудно восстановить возможную перестановку, которой соответствуют варианты слов.

Ответ: слово — АМПЛИТУДА, перестановка — (571932486) или (671932485).

Задача 2. (8–10-е классы.) Осмысленная фраза на русском языке записана два раза подряд без пробелов и знаков препинания и зашифрована шифром Виженера. Зашифрование состоит в следующем. Выбирается ключевое слово, например мир. Для изменения первой буквы шифруемого сообщения создается таблица следующего вида:

Табл. 1

В нижней строке алфавит циклически сдвинут влево так, чтобы первая буква ключевого слова м оказалась под буквой а. Буква открытого текста (например, п) отыскивается в верхней строке и заменяется стоящей под ней буквой (для п — это ь).
Для зашифрования второй буквы аналогичным образом используется буква и, третьей — р, четвертой — вновь м и т.д. Cообщение было зашифровано с использованием ключевого слова из пяти букв. Результат зашифрования выглядит так:

мхлщлифцбдюгишсптаивпбьдюолдьуэюыйемхл

Восстановите исходное сообщение и ключевое слово.

Решение. Убеждаемся, что шифрованный текст имеет длину 38. Осмысленная фраза имеет тогда длину 19. Выписываем друг под другом известные 5 первых знаков второй и первой половины шифрованного текста и находим разность позиций соответствующих букв.

Если x₁x₂x₃x₄x₅ — ключевое слово, то при первом шифровании использовалось оно само, а при втором — слово x₅x₁x₂x₃x₄. Таким образом, найденные разности равны соответственно x₅ – x₁, x₁ – x₂, x₂ – x₃, x₃ – x₄, x₄ – x₅. Тогда при известной первой букве x₁ остальные вычисляются по формулам: x₅ = x₁ + 22, x₄ = x₁ + 14, x₃ = x₁ + 17, x₂ = x₁ + 6. Перебирая 33 варианта для буквы x₁, получаем 33 варианта ключевого слова, среди которых находится единственное осмысленное слово: КРЫША. При расшифровании получаем текст:

В Е Р Б Л Ю Д Ы И Д У Т Н А С Е В Е Р
В Е Р Б Л Ю Д Ы И Д У Т Н А С Е В Е Р.

Задача 3. (8–10-е классы.) На космической станции, состоящей из отсеков (круглых комнат) и соединяющих их коридоров, произошел сбой электроснабжения, в результате чего связь с роботом, работающим на станции, прервалась. После восстановления работы станции выяснилось, что движение по коридорам, половина из которых оказались неосвещенными, возможно только по направлениям, указанным на схеме, и занимает 1 минуту для каждого коридора. При этом неизвестно, в каком отсеке находится робот. Робот управляется командами из нулей и единиц, при этом 0 соответствует движению по освещенному коридору, а 1 — по неосвещенному. Передайте команду роботу, которая приведет его из любой комнаты в лабораторию, где находится выход. С момента начала движения робота его энергоснабжения хватит не более, чем на 5 минут.

Решение. Одним из возможных способов решения поставленной задачи будет нахождение путей длины не более 5, ведущих ИЗ заданной вершины (лаборатории, вершины № 3), то есть куда и по каким коридорам за 5 шагов можно попасть из этой вершины, двигаясь ПРОТИВ стрелок. Сначала из нее можно попасть в вершины № 8 и № 2, и движение возможно только лишь по неосвещенным коридорам. Из вершин № 8 и № 2 ведут пути только по неосвещенным коридорам в вершины № 7, № 5 и № 1, № 6 и т.д. Это приводит к построению дерева, приведенного на рисунке. Остается перебрать 6 вариантов, считывая последовательности справа налево. Истинный вариант: 01011 (выделен жирным).

Задача 4. (8–11-е классы.) В бесконечной последовательности цифр 2, 0, 0, 8, 0, 8, 6... каждая цифра, начиная с пятой, равна младшему разряду суммы четырех предыдущих цифр. Докажите, что в этой последовательности вновь встретятся подряд идущие цифры 2, 0, 0, 8.

Решение. Последовательность состоит из цифр от 0 до 9. Так как число четверок (a; b; c; d) таких цифр конечно (и равно 10 000), то в последовательности рано или поздно встретятся две повторяющиеся четверки. Пусть они встретились на i-м и j-м местах, 0 £ i < j. Если i = 0, то все доказано. Пусть i > 0. (Сейчас доказано, что последовательность периодическая. Но нужно еще доказать, что она чисто периодическая.)

Закон рекурсии:

u_i + 4= r₁₀(u_i_+ 3+ u_i_+ 2+ u_i_+ 1+ u_i), (1)

где r₁₀— остаток от деления на 10. Заметим, что по заданным четырем членам последовательности можно однозначно восстановить предыдущий член. Другими словами, если u_i_+ 4, u_i_+ 3, u_i_+ 2, u_i_+ 1 известны, то существует единственное u_i, для которого выполняется рекуррентное соотношение (1). Поэтому если в последовательности совпали четверки на местах i и j, то совпадут четверки и на местах i – 1 и j – 1. И т.д. Поэтому совпадут четверки на местах 0 и j – i. Что и требовалось доказать.

Задача 5. (8–9-е классы.) Для наблюдения за страной Криптоландией запущен разведывательный спутник. Страна Криптоландия имеет форму прямоугольника. При этом спутник находится на расстоянии 700 км от одной вершины прямоугольника, на расстоянии 330 км от противоположной вершины прямоугольника и на расстоянии 650 км от третьей вершины прямоугольника. Найдите расстояние от спутника до четвертой вершины прямоугольника.

Решение. Решим задачу в общем виде. Пусть дана четырехугольная пирамида, основанием которой является прямоугольник. При этом расстояние от вершины пирамиды до одной вершины основания равно a, расстояние от вершины до противоположной вершины основания равно b, а расстояние до третьей вершины основания равно c. Найти длину четвертого бокового ребра d. Рассмотрим проекцию вершины пирамиды на основание — точку Р.

Пусть расстояние от точки P до сторон прямоугольника AB, BC, CD, AD равно x, y, z, v соответственно. Пусть также h — высота пирамиды. Тогда имеем следующие равенства для определения длин боковых ребер пирамиды:

x² + y² + h² = a²,
v² + z² + h² = b²,
y² + z² + h² = c².

Длина четвертого (неизвестного) бокового ребра d выражается равенством

x² + v² + h² = d².

Из этих четырех равенств нетрудно получить равенство

a² + b² = c² + d²,

то есть d² = a² + b² – c². Осталось подставить в полученное выражение известные значения a, b, c и найти d = 420 км.

Задача 6. (8–10-е классы.) Число n представляется в виде произведения двух чисел: n = p q. Найдите эти числа и приведите решение, если известно:

а) что n = 40 003 200 063, а | p – q | = 2;

б) n = 40 000 398 401, а p, q — простые и | p – q | ≤ 100.

Решение. а) p = x – 1, q = x + 1,

40 003 200 063 =x² – 1, x² = 40 003 200 064.

Нетрудно заметить, что

40 003 200 064 = (200 000 + z)² и z {1; 2; ...; 9}(небольшое).

Число 40 003 200 064 заканчивается на 64, следовательно z = 8.

Ответ: p = 200 007, q = 200 009.

б) Представим p = x – t, q = x + 1, где x, t — натуральные. Тогда n = x² – t², x² = n + t². Легко заметить, что t не превосходит 50 и Из представленных чисел определяем целую часть корня а именно
Это число увеличивается на единицу и возводится в квадрат (первый кандидат на x²) и из полученного вычитается число n (кандидат для t²). Проверяем, извлекается ли квадратный корень; он извлекается сразу же для первого кандидата и равен 40:

То есть x = 200 001, t = 40, откуда получаем ответ.

Ответ: p = 199 961, q = 200 041.

Примечание. Идея разложения числа в произведение двух простых, используемая в пункте б), принадлежит Ферма (т.п. метод Ферма). Составители задачи постарались подсказать ее участникам условие пункта а). Несколько решений были проведены именно по этой схеме. Впрочем, одному из школьников 8-го класса удалось провести разложение планомерным подбором делителей, проведя все необходимые вычисления «вручную» в черновике.

Ответ: p = 199 961, q = 200 041.

Задача 7. (8–11-е классы.) Делится ли число

Решение. Число вида 2^k – 1 делится на 3 тогда и только тогда, когда k четно, на 5 — тогда и только тогда, когда k кратно 4, на 7 — тогда и только тогда, когда k кратно 3, а на 11 — тогда и только тогда, когда k кратно 10. Показатель степени

2²⁰⁰⁷ + 3²⁰⁰⁸ – 2009 делится 4; он делится на 3, так как

2²⁰⁰⁷ + 3²⁰⁰⁸ – 2009 =
= (2²⁰⁰⁷ – 2006) + (3²⁰⁰⁸ – 3) = = (2²⁰⁰⁷ – 2 – 2004) + (3²⁰⁰⁸ – 3) =
= 2(2²⁰⁰⁶ – 1 – 1002) + (3²⁰⁰⁸ – 3),

где 2²⁰⁰⁶ – 1 – 1002 делится на 3. Поэтому в соответствии с первыми тремя критериями N делится на 3, 5 и 7. Числа 3²⁰⁰⁸ и 2²⁰⁰⁷ в десятичной записи оканчиваются на 1 и 8 соответственно, поэтому 2²⁰⁰⁷ + 3²⁰⁰⁸ – 2009 делится на 10. Таким образом, число делится на 35711 = 1155.

Ответ: да, делится.

Задача 8. (11-й класс.) Для зашифрования сообщения на русском языке его записывают в одну строку без пробелов и знаков препинания. Заглавные буквы заменяются на строчные. В получившейся цепочке буквы нумеруются слева направо 1, 2, ..., L. Зашифрование происходит путем перестановки букв исходной цепочки по следующему правилу. Фиксируем два натуральных числа a и b. Буква с номером n в исходной цепочке должна в зашифрованной цепочке иметь номер, равный остатку от деления числа an + b на L (с одним исключением: если aжn + b нацело делится на L, то остаток полагается равным L). Например, если длина цепочки L = 25 и a = 9, b = 11, то третья буква исходной цепочки будет тринадцатой в зашифрованной цепочке (так как 93 + 11 = 38, а число 38 дает остаток 13 при делении на 25). Известно, что в результате применения этого метода зашифрования к цепочке из 43 букв

светитнезнакомаязвездасновамыоторваныотдома

была получена цепочка

таытоеонсоовзмевтрадазедвмаянтоаысзаимнонвк

При этих же значениях a, b проведено зашифрование еще некоторой цепочки из 38 букв. Получилось вот что:

видхьврлмаояооаоддсемдроиввоеозтообнзо

Найдите значения a и b и восстановите исходное сообщение.

Решение. Для начала найдем в открытом тексте две уникальные буквы (по возможности близкие). Это, например, К и Я, стоящие соответственно на 12-й и 16-й позициях в открытом тексте. В шифрованном тексте они стоят соответственно на 43-й и 28-й.

Составляем систему уравнений

Вычитая, получаем уравнение 4a = 28 + 43m, при m = 0 находим a = 7, из первого уравнения находим b = 2.

Расшифровав второй текст, получим:

морозвоеводадозоромобходитвладеньясвои
Задача 9. (11-й класс.) На кодовом замке имеется круглый диск с риской. Вокруг диска нанесены числа от 0 до 99 по часовой стрелке. Для управления замком служат две кнопки: «вправо» и «влево». При нажатии на кнопку «вправо» диск вращается на 43 деления по часовой стрелке, при нажатии на кнопку «влево» — на 20 делений против часовой стрелки. Каждая из этих операций выполняется за 1 секунду. Изначально замок установлен на число 0. Замок открывается при его установке на число 50 — ключ замка.

а) За какое наименьшее время можно открыть замок при данном ключе 50?

б) Докажите, что замок можно открыть при любом ключе (ключ — число от 1 до 99).

в) За какое наименьшее время можно гарантированно открыть замок при любом ключе?

Решение. а) При нажатии u раз на кнопку «вправо» и v раз на кнопку «влево» замок установится на деление с номером r₁₀₀(43u – 20v), где r₁₀₀ означает остаток от деления на 100. Таким образом, нужно подобрать числа u, v такие, что r₁₀₀(43u – 20v) = 50.

Далее понятно, что достаточно подобрать число u, для которого r₁₀₀(43u) = 10, 30, 50, 70, 90, так как после этого замок можно установить на ключ 50, вычитая 20 несколько раз.

Будем действовать перебором: 43, 86, 129, 172, 215, 258, 301, 344, 387, 430. Значит, 10 вправо, 4 влево, всего 14 секунд. Как видно из сделанного перебора, меньше чем за 14 секунд не получится.

б) Продолжим перебор, показывающий, на какие деления можно установить замок только кнопкой «вправо»: 0, 43, 86, 129, 172, 215, 258, 301, 344, 387, 430, 473, 516, 559, 602, 645, 688, 731, 774, 817, 860. Далее кнопкой «влево» можно уменьшать эти числа на 20. Поэтому, чтобы можно было открыть замок при любом ключе, достаточно, чтобы среди перечисленных чисел встречались все остатки от деления на 20. Непосредственно видно, что это так. Следовательно, замок можно открыть при любом ключе.

в) Нужно найти u, v такие, что r₁₀₀(43u – 20v) = k,
где k — ключ. Если u ³ 20, то можно уменьшить u на 20 следующим образом:

43u – 20v = 43(u – 20) – 20(v – 43).

Следовательно, кнопку «вправо» имеет смысл жать не более 19 раз. При этом получим все остатки от деления на 20, как видно и из перебора, сделанного в б). Затем кнопку «влево» жмем не более 4 раз, так как 5ж20 = 100 и за 5 раз диск сделает полный оборот.
Таким образом, в выражении r₁₀₀(43u – 20v) = k числа u, v заключены в пределах 0 ≤ u ≤ 19,
0 ≤ v ≤ 4. Всего 19 + 4 = 23 секунды.

Задача 10. (11-й класс.) Решите при всех значениях параметра a уравнение

x⁴ + 2x³ – 4x² – 2(a + 1)x – (a – 3)(a + 1) = 0.

Решение. Рассмотрим данное уравнение как уравнение второй степени относительно переменной a. При этом коэффициенты уравнения будут зависеть от x:

a² + (2x – 2)a – (x⁴ + 2x³ – 4x² – 2x + 3) = 0.

Решим это уравнение и получим, что

Полученные равенства позволяют разложить исходное выражение на множители

(a + x² + 2x – 3)(a – x² + 1) = 0.

Это позволяет свести решение исходного уравнения к решению двух уравнений меньшей степени.

1. x² + 2x + a – 3 = 0.

Дискриминант уравнения равен 16 – 4a. Значит:

при a > 4 данное уравнение не имеет решений;

при a = 4 данное уравнение имеет единственное решение x = – 1;

при a < 4 данное уравнение имеет два решения:

2. x² – (a + 1) = 0.

Дискриминант уравнения равен 4 + 4a. Значит:

при a < –1 данное уравнение не имеет решений;

при a = –1 данное уравнение имеет единственное решение x = 0;

при a > –1 данное уравнение имеет два решения:

Осталось объединить полученные ответы. Для этого необходимо дополнительно заметить, что

при a = 0

при a = 3

а при остальных значениях параметра a числа попарно различны.

Ответ: при a < –1 уравнение имеет два решения: при a = –1 уравнение имеет три решения: x = 0 и при a = 0 уравнение имеет три решения: x = –1, x = –3, x = 1; при a = 3 уравнение имеет три решения: x = –2, x = 0, x = 2; при a = 4 уравнение имеет три решения: x = –1, при –1 < a < 0, при 0 < a < 3 и при 3 < a < 4 уравнение имеет четыре различных решения: при a > 4 уравнение имеет два решения:

11. (11-й класс.) При каких значениях параметра a уравнение

4(4a – 1)x² + 2(4a + 1)(x² + 1)x + (a + 1)(x² + 1)² = 0

имеет ровно четыре различных решения?

Решение. Поскольку x² + 1 не обращается в ноль, то можно разделить обе части уравнения на выражение (x² + 1)². Получим уравнение

Сделаем замену переменных Во-первых, рассмотрев график функции (или любым другим стандартным способом), можно сделать выводы:

минимальное значение величины равно –1 (при x = –1), максимальное значение величины равно 1 (при x = 1);
множество значений величины имеет вид [–1; 1];
для любого c (–1; 0) (0; 1) уравнение имеет ровно два решения;
для c {–1; 1; 0} уравнение имеет единственное решение.

Теперь решим уравнение

(4a – 1)y² + (4a + 1)y + (a + 1) = 0.

Нам необходимо найти значения параметра a, при которых данное уравнение имеет ровно два решения, лежащие в множестве (–1; 0) (0; 1). (Только при таких условиях исходное уравнение будет иметь четыре решения.)

1. Если a = –1, то данное уравнение имеет решения y = 0. В этом случае исходное уравнение имеет три решения. Кроме того, при a ≠ –1 значение y = 0 не является решением уравнения.