Задача 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