Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
6. Указания и решения1.1. Все клетки квадрата размера 1.2. Легко видеть, что (см. скан) Ответ: ТАКДЕРЖАТЬ 1.3. Ответ: начиная с 54. 1.4. Разложим числа то и образом, искомое число упорядоченных пар совпадает с числом всех делителей Ответ: 16 пар (пары 1.5. Из последней строчки легко заметить, что
Из средней строки ясно, что
Далее, последовательно вычисляем значения: Ответ: ШИФРЗАМЕНЫ 1.6. Ответ: например, Обозначим
В общем случае можно показать, что множество искомых наборов состоит из слов вида:
2.1. Рассмотрим один виток ленты на развертке цилиндра (разрез по горизонтальной линии). По условию высота Ответ: чтобы прочитать текст, надо разрезать ленту на участки по
Рис. 8. 2.2. Согласно условию, исходное сообщение состоит из двух пятерок цифр: Пусть
Обозначим символом смысл. Если Из соотношений (4), (5), (9) и (10) находим соответственно:
Подставляя эти значения в равенства (11) и (12), получим следующие равенства:
Подставив X из (17) и из (18) в (1), (2),(3), (13), (14), (6), (7), (8), (15), (16), найдем выражения для цифр исходного сообщения:
Найденные выражения дают два варианта исходных сообщений:
2.3. Ответ: а — любое, b - не должно делиться на 2 и на 5. Указание. Обозначим через
где Отсюда, пользуясь свойствами остатков, замечаем, что 2.4. Обозначим через Если среди чисел Если среди чисел 2.5. Если две буквы с порядковыми номерами Представим в виде набора порядковых номеров известные шифрованные сообщения (обозначим их соответственно (см. скан) Возможны 15 вариантов (номер варианта обозначим буквой к) расположения слова КОРАБЛИ в каждом из двух исходных сообщений Вначале для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 1 найдем соответствующий участок и. с. 2. Имеем: (см. скан) Поэтому для участка и. с. 2 получаем следующие 15 вариантов: (см. скан) Теперь для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 2 найдем соответствующий участок и. с. 1. Имеем: (см. скан) Поэтому для участка и. с. 1 получаем следующие 15 вариантов: (см. скан) Заменим порядковые номера в найденных вариантах участков и. с. 1 и и. с. 2 на буквы русского алфавита. Получаем следующие таблицы: (см. скан) (см. скан) Из таблиц видно, что осмысленными являются варианты:
Естественно предположить, что в первом исходном сообщении речь идет об отплытии кораблей. Предположив, что неизвестным участком первого исходного сообщения является подходящая по смыслу часть слова ОТПЛЫВАЮТ, находим неизвестную часть второго исходного сообщения: слово ОТХОДЯТ. 2.6. Каждую букву шифрованного сообщения расшифруем в трех вариантах, предполагая последовательно, что соответствующая буква шифрующей последовательности есть буква (см. скан) Выбирая из каждой колонки полученной таблицы ровно по одной букве, находим осмысленное сообщение НАШКОРРЕСПОНДЕНТ, которое и является искомым. Замечание. Из полученной таблицы можно было найти такое исходное сообщение как
которое представляется не менее осмысленным, чем приведенное выше. А если предположить одно искажение в шифрованном сообщении (скажем, в качестве 11-й буквы была бы принята не буква
Число всех различных вариантов исходных сообщений без ограничений на осмысленность равно 3.1. Если каждый из 993 абонентов связан с 99 абонентами, то для этого потребуется Ответ: нельзя. 3.2. Несложно заметить, что рассматриваемый шифр обладает тем свойством, что при зашифровании разные буквы заменяются разными. Следовательно, при зашифровании разных слов получаются разные слова. С другой стороны, одинаковые буквы заменяются на одинаковые независимо от цикла шифрования, так как используется один и тот же ключ. Следовательно, при зашифровании одинаковых слов получаются одинаковые слова. Таким образом, число различных слов, которые можно получить в указанном процессе шифрования с начальным словом СРОЧНО, совпадает с наименьшим номером цикла шифрования, дающем это начальное слово. Так как буква С повторяется в каждом цикле шифрования, номер которого кратен 5, а буквы Ответ: 2730. 3.3. Если символы одного отрезка занумеровать последовательно числами от 1 до 12, то после передачи его из (см. скан) Поскольку в пунктах КРИПТОГРАФИЯ и места одинаковых символов в отрезках, находим, что слово КРИПТОГРАФИЯ зашифровано во втором отрезке. Это дает возможность найти исходное сообщение, используя гипотезы о частых буквах русского языка и смысле исходного сообщения. Ответ: (см. скан) 3.4. Докажем, что 20 является периодом рассматриваемой последовательности. Заметим, что у двух натуральных чисел
где каждое из слагаемых делится на 2 (так как содержит произведение
делится на 10, так как каждое из слагаемых делится на 10. Проверим, что 20 является наименьшим периодом. Выписывая первые 20 значений последовательности
легко убедиться, что она не имеет периода меньшей длины. 3.5. Для того, чтобы найти исходное сообщение, найдем сначала цифровое сообщение, полученное из него с помощью таблицы замены. Согласно этой таблице на нечетных местах цифрового образа исходного сообщения могут быть только цифры 0, 1, 2 и 3. Последовательно рассматривая эти значения для каждого нечетного места цифрового сообщения с использованием соответствующей цифры шифрованного сообщения, найдем соответствующие варианты значений цифр шифрующего отрезка. Для этого вычислим остатки от деления разностей цифр шифрованного и варианта цифрового сообщений: (см. скан) По задаче 3.4 последовательность, из которой выбран шифрующий отрезок, является периодической с периодом 20. Из таблицы вариантов значений цифр шифрующего отрезка видим, что 5-я его цифра может быть равна (см. скан) 3.6. Обозначения понятны из рис. 9. (см. скан)
Рис. 9. (см. скан) Замечание: Точки Ответ: 4.1. Исходный текст состоит из 48 букв, следовательно, при зашифровании было использовано три положения решетки полностью и еще три буквы вписаны в четвертом положении. Значит, незаполненные 12 клеток совпадают с вырезами решетки в четвертом положении. Так как (см. скан) текст вписывается последовательно, то неизвестные нам три выреза могут располагаться только в первой строке таблицы и первых пяти клетках второй строки (до первого известного выреза). Считаем, что трафарет лежит в четвертом положении. Учитывая, что в одну клетку листа нельзя вписать две буквы, получаем, что вырезы могут быть только в отмеченных знаком Очевидно, что из отмеченных в первой строке двух клеток вырезается только одна (так как они совмещаются поворотом). Получаем два возможных варианта решетки (либо первый Ответ: ПОЛЬЗУЯСЬШИФРОМРЕШЕТКАНЕЛЬЗЯОСТАВЛЯТЬПУСТЫЕМЕСТА 4.2. Один из вариантов решения состоит из следующих этапов. (см. скан) Получили текст: (см. скан) Получили текст: (см. скан) (см. скан) Итак, (см. скан) Ответ: Бегают по лесу стаи зверей — Не за добычей, не на водопой: Денно и нощно они егерей Ищут веселой толпой. 4.3. Ответ: 4.4. Занумеруем буквы латинского алфавита последовательно числами от 1 до 24. Пусть
Это означает, что соседние числа Ответ: INTER ARMA SILENT MUSAE (интер арма сйлент музэ — когда гремит оружие, музы молчат). 4.5. Составим возможные варианты переданных букв: (см. скан) Выбирая вторую и последнюю группу букв (где есть короткие колонки букв), определяем слова, им соответствующие: Из нескольких вариантов, например, в третьей группе: ГНОЙ ГНОМ ГРОМ выбираем варианты так, чтобы каждая буква использовалась один раз. Продолжая таким образом, получим ответ. Ответ: БЫК ВЯЗ ГНОЙ ДИЧЬ ПЛЮЩ СЪЁМ ЦЕХ ШУРФ ЭТАЖ 4.6. Заметим, что Ясно, что при расшифровании так же, как и при зашифровании, вместо чисел
где (см. скан) Заключительный этап представлен в таблице: (см. скан) 4.7. Ответ:
5.1. Указание. Найдите допустимые варианты для остатков от деления неизвестных х и у на 7. Таких вариантов будет восемь. Учитывая принадлежность неизвестных к заданному диапазону, найдите допустимые варианты для (х,у) (19 вариантов). Для каждой пары 5.2. Так как при записывании сообщения в таблицу пробелы опускались, можно сделать вывод, что столбцы, содержащие пробел в последней клетке, до перестановки стояли в конце таблицы. Таким образом, столбцы можно разбить на две группы, как показано на рис. 10. При этом для получения исходного текста потребуется переставлять столбцы только внутри групп.
Рис. 10. Естественно предположить, что сообщение оканчивалось точкой. Поэтому на третьем с конца месте в первой группе должен быть столбец, оканчивающийся на
Рис. 11.
Рис. 12. Таким образом, удалось зафиксировать последние три столбца первой группы. Переставляя столбцы второй группы, ищем «читаемые» продолжения зафиксированных столбцов (рис. 11). Действуя далее аналогичным образом с оставшимися столбцами первой группы, достаточно легко получаем исходное сообщение. Ответ: (см. скан) 5.4. Во втором случае известны пары цифр, которыми шифруются буквы Ответ: во втором случае легче. 5.5. Ответ: 481. 5.6. Можно заметить, что последовательность букв
На основе этого наблюдения можно предположить, что шифрование заключается в следующем. В каждый промежуток между буквами исходного сообщения (начало и конец также считаются промежутками) вставляются одна либо две буквы в соответствии с известным только отправителю и получателю ключом. Очевидно, что первая буква сообщения должна попасть на 2-е или 3-е место шифрованного текста. Сравнивая буквы, стоящие на указанных местах в подлежащих расшифрованию криптограммах, делаем вывод, что одно и то же исходное сообщение соответствует первому и третьему шифртексту и что первая буква этого сообщения — Рассуждая далее аналогичным образом, заключаем, что второй буквой повторяющегося сообщения является О (сопоставили ПОВТОРЕНИЕМАТЬУЧЕНИЯ Теперь расшифруем вторую криптограмму. Первой буквой сообщения могут быть только С или И. Далее, подбирая к каждой из них возможные варианты последующих букв и вычеркивая заведомо «нечитаемые» цепочки букв, получим:
(см. скан) В итоге получим исходное сообщение СМОТРИВКОРЕНЬ. Ответ: 1,3 — ПОВТОРЕНИЕМАТЬУЧЕНИЯ 2 — СМОТРИВКОРЕНЬ 5.7. Обратив внимание на то, что некоторые символы в тексте условий задач пятой олимпиады набраны выделенным шрифтом, и выписав эти символы в порядке их следования, получаем текст:
6.1. Так как каждый из 1997 абонентов связан ровно с N другими, то общее число направлений связи равно Докажем, что для каждого 6.2. Покажем, что на диагонали присутствуют все числа от 1 до 1997. Пусть число а Всего на диагонали 1997 клеток, поэтому каждое число из множества 6.3. Ответ: ШЕСТАЯОЛИМПИАДАПОКРИПТОГРАФИИПОСВЯЩЕ Указание. Пусть некоторая буква а при зашифровании первым способом заменялась на букву (3. Тогда количество повторов буквы (3 в первой криптограмме будет равно числу повторов буквы а во второй криптограмме. 6.4. а) Определим моменты остановок после начала шифрования. Для этого каждой букве русского алфавита припишем ее порядковый номер: (см. скан) Искомый шифртекст: 515355128523864354 б) Пусть
Тогда, учитывая, что начальное положение стрелок соответствует букве А на первом колесе и 0 на II и III колесах, справедливы равенства
для подходящих неотрицательных целых чисел Заметим, что
Подставляя эти значения в равенства (1) и (2), получим
Следовательно,
Правая и левая части делятся на 70, то есть имеют вид
Подставляя
Учитывая условие (см. скан) 6.5. Указание. Рассмотрим некоторую расстановку ненулевых цифр на окружности. Упорядоченную пару Каждой расстановке ненулевых цифр на окружности однозначно соответствует цепочка
Если из цепочки Если из цепочки Удаление из
Таким образом, при наличии двух указанных в условии задачи цифровых текстов нам будут известны некоторые Ответ: для однозначного восстановления расстановки цифр на окружности необходимо и достаточно, чтобы в одном из цифровых текстов было не менее 7 ненулевых цифр (это соответствует удалению из цепочки 6.6. Последовательность остатков от деления чисел
Кроме того, 6.7. Ответ: Указание. При а 0 рассматриваемое уравнение равносильно При
Ситуация недопустима, ибо при выходе из строя узлов Вот два примера, удовлетворяющие условиям задачи с 15-ю линиями связи:
Приведем доказательство для первого примера. Если вышли из строя два узла на одном пятиугольнике, то связь сохранится через другие пятиугольники. Если вышли из строя по одному узлу на разных пятиугольниках, то связь сохранится по линиям, соединяющим эти пятиугольники. Ответ: 15. 7.2. Процедура зашифрования может быть полностью описана квадратной таблицей Обозначим через (см. скан) Очевидно, что в строке с номером 2 в последней клетке стоит 1. Знание этой таблицы позволяет однозначно расшифровать Ответ: полностью можно расшифровать только 5393511, получится 5830829. 7.3. Сообщение состоит из (см. скан) Соседние буквы при перестановке переходят в буквы, отстоящие друг от друга на одинаковое расстояние: буква на (см. скан) Из трех вариантов начала текста легко определяется истинный вариант. Ответ: ЧТОБЫПОЛУЧИТЬПЯТЬНУЖНООТЛИЧНОЗНАТЬПОЛУЧИЛОСЬНЕПЛОХО 7.4. Последовательность обхода доски показана на рисунке: (см. скан) Ответ: Кавалергардов век недолог И потому так сладок он. Труба трубит, откинут полог 7.5. Из однородности всех членов следует, что неравенство эквивалентно неравенству Пусть с — минимальное из чисел
Находим минимум квадратного трехчлена с параметром с и положительным коэффициентом при 7.6. Если мелом с квадратным сечением нарисовать на доске отрезок прямой так, чтобы стороны сечения были параллельны краям доски, то площадь полученной линии будет равна площади ступенчатой линии с такими же концами (см. рис. 13). Если на доске нарисовать некоторый (выпуклый) многоугольник, то найдутся такие граничные «точки» этого многоугольника, которые являются ближайшими к одному из краев доски. Площадь границы прямоугольника, содержащей все такие «точки», равна площади границы нарисованного выпуклого многоугольника (см. рис. 14).
Рис. 13.
Рис. 14. Такой прямоугольник назовем окаймляющим. Ясно, что площадь окаймляющего прямоугольника не меньше площади соответствующего многоугольника. Значит, для любого многоугольника данной площади найдется прямоугольник такой же площади, но с площадью границы не большей, чем площадь границы исходного многоугольника. Если многоугольник со сторонами
Минимум достигается в случае, когда возводимое в квадрат выражение равно 0. В этом случае Ответ: квадрат со стороной 7.7. Если группа цифр, из которой образуются числа, состоит из к цифр, то существует ровно используются все цифры группы ровно по одному разу. Группу из к цифр будем обозначать Поскольку в сообщении отсутствуют цифры 2 и 9, эти цифры образуют либо две группы по одной цифре, либо одну группу из двух цифр. В обоих случаях эти цифры могут быть использованы для зашифрования ровно двух букв алфавита. Так как
(см. скан) Сообщение после расшифрования имеет вид: а) Если (см. скан) Сообщение легко прочитать: НАУКА. Литература к главе 7(см. скан)
|
1 |
Оглавление
|