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

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

Условие

24 студента решали 25 задач. У преподавателя есть таблица размером 24×25, в которой записано, кто какие задачи решил. Оказалось, что каждую задачу решил хотя бы один студент. Докажите, что
  а) можно отметить некоторые задачи "галочкой" так, что каждый из студентов решил чётное число (в частности, может быть, нуль) отмеченных задач;
  б) можно отметить некоторые из задач знаком "+", а некоторые из остальных – знаком "–" и приписать каждой задаче некоторое натуральное число баллов так, чтобы каждый студент набрал поровну баллов за задачи, отмеченные знаками "+" и "–".

Решение

  Зададим числа aij  (1 ≤ i ≤ 24,  1 ≤ j ≤ 25)  следующим образом: aij равно 1, если i-й студент решил j-ю задачу, и 0, если нет. Мы должны доказать, что существуют такие целые числа xj  (1 ≤ j ≤ 25),  не все равные нулю, что
    a1,1x1 + a1,2x2 + ... + a1,25x25 = 0,
    a2,1x1 + a2,2x2 + ... + a2,25x25 = 0,
        ...
    a24,1x1 + a24,2x2 + ... + a24,25x25 = 0,
  Из теории линейных систем известно, что если число уравнений меньше числа неизвестных, то однородная система имеет нетривиальное решение. Более того, так как коэффициенты нашей системы рациональны, то она имеет нетривиальное решение в рациональных числах. Если мы умножим все эти числа на общее кратное знаменателей, то получим решение в целых числах.

  а) Первый способ. Пусть уже найден набор целых чисел xj, удовлетворяющих системе из б). Можно считать, что не все xj чётные, иначе разделим все числа на 2. Заменим все чётные числа xj на 0, а нечётные – на 1, и отметим задачи, которым соответствует единица. Ясно, что каждая сумма     осталась чётной (поскольку каждое слагаемое изменено на чётное число). Поэтому каждый студент решил чётное число отмеченных задач.
  Второй способ. Для каждого из 2n подмножеств множества задач сопоставим цифру 1 тем студентам, которые решили нечётное число задач и 0 – тем, кто решил чётное число задач из этого подмножества. Таким образом, каждому подмножеству A мы поставим в соответствие столбец "высоты" m из нулей и единиц. Различных столбцов "высоты" m всего  2m < 2n. Следовательно, найдутся два разные подмножества A и B, которым соответствует одинаковые столбцы. Отметим теперь те задачи, которые входят ровно в одно из множеств A и B, то есть задачи из множества
A Δ B.
  Поскольку у каждого студента число решённых задач из A и B имеют одинаковую чётность, то в  A Δ B  количество решённых им задач чётно (оно равно сумме чисел решённых задач из A и B минус удвоенное число решённых задач из  A ∩ B).

Замечания

Утверждения задачи верны во всех случаях, когда количество задач больше количества студентов.

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

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

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

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