Страница: 1
2 3 4 5 6 >> [Всего задач: 30]
|
[Код, исправляющий ошибку]
|
|
Сложность: 3
Классы: 9,10,11
|
Предположим, что требуется передать сообщение, состоящее из n² нулей и единиц. Запишем его в виде квадратной таблици n×n.
Допишем к каждой строке сумму её элементов по модулю 2. Получится еще один столбец высоты n. Аналогично поступим с каждым столбцом (в том числе найдём и сумму элементов дописанного столбца). Например, если требуется передать сообщение 0111, то таблица 2×2 (рис. слева) окажется дополненной до таблицы 3×3 (рис. справа).
а) Докажите, что если при передаче расширенной таблицы (
n+1)×(
n+1) произойдёт одна ошибка, то эту ошибку можно
будет найти и исправить.
б) Какое наименьшее число ошибок должно произойти, чтобы об этом нельзя было узнать?
Решение
а) В расширенной таблице сумма элементов в любом столбце и в любой строке чётна. Если изменить один из элементов, то изменятся суммы для одной строки и одного столбца (станут нечётными). Чтобы исправить такую ошибку, надо будет изменить тот элемент таблицы, который находится на пересечении строки и столбца с нечётными суммами.
б) Минимальное число ошибок, которые нельзя обнаружить – 4. Например, можно изменить все четыре цифры в сообщении 0111. При этом суммы во всех строках и
столбцах останутся чётными.
Ответ
б) 4 ошибки.
|
|
|
Сложность: 3
Классы: 6,7,8
|
Цифры от 0 до 9 зашифрованы буквами A, B, C, D, E, F, G, H, I, J в каком-то порядке. За один вопрос можно узнать зашифрованную запись суммы нескольких различных букв. Например, если спросить «А + B = ?», то в случае, когда A = 9, B = 1, C = 0, ответом будет «А + В = BC». Как можно за пять таких вопросов определить, какие буквы каким цифрам соответствуют?
Решение
Сумма всех десяти цифр равна 45. Поэтому, назвав все десять букв, мы узнаем, какими буквами зашифрованы цифры 4 и 5. Исключив эти буквы и спросив про сумму остальных восьми, мы узнаем, как зашифрованы цифры 3 и 6. В каждом следующем вопросе так же будем спрашивать про сумму еще не расшифрованных букв. В результате после третьего вопроса узнаем, какими буквами зашифрованы 2 и 7, после четвёртого – 1 и 8 и, наконец, после пятого узнаем, какой из оставшихся букв зашифрована цифра 9, а какой 0.
|
|
|
Сложность: 5-
Классы: 8,9,10
|
Дима придумал секретный шифр: каждая буква заменяется на слово длиной не
больше 10 букв. Шифр называется хорошим, если всякое зашифрованное слово
расшифровывается однозначно. Серёжа убедился (с помощью компьютера), что если
зашифровать слово длиной не больше 10000 букв, то результат расшифровывается
однозначно. Следует ли из этого, что шифр хороший? (В алфавите 33 буквы, под "словом" мы понимаем любую последовательность букв, независимо от того, имеет ли она смысл.)
Решение
Предположим, что это не так: некоторые шифровки декодируются неоднозначно. Выберем самую короткую такую шифровку. По условию в ней более 10000 букв.
Назовём полусловом несколько (но не ноль и не все) первых букв слова, кодирующего букву. Ясно, что различных полуслов не больше чем
9·33 = 297.
Декодирование шифровки определяется позициями между буквами, в которых она делится на слова, кодирующие буквы. Отметим эти позиции в первом случае красным, а во втором – синим цветом (красные и синие разделители нигде не совпадают, иначе можно было бы отбросить часть шифровки до или после этих разделителей, получив более короткую "неоднозначную" шифровку). Рассмотрим для каждого красного разделителя слово, образованное этим разделителем и последним синим разделителем, стоящим перед этим красным (или началом шифровки, если таких синих разделителей нет). Ясно, что это полуслово. Какие-то два таких полуслова совпадают (шифрующих слов у нас не менее 1001, поэтому красных разделителей – не менее 1000 > 297). Значит, кусок между соответствующими красными разделителями можно выкинуть, получив новую (более короткую) "неоднозначную" шифровку. Противоречие.
Ответ
Следует.
|
|
|
Сложность: 2-
Классы: 5,6,7
|
Попробуйте
прочесть слово, изображённое на рис. 1, пользуясь ключом
(см. рис. 2).
Подсказка
Не напоминают ли вам элементы ключа уменьшенные фрагменты
основного рисунка?
Решение
Ключ показывает, какие именно стрелки отходят из того места,
где стоит буква, которую мы должны выбрать. В результате прочитывается
слово КОМПЬЮТЕР.
Ответ
КОМПЬЮТЕР.
|
|
|
Сложность: 2
Классы: 6,7,8
|
Зашифрование сообщения состоит в замене букв исходного текста на пары цифр в соответствии с некоторой (известной только отправителю и получателю) таблицей, в которой разным буквам алфавита соответствуют разные пары цифр. Криптографу дали задание восстановить зашифрованный текст. В каком случае ему будет легче
выполнить задание: если известно, что первое слово второй строки – "термометр" или что первое слово третьей строки – "ремонт"?
Подсказка
Облегчает расшифровку не длина известного слова, а набор известных букв.
Решение
Во втором случае известны пары цифр, которыми шифруются буквы из множества
{р, е, м, о, н, т}, а в первом – пары цифр для букв того же множества, за исключением буквы "н".
Ответ
Во втором.
Страница: 1
2 3 4 5 6 >> [Всего задач: 30]
Фильтр
