Задача 73647

Темы:    [ Линейная и полилинейная алгебра ] [ Числовые таблицы и их свойства ] [ Линейные зависимости векторов ]

Сложность: 5 Классы: 10,11

Условие

В таблице размером m×n записаны числа так, что для каждых двух строк и каждых двух столбцов сумма чисел в двух противоположных вершинах образуемого ими прямоугольника равна сумме чисел в двух других его вершинах. Часть чисел стёрли, но по оставшимся можно восстановить стёртые. Докажите, что осталось не меньше чем  (n + m – 1)  чисел.

Решение

  Таблицы, удовлетворяющие условию задачи, образуют линейное пространство.
  Укажем  n + m – 1  линейно независимых таблиц: таблицы A_k1  (k = 2, 3, ..., m),  где k-я строка заполнена единицами, а остальные элементы равны нулю; таблицы A_il  (l = 2, 3, ..., n – 1),  где l-й столбец заполнен единицами, а остальные элементы равны нулю, и таблица A₁₁, у которой  a₁₁ = 1,  a_1j = 0,  a_i1 = 0  при  i, j > 1  и  a_ij = –1  при  i, j > 1  (см. рис.).

  Пусть числа, стоящие в некоторых s клетках, определяют таблицу однозначно. Заметим, что только у нулевой таблицы в указанных s клетках стоят нули. Действительно, если бы нашлась ненулевая таблица B, у которой в наших s клетках стояли бы нули, то было бы можно восстановить не только некоторую таблицу A, но и таблицу  A + B.
  Докажем, что любые  s + 1  таблиц  A₁, A₂, ..., A_s+1  линейно зависимы. Рассмотрим наборы чисел, стоящих в этих таблицах на указанных местах, как векторы a_i в s-мерном пространстве. Поскольку их  s + 1,  то они линейно зависимы, то есть найдутся такие числа  λ₁, λ₂, ..., λ_s+1,  не все равные нулю, что у таблицы  A = λ₁A₁ + λ₂A₂ + ... + λ_s+1A_s+1  во всех наших клетках стоят нули. Как показано выше,  A = 0.
  Следовательно,  s ≥ n + m – 1.

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

журнал
Название	"Квант"
год
Год	1971
выпуск
Номер	11
Задача
Номер	М112