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

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

Условие

В таблице из n столбцов и 2n строк, в которых выписаны все возможные различные наборы из n чисел 1 и –1, некоторые числа заменены нулями. Докажите, что можно выбрать некоторое непустое подмножество строк так, что:
  а) сумма всех чисел в выбранных строках равна 0;
  б) сумма всех выбранных строк есть нулевая строка.
(Строки складываются покоординатно как векторы.)


Решение

  а) Первый способ. См. б).
  Второй способ. Индукция по n. База  (n = 1)  очевидна.
  Шаг индукции. Рассмотрим исходную таблицу A размера 2n×n и испорченную таблицу B, полученную из A заменой некоторых чисел нулями. Заметим, что если в какой-то строке таблицы B встречаются как единицы, так и минус единицы, то их число можно уменьшить, заменив одну единицу и одну минус единицу нулями. При этом сумма чисел в строке не изменится, поэтому на справедливость доказываемого утверждения это не повлияет. Поэтому можно считать, что в таблице B нет строк с числами разных знаков.
  Возьмём таблицу A' размера  2n–1×(n–1)  из всевозможных векторов размерности  n – 1  с координатами ±1. Построим по ней испорченную таблицу B'.
  Каждой строке a таблицы A' соответствуют две строки  (a, 1)  и  (a, –1)  в таблице A. Из них получены две строки  (b, δ)  и  (b', –ε)  в таблице B, где δ, ε равны 0 или 1. В таблицу B' вместо a впишем строку b'', полученную по следующему алгоритму.
  1)  δ = 0.  Тогда  b'' = b.
  2)  δ = 1,  ε = 0.  Тогда  b'' = b'.
  3)  δ = ε = 1.  Тогда  b'' = b + b'.  Мы вправе это сделать, поскольку в строке b нет минус единиц, в строке b' нет единиц, значит, строка
b + b'  может быть получена из a вписыванием нулей. Заметим, что в этом случае  (b, δ) + (b', –ε) = (b'', 0).
  Итак, в любом случае сумма чисел в строке b'' по построению равна сумме чисел в одной или двух соответствующих строках таблицы B.
  По предположению индукции из построенной страницы B' можно выбрать несколько строк, общая сумма чисел в которых равна нулю. Но тогда и общая сумма чисел в соответствующих строках таблицы B равна нулю.

  б) См. задачу 107820.

Замечания

баллы: 4 + 5

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

олимпиада
Название Турнир городов
Турнир
Дата 1995/1996
Номер 17
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 6
журнал
Название "Квант"
год
Год 1996
выпуск
Номер 3
Задача
Номер М1550

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

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