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

XIX Межрегиональная олимпиада школьников по математике и криптографии была проведена 29 ноября 2009 года на базе следующих вузов: ИКСИ Академии ФСБ России, Бийского технологического института, Дальневосточного государственного университета (г. Владивосток), Донского государственного технического университета (г. Ростов-на-Дону), Марийского государственного технического университета, Нижегородского государственного университета, Новосибирского государственного университета экономики и управления, Иркутского государственного университета, Озерского технологического института, Омского государственного университета, Оренбургского государственного аграрного университета, Пермского государственного университета, Самарского государственного университета, Санкт-Петербургского государственного политехнического университета, Северо-Кавказского государственного технического университета (г. Ставрополь), Сибирского государственного аэрокосмического университета (г. Красноярск), Сибирского федерального университета (г. Красноярск), Томского государственного университета систем управления и радиоэлектроники, Томского государственного университета, Уральского государственного университета (г. Екатеринбург).
Участие в олимпиаде приняли более 2000 школьников. Проверка работ проводилась централизовано по единым критериям. Всего дипломами I–III степени награждено 160 участников, а еще 92 школьника отмечены поощрительными грамотами за успешное выступление на олимпиаде.
Задания олимпиады были подготовлены для каждой возрастной категории в нескольких равноценных вариантах. Далее приводятся условия и решения одной задачи каждого вида.

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

1(а). (8–9-е классы.) Подсчитать, сколько всего существует натуральных чисел, которые не превосходят число 841 и не имеют с ним общих делителей, отличных от 1.
Решение. Заметим, что 841 = 29² и 29 — простое число. Теперь нетрудно сообразить, что существует 29(29 – 1) = 812 натуральных чисел, которые не превосходят число 841 и не имеют с ним общих делителей, отличных от 1.
Ответ: 812.

1(б). (10–11-е классы.) Известно, что число N = 202 718 099 является произведением двух простых чисел p и q, а количество натуральных чисел, меньших N и взаимно простых с N, равно 202 687 920. Найти числа p и q.
Решение. Сначала заметим, что если N = pq, где p и q — простые числа, количество натуральных чисел, меньших N и взаимно простых с N, равно (p – 1)(q – 1) (это число называется функцией Эйлера и обозначается как ϕ(N)). Действительно, всего натуральных чисел, меньших N, имеется
pq – 1 штук. Из них не взаимнопросты с N те числа, которые делятся либо на p, а именно: p, 2p, ..., (q – 1)p (всего q – 1 число), либо на q, это числа q, 2q, ..., (p – 1)q (всего p – 1 число). Значит,
ϕ(N) = pq – 1 – (p – 1) – (q – 1) = pq – p – q + 1 = (p – 1)(q – 1).
Поэтому получаем систему:

По теореме Виета получаем, что p и q — решения квадратного уравнения
x2 – (N + 1 – ϕ(N))x + N = 0.
В представленной задаче N = 202 718 099,
ϕ(N) = 202 687 920, и квадратное уравнение примет вид: x2 – 30 180x + 202 718 099 = 0. Для того, чтобы извлечь квадратный корень из дискриминанта этого квадратного уравнения, равного можно заметить, что результат должен быть немного меньше, чем 10 000, причем последняя цифра в этом числе должна быть либо 2,
либо 8. Тогда претендентами будут следующие числа: 9998, 9992, 9988, 9982, ... Начинаем последовательно возводить их в квадрат, в результате сразу находим: 99982 = 99 960 004. Итак:

Ответ: 10 091 и 20 089.

2(а). (8–9-е классы.) Для зашифрования фразы был взят кубик Рубика с нанесенными на гранях русскими буквами. Развертка кубика показана на рисунке 1. Затем грани последовательно повернули по часовой стрелке на 90° определенное число раз: грань 1 — шесть раз; затем грань 2 — три раза; грань 3 — один раз; грань 4 — четыре; грань 5 — два и, наконец, грань 6 — пять раз. Затем каждая буква фразы отыскивалась на грани кубика и заменялась на букву этой же грани, которая следует за ней по часовой стрелке (так, например, для рисунка 1 буква A перейдет в букву Б, буква П — в С). Буквы, находящиеся в центре грани, не заменялись. Получилось:

ОЕХДМАПРМКПДОПИМ.

