|
|
 |
Условие
Учащиеся одной школы часто собираются группами и ходят в кафе-мороженое. После такого посещения они ссорятся настолько, что никакие двое из них после этого вместе мороженое не едят. К концу года выяснилось, что в дальнейшем они могут ходить в кафе-мороженое только поодиночке. Докажите, что если число посещений было к этому времени больше 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+1 ≤ kn, ..., sm ≤ kn и тем более
skn+1 ≤ kkn+1, ..., sm ≤ km, так как kn – наименьшее из всех чисел ki. Следовательно,
skn+1 + ... + sm ≤ kkn+1 + ... + kn, откуда следует, что
s1 + ... + sm < k1 + ... + kn. А это противоречит 4.
Замечания
В решениях Задачника "Кванта" обсуждаются другие перефомулировки этой задачи, а также вопрос о том, когда возможно равенство m = n.
