К задачам седьмой олимпиады

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

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

Вот два примера, удовлетворяющие условиям задачи с 15-ю линиями связи:

Приведем доказательство для первого примера. Если вышли из строя два узла на одном пятиугольнике, то связь сохранится через другие пятиугольники. Если вышли из строя по одному узлу на разных пятиугольниках, то связь сохранится по линиям, соединяющим эти пятиугольники.

Ответ: 15.

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

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

	0	1	2	3	4	5	6	7	8	9
0									5
1			3
2	4	3	7					8
3		7
4			2
5									3
6
7						4
8			1	9
9

	0	1	2	3	4	5	6	7	8	9
0			6						5
1			3
2	4	3	7	0	6	2	5	8	9
3	3	7
4			2
5									3	7
6
7						4
8			1	9
9			1

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

Ответ: полностью можно расшифровать только 5393511, получится 5830829.

Сообщение состоит из буквы. Поэтому или (при и - получается нечитаемый текст). При не получается осмысленного текста при всех шести возможных вариантах перестановки букв (, ). Рассмотрим случай :

Соседние буквы при перестановке переходят в буквы, отстоящие друг от друга на одинаковое расстояние: буква на -м месте переходит на место, определяемое остатком от деления на 17, а буква на -м месте - на место, определяемое остатком от деления на 17. Это верно для любого . Поэтому есть всего 16 вариантов переходов соседних букв (исходный текст нечитаем), которые определяют однозначно переходы всех остальных букв. Перебирая их, получаем нечитаемые тексты во всех случаях, кроме одного, который дает текст:

Из трех вариантов начала текста легко определяется истинный вариант.

Ответ:

ЧТОБЫПОЛУЧИТЬПЯТЬНУЖНООТЛИЧНОЗНАТЬПОЛУЧИЛОСЬНЕПЛОХО

Последовательность обхода доски показана на рисунке:

Ответ:

Кавалергардов век недолог

И потому так сладок он.

Труба трубит, откинут полог...

Из однородности всех членов следует, что неравенство эквивалентно неравенству 1/4$" width="181" height="33" > при условии , 0$" width="42" height="28" >, 0$" width="40" height="29" >, 0$" width="40" height="28" >.

Пусть - минимальное из чисел (. Тогда

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

Если мелом с квадратным сечением нарисовать на доске отрезок прямой так, чтобы стороны сечения были параллельны краям доски, то площадь полученной линии будет равна площади ступенчатой линии с такими же концами (см. рис. ).

Если на доске нарисовать некоторый (выпуклый) многоугольник, то найдутся такие граничные ``точки'' этого многоугольника, которые являются ближайшими к одному из краев доски. Площадь границы прямоугольника, содержащей все такие ``точки'', равна площади границы нарисованного выпуклого многоугольника (см. рис. ).

Рис. 20.

Рис. 21.

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

Если многоугольник со сторонами и имеет площадь 10000 см, то площадь его границы равна

Минимум достигается в случае, когда возводимое в квадрат выражение равно 0. В этом случае , что влечет . Таким образом, наименьшую площадь границы, равную 404 см, имеет квадрат со стороной 1 м.

Ответ: квадрат со стороной 1 м; площадь его границы - 404 см.

Если группа цифр, из которой образуются числа, состоит из цифр, то существует ровно различных чисел, для записи которых используются все цифры группы ровно по одному разу. Группу из цифр будем обозначать .

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

Так как , то

.

Если , то из сообщения находим:

а) , , либо

б) , , .

	Случай а	Случай б		Случай а	Случай б		Случай а	Случай б
А	2 (4)	0	К	1738	1738	Х	7183	7183
Б	4 (29)	2 (29)	Л	1783	1783	Ц	7318	7318
В	9 (56)	9 (92)	М	1837	1837	Ч	7381	7381
Г	56 (65)	456	Н	1873	1873	Ш	7813	7813
Д	65 (92)	465	О	3178	3178	Щ	7831	7831
Е	506	546	П	3187	3187	Ъ	8137	8137
	605	564	Р	3718	3718	Ы	8173	8173
Ж	650	645	С	3781	3781	Ь	8317	8317
З	650	654	Т	3817	3817	Э	8371	8371
И	1378	1378	У	3871	3871	Ю	8713	8713
Й	1387	1387	Ф	7138	7138	Я	8731	8731

<

Сообщение после расшифрования имеет вид: а) ЯАЗЧ или б) ЯДАЧ, т.е. не читается.

Если , то из сообщения находим ,

. В этом случае таблица замены букв числами имеет вид:

А	1		465	Л	783	С	4560	Ч	5460	Э	6450
Б	2(29)	Ж	546	М	837	Т	4605	Ш	5604	Ю	6504
В	9(92)	З	564	Н	873	У	4650	Щ	5640	Я	6540
Г	378	И	645	О	4056	Ф	5046	Ъ	6045
Д	387	Й	654	П	4065	Х	5064	Ы	6054
Е	456	К	738	Р	4506	Ц	5406	Ь	6405

Сообщение легко прочитать: НАУКА.

Next: ...к задачам восьмой олимпиады

Up: 7.6. Указания и решения

Previous: ...к задачам шестой олимпиады

Contents:

ЗАРОЖДЕНИЕ КРИПТОГРАФИИ

К задачам шестой олимпиады

Так как каждый из 1997 абонентов связан ровно с другими, то общее число направлений связи равно . Отсюда общее число связанных пар абонентов равно , так как каждая связанная пара имеет ровно 2 направления связи. Поскольку число должно быть целым, а число 1997 - нечетное, то число должно быть четным.

Докажем, что для каждого существует система связи из 1997 абонентов, в которой каждый связан ровно с другими. В самом деле, расположив всех абонентов на окружности и связав каждого из них с ближайшими к нему по часовой стрелке и с ближайшими к нему против часовой стрелки, получим пример такой сети связи.

Покажем, что на диагонали присутствуют все числа от 1 до 1997. Пусть число не стоит на диагонали. Тогда, в силу симметрии таблицы, число встречается четное количество раз. С другой стороны, так как число по одному разу встречается в каждой строке, всего в таблице чисел нечетное количество (1997). Получили противоречие.

Всего на диагонали 1997 клеток, поэтому каждое число из множества

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

Ответ: 1995003.

Ответ: ШЕСТАЯОЛИМПИАДАПОКРИПТОГРАФИИПОСВЯЩЕНАСЕМИДЕСЯТИ

ПЯТИЛЕТИЮСПЕЦИАЛЬНОЙСЛУЖБЫРОССИИ

Указание. Пусть некоторая буква при зашифровании первым способом заменялась на букву . Тогда количество повторов буквы в первой криптограмме будет равно числу повторов буквы во второй криптограмме.

а) Определим моменты остановок после начала шифрования. Для этого каждой букве русского алфавита припишем ее порядковый номер: А - 0, Б - 1, и т.д. Тогда буквам из шифруемого слова будут соответствовать номера: О - 15, Л - 12, И - 9, М - 13, П -16, А - 0, Д - 4. Моменты остановок будем указывать числом одношаговых (на один зубец) поворотов I колеса до соответствующей остановки.

# остановки	1	2	3	4	5	6	7	8	9
Буква I колеса	О	Л	И	М	П	И	А	Д	А
Число одношаговых поворотовот начала до остановки	15	45	75	79	82	108	132	136	165
Цифра II колеса	5	5	5	1	8	2	8	4	5
Цифра III колеса	1	2	5	2	5	3	6	3	4