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

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

Условие

Автор: Фольклор

В классе 32 ученика. Было организовано 33 кружка, причём каждый кружок состоит из трёх человек и никакие два кружка не совпадают по составу. Доказать, что найдутся такие два кружка, которые пересекаются ровно по одному ученику.


Решение 1

  Решим более общую задачу: пусть k учеников занимаются в n кружках (из трёх человек),  kn.
  Предположим противное: каждые два кружка либо не пересекаются, либо пересекаются ровно по двум ученикам. Заметим, что если кружки K и L пересекаются с кружком M, то они пересекаются и между собой (их пересечения с M имеют общий элемент). Значит, кружки разбиваются на группы пересекающихся между собой кружков. Каждой группе кружков соответствует группа учеников – объединение их составов. Эти группы также не пересекаются. Далее можно рассуждать по-разному.

  Первый способ. Поскольку кружков больше, чем учеников, в какой-то группе это неравенство также сохраняется. Поставим в соответствие каждой паре кружков этой группы пару учеников, каждый из которых ходит ровно в один из этих кружков. Пар кружков больше, чем пар учеников, поэтому какой-то паре учеников  {a, b}  соответствует по крайней мере две пары кружков  {a, c, d},  {b, c, d}  и  {a, u, v},  {b, u, v}.  Но кружки  {a, c, d}  и
{b, u, v}  не могут иметь двух общих учеников, поскольку пары  {c, d}  и  {u, v}  не совпадают. Противоречие.

  Второй способ. Если в группе, содержащей некоторый кружок  {a, b, c},  есть кружки, содержащие хотя бы две из трех пар  {a, b}, {a, c}, {b, c},  скажем кружок  {a, b, d}  и кружок  {a, c, e},  то  d = e  (два последних кружка должны иметь двух общих членов). Единственный возможный кружок, пересекающийся с каждым из этих трех по двум элементам, – это  {b, c, d}.  Таким образом, в такой группе не более четырёх кружков, куда ходят не менее четырёх учеников.
  Если же все кружки группы содержат только одну из трёх указанных пар (например,  {a, b}),  то количество кружков в ней на 2 меньше количества всех учеников, их посещающих.

  Итак, число кружков не превосходит числа учеников в классе.


Решение 2

Пусть есть k учеников и набор (не совпадающих по составу) кружков, каждый из которых посещает нечетное число учеников. Поставим в соответствие каждому кружку A  k-мерный вектор a над полем Z2 из двух элементов:  ai = 1  тогда и только тогда, когда i-й ученик посещает А. "Скалярный квадрат"
(a, a) = 1  для каждого кружка. Если же два кружка A и В пересекаются по чётному числу учеников, то соответствующие векторы a и b "ортогональны":
(a, b) = 0.  Рассмотрим набор из n кружков, каждые два из которых удовлетворяют этому условию. Тогда соответствующие векторы линейно независимы. Действительно, умножив равенство  α1a1 + ... + αnan  на  ai,  получим   αi = 0.  Значит,  n ≤ k,  то есть число кружков с попарным "чётным" пересечением не превосходит числа учеников.

Замечания

7-8 кл. – 8 баллов, 9-10 кл. – 6 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 1984/1985
Номер 6
вариант
Вариант весенний тур, основной вариант, 9-10 класс
Задача
Номер 3
олимпиада
Название Турнир городов
Турнир
Дата 1984/1985
Номер 6
вариант
Вариант весенний тур, основной вариант, 7-8 класс
Задача
Номер 3

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

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