Заметим, что n >2 и что достаточно доказать неравенство m ≥ n для системы множеств, содержащих не менее двух элементов.
1. Система состоит не менее чем из двух множеств. Если бы система состояла из одного множества, то в силу условия 2) это множество содержало бы сразу все элементы, что противоречит условию 1).
2. Каждый элемент входит не менее чем в два множества системы. Если бы элемент входил только в одно множество, то в силу 2) оно должно было бы содержать все n элементов, что противоречит 1).
3. Один и тот же элемент не может входить сразу во все множества системы. Пусть какой-то элемент, назовем его x, входит во все множества системы. Тогда в силу условия 3) никакие два множества не содержат одинаковых элементов, за исключением элемента x. Следовательно, никакие два элемента, отличные от x, не встречаются ни в одном из множеств, но это противоречит 2).
4. Сопоставим каждому элементу число множеств системы, в которые он входит, т.е. считаем, сколько раз он повторяется в этой системе. В примере элементу a сопоставляется число 3, элементу b - 4 и т.д.
Каждому множеству системы сопоставим число элементов, которые оно содержит. В примере первому множеству сопоставляется число 2, второму – 3 и т.д.
Сумма всех чисел, соответствующих элементам, равна сумме всех чисел, соответствующих множествам. В примере 3 + 4 + 3 + 4 + 3 = 2 + 3 + 2 + 2 + 2 + 2 + 2 + 2 = 17.
В самом деле, если считать два элемента разными, когда они входят в разные множества, то обе суммы равны числу элементов всех множеств системы.
5. Обозначения. Возьмем один из тех элементов, которым соответствует наименьшее число, т.е. который входит в наименьшее число множеств системы. В примере мы можем взять либо a, либо c, либо e; возьмем a. Обозначим этот элемент через an , а число множеств, в которые он входит, через kn . В примере a5 = a, k5 = 3. В силу пп. 2 и 3 имеем 2 ≤ kn < m .
Множества, в которые входит an, обозначим в некотором порядке через A1, A2 , ... , Akn , а остальные через Akn+1 , ... , Am . В примере A1=(a, b)>, A2=(a,c,e), A3=(a,d), A4=(b,e), ... , A8=(c,d).
Рассмотрим первые kn множеств A1 , A2 , ... , Akn . Рассуждая так же, как в п.3, мы видим, что никакие два из них не содержат одинаковых элементов, за исключением an . Следовательно, мы можем взять по одному элементу каждого из этих множеств и обозначить их соответственно через a1 , a2 , ... , akn . Остальные элементы обозначим в некотором порядке через akn+1 , akn+2 , ... , an . В примере полагаем a1 = b, a2 = c, a3 = d, a4 = e; тогда A1 = (a1, a5), A2 = (a2, a4, a5, A3 = (a3, a5), A4 = (a1, a4), A5 = (a1, a2), A1 = (a1, a3), A7 = (a3, a4), A1=(a2, a3).
Теперь обозначим числа, соответствующие элементам a1 , a2 , ... , akn , ... , an-1 в том же порядке через k1 , k2 , ... , kn-1 . Напомним, что элементу an соответствует число kn , причем оно наименьшее из всех чисел k1 , k2 , ... , kn-1 , kn .
Наконец, обозначим числа, соответствующие множествам A1 , A2 , ... , Am в том же порядке через s1 , s2 , ... , skn , ... , sm .
Обратим еще раз внимание на то, как мы пронумеровали элементы и множества.
Во-первых, kn наименьшее из чисел k1 , k2 , ... , kn-1 .
Во-вторых, kn – номер последнего из множеств, в которые входит элемент an , и, таким образом, элемент an не входит в множества Akn+1 , ... , Am .
Множество Ai содержит элемент ai , но не содержит элементов aj, если 1 ≤ i ≤ kn, 1 ≤ j ≤ kn и i ≠ j . Кроме того, согласно п.4, k1 + ... + kn = s1 + ... + sm.
6. Если элемент ai не принадлежит какому-нибудь множеству Aj , то ki ≥ sj. Действительно, пусть множество Aj не содержит элемента a и состоит из sj различных элементов. Тогда элемент ai должен встретиться с каждым из этих элементов в каком-нибудь из остальных множеств системы. С другой стороны, никакие два из этих элементов не могут ни разу встретиться в этих множествах, так как они уже встречались в Aj . Следовательно, число множеств, в которые входит элемент ai, не меньше числа sj.
7. Рассмотрим первые kn множеств A1 , A2 , ... , Akn и первые kn элементов a1 , a2 , ... , akn . Они выбраны таким образом, что каждое множество Ai содержит элемент ai с тем же номером, но не содержит элементов с другими номерами, тогда, согласно п.6, s1 k2 , s2 k1 , если kn=2 и
//текст доступен после регистрации//, если kn>2.
В примере kn = 3 и
//текст доступен после регистрации//8. Складывая все неравенства, мы получаем, что
(kn - 1)(s1+s2 + ... + skn) ≤ (kn - 1)(k1 + ... + kkn)
или
s1 + s2 + ... + skn ≤ k1 + ... + kkn.
9. Теперь мы можем доказать требуемое в задаче неравенство m ≥ n .
Допустим, что m < n . Сравним две суммы
S = (s1 + s2 + ... + skn) + skn + 1 + ... + sm
и
K = (k1 + k2 + ... + kn) + kkn + 1 + ... + kn.
Заметим, что мы так перенумеровали множества, что элемент an не принадлежит множествам Akn+1 , ... , Am ; значит, skn+1 ≤kn , ... , sm ≤ kn и тем более skn+1 ≤ kkn+1 , ... , sm ≤ km , так как kn – наименьшее из всех чисел ki. В таком случае, поскольку m < n, получаем: kkn + 1 + ... + kn > skn + 1 + ... + sm, но тогда S<K , а это противоречит п.4.
Доказательство того, что m ≥ n , окончено.
P.S. Про равенство m и n написано столько же. Если интересно, то могу привести.