Прочтите исходное сообщение.
Решение. Заметим, если повернуть грань четыре раза, то это то же самое, что ее не поворачивать вообще, а совершение трех поворотов грани по часовой стрелке эквивалентно одному повороту против часовой стрелки. Таким образом, чтобы узнать, как были расположены буквы при шифровании, необходимо повернуть грань 1 — два раза; грань 2 — один раз (против часовой стрелки); грань 3 — один раз; грань 4 — не поворачивать; грань 5 — два и, наконец, грань 6 — один раз. Совершив такие повороты, исходя из расположения букв на полученном кубике, легко можно найти исходное сообщение, заменяя буквы шифртекста на буквы, стоящие в ячейках против часовой стрелки. Отметим, однако, что нет необходимости узнавать, куда перешли все написанные на кубе буквы. Достаточно узнать расположение букв шифртекста после описанных преобразований. После этого следует выделить ячейку, следующую против часовой стрелки за ячейкой с рассматриваемой буквой из шифртекста. Затем необходимо осуществить обратное преобразование и в выделенной ячейке на исходном кубе будет находиться соответствующая буква открытого текста (подробнее см. задачу 2(б)).
Ответ: Джероламо Кардано.

2(б). (10-й класс.) Для зашифрования фразы был взят кубик Рубика с нанесенными на гранях русскими буквами. Развертка кубика показана на рисунке 1. Три его грани повернули по часовой стрелке на 90°. При этом грань с меньшим номером поворачивалась раньше, чем грань с большим номером. Затем каждая буква фразы отыскивалась на грани кубика и заменялась на букву этой же грани, которая следует за ней по часовой стрелке (так, например, для рисунка 1 буква A перейдет в букву Б, буква П — в С). Буквы, находящиеся в центре грани, не заменялись. Известно, что перед шифрованием запятая во фразе заменялась на ЗПТ, точка – на ТЧК, а пробелы пропускались. Получилось: 
Прочтите исходное сообщение.

ЕПОЕЬРИТСГХЖЗТЯПСТАПДСБИСТЧК

Решение. Поскольку при данном способе шифрования буквы Т, Ч, К, Ф, Э, Ц не изменяются, то можно предположить, что одна из букв Т в шифрованном тексте принадлежит трехбуквенному сочетанию ЗПТ:

ЕПОЕЬРИТСГХЖЗТЯПСТАПДСБИСТЧК
            ЗПТ         ЗПТ    ЗПТ

Предположим, что это сочетание ЖЗТ. Из этого следует, что при шифровании буква З переходит в Ж, а П переходит в З. Рассмотрим все возможные варианты поворота трех граней и выделим из них те, при которых такие переходы возможны (табл. 1).
Рассмотрим первый случай: 000111, который говорит о том, что поворачивали грань 4, затем 5 и 6. Отследим движение выделенных букв исходя из такого вращения (рис. 2, первая строка). Тогда буквы З и П при шифровании будут переходить в буквы, стоящие в соответствующих отмеченных ячейках (рис. 2, вторая строка, справа). Совершая обратное преобразование, находим эти буквы. При таком движении З переходит в Ж, а П в З не переходит, о чем делаем отметку в таблице 1. Продолжаем эту процедуру для других возможных комбинаций движения и заполняем таблицу 1.

Для перехода З → Ж существует девять вариантов. Отбросим из них те, для которых невозможен переход П → З. Остается один вариант: 100011. Значит, чтобы получить кубик, на котором проводилось шифрование, необходимо один раз повернуть первую грань, пятую и шестую. Расшифровывая сообщение, получим открытый текст:

ДОЖДУСЬТЕБЯЗПТМОЕТВОРЕНЬЕТЧК.

Здесь отметим, что для других вариантов расположения ЗПТ получается либо нечитаемый текст, либо нарушаются условия перехода выделенных букв.
Ответ: «Дождусь тебя, мое творенье».

3. (8–9-е классы.) Для передачи сообщения на русском языке Крокодил Гена и Чебурашка предпринимают следующие действия. Каждый из них выбирает свою последовательность, состоящую из целых чисел в пределах от 0 до 32 с количеством чисел, равным длине сообщения. Буквы сообщения заменяются числами согласно таблице 2.

