ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60648
Темы:    [ Криптография ]
[ Четность и нечетность ]
Сложность: 3
Классы: 9,10,11
Название задачи: Код, исправляющий ошибку.
В корзину
Прислать комментарий

Условие

Предположим, что требуется передать сообщение, состоящее из n² нулей и единиц. Запишем его в виде квадратной таблици n×n. Допишем к каждой строке сумму её элементов по модулю 2. Получится еще один столбец высоты n. Аналогично поступим с каждым столбцом (в том числе найдём и сумму элементов дописанного столбца). Например, если требуется передать сообщение 0111, то таблица 2×2 (рис. слева) окажется дополненной до таблицы 3×3 (рис. справа).

  а) Докажите, что если при передаче расширенной таблицы  (n+1)×(n+1)  произойдёт одна ошибка, то эту ошибку можно будет найти и исправить.
  б) Какое наименьшее число ошибок должно произойти, чтобы об этом нельзя было узнать?


Решение

а) В расширенной таблице сумма элементов в любом столбце и в любой строке чётна. Если изменить один из элементов, то изменятся суммы для одной строки и одного столбца (станут нечётными). Чтобы исправить такую ошибку, надо будет изменить тот элемент таблицы, который находится на пересечении строки и столбца с нечётными суммами.

б) Минимальное число ошибок, которые нельзя обнаружить – 4. Например, можно изменить все четыре цифры в сообщении 0111. При этом суммы во всех строках и столбцах останутся чётными.


Ответ

б) 4 ошибки.

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 4
Название Арифметика остатков
Тема Деление с остатком. Арифметика остатков
параграф
Номер 1
Название Четность
Тема Четность и нечетность
задача
Номер 04.022

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .