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

Проект МЦНМО
при участии
школы 57
Задача 73647
Темы:    [ Линейная и полилинейная алгебра ]
[ Числовые таблицы и их свойства ]
[ Линейные зависимости векторов ]
Сложность: 5
Классы: 10,11
В корзину
Прислать комментарий

Условие

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


Решение

  Таблицы, удовлетворяющие условию задачи, образуют линейное пространство.
  Укажем  n + m – 1  линейно независимых таблиц: таблицы Ak1  (k = 2, 3, ..., m),  где k-я строка заполнена единицами, а остальные элементы равны нулю; таблицы Ail  (l = 2, 3, ..., n – 1),  где l-й столбец заполнен единицами, а остальные элементы равны нулю, и таблица A11, у которой  a11 = 1,  a1j = 0,  ai1 = 0  при  i, j > 1  и  aij = –1  при  i, j > 1  (см. рис.).

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

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

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

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

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