Сначала Гена шифрует сообщение, используя свою последовательность: числовое значение первой буквы сообщения и первое число его последовательности складываются, а полученная сумма заменяется остатком от деления на 33 и переводится обратно в буквенный вид согласно таблице 2. Затем эта процедура повторяется для вторых, третьих и т.д. чисел сообщения и последовательности. Полученный результат:

ЁЛИСУВШОЮЦОМЮВЫЗПЭЪМО,

передается Чебурашке. Затем Чебурашка шифрует это зашифрованное сообщение с помощью своей последовательности и передает Гене:

ЪЭЛВШРЕЭЭТЖЩЮИГВФБСЦХ.

Гена отнимает от числовых значений букв полученного сообщения числа своей последовательности (к отрицательной разнице прибавляется число 33) и передает результат Чебурашке:

ЖЪЫХЙТСЖЫАШШЬЯМЫШЗЬВГ.

Какое сообщение зашифровал Крокодил Гена?

Решение. Из условия задачи, имеется три зашифрованных сообщения:
C₁ = M + K_Г = ЁЛИСУВШОЮЦОМЮВЫЗПЭЪМО,
C₂ = C₁ + K_Ч = M + K_Г + K_Ч = ЪЭЛВШРЕЭЭТЖЩЮИГВФБСЦХ,
C₃ = C₂ – K_Г = M + K_Ч = ЖЪЫХЙТСЖЫАШШЬЯМЫШЗЬВГ,
где M — переданное открытое сообщение, K_Г — последовательность, выбранная Крокодилом Геной, K_Ч — последовательность, выбранная Чебурашкой. Тогда открытый текст можно найти следующим образом:
M = C₁ – C₂ + C₃:

Ответ: ТИШЕ ЕДЕШЬ ДАЛЬШЕ БУДЕШЬ.

4. (8–10-е классы.) Для доступа к общему почтовому ящику в интернете Катя и Юра пользуются паролем СВЕЧА. Катя решает сменить этот пароль на новый (осмысленное слово русского языка из пяти букв). Новый пароль передается по сети Юре в зашифрованном виде. Зашифрование осуществляется так: первые буквы нового и старого пароля заменяются числами согласно таблице 2, затем эти числа складываются, а полученная сумма заменяется остатком от деления на 33. Таким же образом затем поступают со вторыми буквами паролей, затем с третьими и т.д. После процедуры расшифрования Юра получил нечитаемый пароль из английских букв: SARCL. Оказалось, что программа расшифрования Юры была настроена на работу с английским алфавитом. При этом перед расшифрованием программа приводила числовые значения поступившего зашифрованного пароля и старого пароля к остаткам от деления на 26, а расшифрование заключалось в нахождении их разностей (к отрицательной разнице прибавлялось число 26), которые приводились к буквенному виду согласно таблице 3. Помогите Юре понять, какой новый пароль установила Катя.

Решение. Рассмотрим сумму полученного нового пароля SARCL и известного старого пароля СВЕЧА, от числовых значений которого взяты остатки от деления на 26, и от значений полученной суммы также возьмем остатки от деления на 26:

Таким образом, получено зашифрованное сообщение, переданное Катей и искаженное на приемном конце программой Юры. На самом деле зашифрование осуществлялось в русском алфавите, поэтому для некоторых числовых значений зашифрованного сообщения могли быть варианты:

Вычитаем теперь числовые значения старого пароля в русском алфавите 19  3  6  25  1, и возьмем от полученных разностей остатки от деления на 33:

Единственный читаемый вариант — ШАРИК.
Ответ: ШАРИК.

