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

Next: Задачи восьмой олимпиады Up: 7.5. Условия задач олимпиад Previous: Задачи шестой олимпиады Contents: Содержание

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

7.1. Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?

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

Известен список зашифрованных паролей:

4249188780319, 4245133784397, 5393511, 428540012393,
4262271910365, 4252370031465, 4245133784735

и два пароля 4208212275831, 4242592823026, имеющиеся в зашифрованном виде в этом списке. Можно ли определить какие-либо другие пароли? Если да, то восстановите их.

7.3. В результате перестановки букв сообщения получена криптограмма:

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

Прочтите исходное сообщение, если известно, что оно было разбито на отрезки одинаковой длины , в каждом из которых буквы переставлены одинаково по следующему правилу. Буква отрезка, имеющая порядковый номер ( $х=1,2,\dots,r$ ), в соответствующем отрезке криптограммы имеет порядковый номер $f(x)=ax\oplus b$ , где и - некоторые натуральные числа, $ax\oplus b$ равно остатку от деления суммы на , если остаток не равен нулю, и равно , если остаток равен нулю.

7.4. Знаменитый математик Леонард Эйлер в 1759 г. нашел замкнутый маршрут обхода всех клеток шахматной доски ходом коня ровно по одному разу. Прочтите текст, вписанный в клетки шахматной доски по такому маршруту (см. рис. 12). Начало текста в a4.

Рис. 12.

$\epsfbox{latt.6}$

7.5. При , , докажите неравенство:

$\begin{displaymath}a^3+b^3+c^3+6abc> \frac{1}{4}(a+b+c)^3. \end{displaymath}$

7.6. Для рисования на большой прямоугольной доске используется мел с квадратным сечением со стороной 1 см. При движении мела стороны сечения всегда параллельны краям доски. Как начертить выпуклый многоугольник площадью 1 м ${}^2$ с наименьшей площадью границы (площадь границы не входит в площадь многоугольника)?

7.7. Цифры 0,1,...,9 разбиты на несколько непересекающихся групп. Из цифр каждой группы составляются всевозможные числа, для записи каждого из которых все цифры группы используются ровно один раз (учитываются и записи, начинающиеся с нуля). Все полученные числа расположили в порядке возрастания и -ому числу поставили в соответствие -ую букву алфавита

АБВГДЕ $\myYo$ ЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Оказалось, что каждой букве соответствует число и каждому числу соответствует некоторая буква. Шифрование сообщения осуществляется заменой каждой буквы соответствующим ей числом. Если ненулевое число начинается с нуля, то при шифровании этот нуль не выписывается. Восстановите сообщение 873146507381 и укажите таблицу замены букв числами.