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

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

Условие

Автор: Бурбаки Н.

Учащиеся одной школы часто собираются группами и ходят в кафе-мороженое. После такого посещения они ссорятся настолько, что никакие двое из них после этого вместе мороженое не едят. К концу года выяснилось, что в дальнейшем они могут ходить в кафе-мороженое только поодиночке. Докажите, что если число посещений было к этому времени больше 1, то оно не меньше числа учащихся в школе.


Решение

  Наша задача может быть сформулирована следующим образом.
  Дано n различных элементов и имеется система m множеств, составленных из этих элементов, причём:
    1) никакое множество нашей системы не содержит сразу всех элементов;
    2) каждые два из данных n элементов встречаются в одном из множеств системы;
    3) если два элемента встретилась в одном из множеств, то они не встречаются вместе ни в одном из остальных множеств системы.
  Доказать, что  m ≥ n.
.
  Сначала докажем несколько простых утверждений.
  1. Система состоит не менее чем из двух множеств. Если бы система состояла из одного множества, то в силу условия 2) это множество содержало бы сразу все элементы, что противоречит условию 1).
  2. Каждый элемент входит не менее чем в два множества системы. Если бы элемент входил только в одно множество, то в силу 2) оно должно было бы содержать все n элементов, что противоречит 1).
  3. Один и тот же элемент не может входить сразу во все множества системы. Пусть какой-то элемент x входит во все множества. Тогда в силу условия 3) никакие два множества не содержат одинаковых элементов, за исключением x. Следовательно, никакие два элемента, отличные от x, не встречаются ни в одном из множеств, что противоречит 2).
  Назовём кратностью элемента число множеств системы, в которые он входит. Напомним, что число элементов множества называется его мощностью.
  4. Сумма кратностей всех элементов равна сумме мощностей всех множеств. В самом деле, если считать два элемента разными, когда они входят в разные множества, то обе суммы равны числу элементов всех множеств системы.
  Возьмём один из элементов an наименьшей кратности kn. Множества, в которые входит an, обозначим в некотором порядке через A1, A2, ..., Akn, а остальные через Akn+1, ..., Am.
  Рассуждая как в 3, мы видим, что никакие два из множеств A1, A2, ..., Akn не содержат одинаковых элементов, за исключением an. Следовательно, мы можем взять по одному элементу каждого из этих множеств и обозначить их соответственно через a1, a2, ..., akn. Остальные элементы обозначим в некотором порядке через akn+1, ..., an. Кратности элементов a1, a2, ..., an–1. Мощности множеств A1, ..., Am обозначим через s1, ..., sm.
  5. Если элемент ai не принадлежит какому-нибудь множеству Aj, то  ki ≥ sj.
  Действительно, пусть множество Aj не содержит элемента a. Тогда элемент ai должен встретиться с каждым из этих элементов в каком-нибудь из остальных множеств системы. С другой стороны, никакие два из этих элементов не могут ни разу встретиться в этих множествах, так как они уже встречались в Aj. Следовательно,  ki ≥ sj.
  Множества A1, ..., Akn и элементы a1, ..., akn выбраны таким образом, что каждое множество Ai содержит элемент ai, но не содержит элементов с другими номерами. Согласно 5,  sj ≤ ki,  если  1 ≤ i, j ≤ kn  и  i ≠ j.
  Складывая эти неравенства, получаем  (kn – 1)(s1 + ... + skn) ≤ (kn – 1)(k1 + ... + kkn),  или  s1 + ... + skn ≤ k1 + ... + kkn.
  Допустим, что  m < n.  Поскольку an не принадлежит множествам Akn+1, ..., Am, то согласно 5  skn+1kn, ..., sm ≤ kn  и тем более
skn+1kkn+1, ..., sm ≤ km,  так как kn – наименьшее из всех чисел ki. Следовательно,   skn+1 + ... + smkkn+1 + ... + kn,  откуда следует, что
s1 + ... + sm < k1 + ... + kn.  А это противоречит 4.

Замечания

В решениях Задачника "Кванта" обсуждаются другие перефомулировки этой задачи, а также вопрос о том, когда возможно равенство  m = n.

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

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

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

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