5. (10–11-е классы.) Торговые автоматы в Криптоландии принимают монетки номиналом только в 3 и 7 единиц. Укажите все цены, которые нельзя устанавливать на товары, продаваемые через автоматы подобного вида. Автоматы сдачу не дают.
Решение. Заметим, что 12 = 3 + 3 + 3 + 3,
13 = 7 + 3 + 3, 14 = 7 + 7. Таким образом, имеется три подряд идущих числа, которые представимы в требуемом виде. Очевидно, что все последующие числа получаются прибавлением или к 12, или к 13, или к 14 нужного числа монет достоинством 3 единицы. Остается перебором чисел от 1 до 11 найти цены, которые нельзя устанавливать.
Приведем теперь теоретическое обоснование решения задач данного типа. Фактически надо найти x, y такие, что ax + by = n (в данном случае a = 3, b = 7). Уравнение ax + by = n, в котором НОД(a; b) = 1, неразрешимо в неотрицательных целых числах x, y при
n = F(a; b) = ab – a – b и разрешимо при всех натуральных n > F(a; b) = ab – a – b.
Число F(a; b) называется числом Фробениуса для пары (a; b). В самом деле, покажем, что уравнение
ax + by = ab – a – b,
a(x + 1) + b(y + 1) = ab, ax' + by' = c
не имеет натуральных решений x', y' при c = ab и имеет такие решения при всех c > ab. Пусть при натуральных a, b, x', y' выполнено ax' + by' = ab, тогда ax' = b(a – y'), то есть x' делится на b (так как НОД(a; b) = 1 и у чисел a, b нет общих делителей, кроме 1), откуда
x' ≥ b, тогда ax' + by' > ab. Пусть
c > ab, тогда в силу условия НОД(a; b) = 1 найдутся такие натуральные u, v (по алгоритму Евклида), что au – bv = c > ab, то есть

Следовательно, найдется такое натуральное t, что
При этом t зададим натуральные числа x', y' следующим образом: x' = u – bt, y' = at – v. Тогда
ax' + by' = a(u – bt) + b(at – v) = au – bv = c.
Ответ: {1; 2; 4; 5; 8; 11}.

6. (8–9-е классы.) Дан треугольник ABC, в котором AB = 99, AC = 71, ∠ BAC = 67°. Только с помощью циркуля и линейки построить треугольник DEF со сторонами DE = 101, EF = 73 и углом между ними ∠ DEF = 51°.
Решение. Способ I. Поскольку для длин сторон AB = 99, AC = 71, НОД(99; 71) = 1 и для значений углов 67° и 360° НОД(67; 360) = 1, то по схеме алгоритма Евклида можно построить отрезок дли-
ны 1 и угол, равный 1°.
Схема алгоритма Евклида с помощью циркуля и линейки реализуется следующим образом. Сначала на большом отрезке AB последовательно от точки A засечками циркуля откладывается малый отрезок AC наибольшее возможное число раз, в данном случае — 1 раз; получается остаток длины 18. Затем на AC наибольшее число раз откладывается этот остаток, получается новый остаток и т.д. В конце концов получится остаток длины 1.
Опишем окружность произвольного радиуса с центром в точке A. Возьмем раствор циркуля, равный расстоянию между точками пересечения окружности с полупрямыми AB и AC. Этим циркулем отложим последовательно на окружности дуги, соответствующие центральному углу ∠ BAC = 67°, наибольшее возможное число раз, тем самым обнаруживается угол, равный в градусах остатку от деления 360 на 67, то есть 25°. Затем этот остаток раствором циркуля отложим наибольшее число раз на дуге, соответствующей центральному углу 67°, то есть 2 раза; получим остаток 17° и т.д. В результате получится угол, равный 1°.
Способ II. С помощью циркуля и линейки не составляет труда построить угол в 90°, а также угол в 30° и 60°, кроме того, в условии дан угол в 67°. Искомый угол в 51° может быть построен исходя из соотношения: 51° = 67° – 16°, поэтому достаточно научиться строить угол в 16°. Для этого можно заметить, что 16° = 2∙90° – 2∙67° – 30°.
Поэтому
51° = 3∙67° + 30° – 2∙90°.
Для построения отрезков длины 101 и 73 можно заметить, что:
101 = 7∙71 – 4∙99,
73 = 8∙71 – 5∙99.

7. (8–10-е классы.) Четыре фразы на русском языке записываются без знаков препинания и пробелов. Для зашифрования каждой фразы используются неизвестные последовательности цифр x1, x2, ... Буквы во фразе последовательно заменяются на пары цифр согласно таблице 2 (к одноразрядным числам слева дописывается 0: например, A будет заменяться на 01). Зашифрование состоит в преобразовании получившейся цепочки цифр по следующему правилу. К первой цифре цепочки прибавляем цифру x₁ и записываем последнюю цифру суммы, потом ко второй цифре цепочки прибавляем x₂ и также записываем последнюю цифру суммы и т.д. Результат зашифрования выглядит следующим образом:
1)
043638963711015628961406277802266891
5272874106897713780236
2)
90391397330625341592242335760114427
1609271
3)
17915094077497245567822036742365175
971
4)
37035325199253279170859097506579819
01587194945023834835000452922
Известно, что две фразы зашифрованы с помощью одной и той же последовательности. Укажите, какие именно (ответ обосновать).
Решение. Заметим, что на нечетных местах исходного текста могут появляться только цифры 0, 1, 2 и 3. Поэтому, если из одного шифртекста вычесть другой, зашифрованный с помощью той же последовательности, на нечетных местах разности могут получиться не любые цифры, а только 0, 1, 2, 3, 7, 8, 9, что будет являться критерием для выбора искомых цепочек.
Ответ: первая и вторая.

8. (10–11-е классы.) Известно, что три числа, a1, a2, a3, были получены так: сначала выбрали натуральное число A и нашли числа

где [X]₁₆ — остаток от деления целой части числа X на 16 (например, ). Затем было выбрано целое число B такое, что 0 ≤ B ≤ 15. Числа A₁, A₂, A₃ и B записывают в двоичной системе счисления, т.е. представляют каждое из них в виде цепочки из 0 и 1 длины 4, приписывая слева необходимое число нулей. Такие цепочки условимся складывать посимвольно «в столбик» без переносов в следующий разряд согласно правилу:
1 + 1 = 0 + 0 = 0 и 0 + 1 = 1 + 0 = 1, а саму операцию посимвольного сложения обозначим как . Например, 3 14 = (0011) (1110) = (1101) = 13.
Положим a₁ = A₁ B, a₂ = A₂ B, a₃ = A₃ B. Найти все возможные значения числа a₃, если известно, что a₁ = 4, a₂ = 10.
Решение. Пусть в двоичной системе счисления A = (x_n; ...; x₀). Тогда
A₁ = (x₃; x₂; x₁; x₀),
A₂ = (x₄; x₃; x₂; x₁),
A₃ = (x₅; x₄; x₃; x₂).
Следовательно,
a₁ a₂ = (A₁ B) (A₂ B) = A₁ A₂ =
= (x₃ x₄; x₂ x₃; x₁ x₂; x₀ x₁),
a₃ a₂ = (A₃ B) (A₂ B) = A₃ A₂ =
= (x₅ x₄; x₄ x₃; x₃ x₂; x₂ x₁).
Итак, если вычислить a₁ a₂, то три младших бита a₃ a₂ будут найдены, а старший бит будет произвольным.
Вычислим значение a₁ a₂:

Тогда возможные значения (a₂ a₃) имеют вид (*; 1; 1; 1), и a₃ = a₂ (a₃ a₂):

Итак, a₃ = 13 либо a₃ = 5. Можно убедиться в том, что оба варианта верны, если рассмотреть последовательности с параметрами A = 20 либо A = 52 и B = 0.
Ответ: 13 и 5.

9. (11-й класс.) Для зашифрования сообщения на русском языке, записанного без знаков препинания и пробелов, используется последовательность натуральных чисел x₁, x₂, ..., удовлетворяющая соотношению: x_k = b∙8^a(k – 1), k = 1, 2, ... Здесь a и b — фиксированные (но неизвестные) натуральные числа. Зашифрование происходит следующим образом. Первую букву сообщения заменяют числом согласно таблице 4 и складывают с x₁, потом так же заменяют вторую букву и складывают с x₂ и т.д. Затем все суммы заменяют остатками от деления на 31, а остатки заменяют буквами согласно таблице 4.
В результате получился текст:

ояфпрпяфбкпщсьижьияысязтхжутнажбсЁнфвгмнутуЁшжфн

Найти исходное сообщение, представляющее собой отрывок стихотворения, если известно, что в нем есть слово равнины.
Решение. «Двигаем» указанное в условии слово по шифрованному тексту. При правильном расположении после вычитания слова из фрагмента шифрованного текста получим значения, образующие геометрическую прогрессию, от членов которой взяты остатки от деления на 31 (табл. 5). Кроме того, последовательность этих значений имеет период 5 в силу того, что остаток от деления числа 8⁵ = (2⁵)³ = 32³ на 31 равен 1, и это свойство легко обнаружить.

Ответ: морозноравниныбелеютподснегомчернеетсялесвпереди: b = 2,
a = 1, период последовательности равен 5.

10. (11-й класс.) Все 16 городов Криптоландии в качестве названий имеют различные четырехразрядные комбинации, состоящие из нулей и единиц (например, «0011»). Все города попарно соединены непересекающимися дорогами, причем проезд из одного города в другой стоит столько криптов, в скольких разрядах различаются их имена (например, из «0011» в «1001» — 2 крипта). Путешественник, находящийся в «0000», хочет объехать все города страны и вернуться назад за минимальную цену. Как ему это сделать?
Решение. Одно из возможных решений указано в таблице 6. Номеру поездки соответствует город прибытия. Для того, чтобы такая таблица соответствовала решению, все комбинации, состоящие из четырех цифр, каждая из которых равна либо 0, либо 1, должны быть перечислены и последовательные комбинации должны отличаться в одном разряде.

Поясним способ построения маршрута. В шаге с 0 по 7 перечисляются в специальном порядке все комбинации длины 3 (подкомбинации) с приписанным слева нулем, а в шагах с 8 по 15 — те же самые комбинации, но с приписанной единицей и в обратном порядке. В шаге 16 возвращаемся в начальную точку маршрута. Перечисление подкомбинаций строится итеративно.

11(а). (11-й класс.) Найти число решений системы уравнений

при всех возможных значениях параметра a.
Решение. Приведем геометрическое решение данной задачи.
1. Рассмотрим графики линий, задаваемых системой уравнений при a > 0 (рис. 3):

Отсюда видно, что при a > 0 система может иметь одно, два, три или четыре решения.
Ровно три решения система имеет при тех a > 0, при которых луч y = 2 – ax, x > 0, проходит через точку B(1; 0), то есть при a = 2.
При a > 2 луч y = 2 – ax, x > 0, пересекает линию | y | = 1 – x в двух точках. Поэтому в данном случае система имеет ровно четыре решения.
При 0 < a < 2 луч y = 2 – ax не пересекает линию | y | = 1 – x. Поэтому в данном случае система имеет одно или два решения. Два решения получаются пересечением луча
y = 2 – a| x |, x < 0, и линии | y | = 1 – x в двух точках. Это может быть, если луч
y = 2 – a| x |, x < 0, имеет угловой коэффициент (который равен a) больший, чем 1.
Итак, при 1 < a < 2 система имеет ровно два решения.
Если же 0 < a ≤ 1, то система имеет одно решение.
2. Рассмотрим графики линий, задаваемых системой уравнений при a < 0 (рис. 4).

Отсюда видно, что при a < 0 система может не иметь решений или иметь одно решение.
Система не имеет решений при тех a < 0, при которых луч y = 2 – a| x |, x < 0, не пересекает линию | y | = 1 – x, то есть при a ≤ –1.
При –1 < a < 0 луч y = 2 – a| x |, x < 0, пересекает линию | y | = 1 – x ровно в одной точке. Поэтому в данном случае система имеет ровно одно решение.
3. При a = 0 система, очевидно, имеет ровно одно решение, а именно (–1; 2).
Ответ: при a ≤ –1 — нет решений; при –1 < a ≤ 1 — одно решение; при 1 < a < 2 — два решения; при a = 2 — три решения; при a > 2 — четыре решения.

11(б). (11-й класс.) Изобразить на плоскости Oxy множество всех точек с координатами (x; y) таких, что y ≥ x² – 1 и при любом значении параметра a выполняется неравенство
a²y + 2ax – y – 2 ≤ 0.
Ответ обосновать.
Решение. Первое неравенство задает область внутри параболы y = x2 – 1. Рассмотрим второе неравенство a2y + 2ax – y – 2 ≤ 0. Для того, чтобы данное неравенство выполнялось при фиксированных (x; y) для всех значений параметра a, необходимо и достаточно выполнение условий:

Этот вывод можно сделать, если рассмотреть многочлен a2y + 2ax – y – 2 как квадратный трехчлен относительно a с коэффициентами, зависящими от x, y.
В результате имеем систему условий:

Множество всех точек на плоскости Oxy с координатами (x; y), удовлетворяющими этой системе условий, указано на схематическом рисунке (рис. 5, заштрихованная область):

Зязин А.