Наша задача может быть сформулирована следующим образом.

  Дано n различных элементов и имеется система m множеств, составленных из этих элементов, причём:

  Доказать, что  m ≥ n..

  Сначала докажем несколько простых утверждений.

  1. Система состоит не менее чем из двух множеств. Если бы система состояла из одного множества, то в силу условия 2) это множество содержало бы сразу все элементы, что противоречит условию 1).

  2. Каждый элемент входит не менее чем в два множества системы. Если бы элемент входил только в одно множество, то в силу 2) оно должно было бы содержать все n элементов, что противоречит 1).

  3. Один и тот же элемент не может входить сразу во все множества системы. Пусть какой-то элемент x входит во все множества. Тогда в силу условия 3) никакие два множества не содержат одинаковых элементов, за исключением x. Следовательно, никакие два элемента, отличные от x, не встречаются ни в одном из множеств, что противоречит 2).

  Назовём кратностью элемента число множеств системы, в которые он входит. Напомним, что число элементов множества называется его мощностью.

  4. Сумма кратностей всех элементов равна сумме мощностей всех множеств. В самом деле, если считать два элемента разными, когда они входят в разные множества, то обе суммы равны числу элементов всех множеств системы.

  Возьмём один из элементов a_n наименьшей кратности k_n. Множества, в которые входит a_n, обозначим в некотором порядке через A₁, A₂, ..., A_kn, а остальные через A_kn+1, ..., A_m.

  Рассуждая как в 3, мы видим, что никакие два из множеств A₁, A₂, ..., A_kn не содержат одинаковых элементов, за исключением a_n. Следовательно, мы можем взять по одному элементу каждого из этих множеств и обозначить их соответственно через a₁, a₂, ..., a_kn. Остальные элементы обозначим в некотором порядке через a_kn+1, ..., a_n. Кратности элементов a₁, a₂, ..., a_n–1. Мощности множеств A₁, ..., A_m обозначим через s₁, ..., s_m.

  5. Если элемент a_i не принадлежит какому-нибудь множеству A_j, то  k_i ≥ s_j.

  Действительно, пусть множество A_j не содержит элемента a. Тогда элемент a_i должен встретиться с каждым из этих элементов в каком-нибудь из остальных множеств системы. С другой стороны, никакие два из этих элементов не могут ни разу встретиться в этих множествах, так как они уже встречались в A_j. Следовательно,  k_i ≥ s_j.

  Множества A₁, ..., A_kn и элементы a₁, ..., a_kn выбраны таким образом, что каждое множество A_i содержит элемент a_i, но не содержит элементов с другими номерами. Согласно 5,  s_j ≤ k_i,  если  1 ≤ i, j ≤ k_n  и  i ≠ j.

  Складывая эти неравенства, получаем  (k_n – 1)(s₁ + ... + s_kn) ≤ (k_n – 1)(k₁ + ... + k_kn),  или  s₁ + ... + s_kn ≤ k₁ + ... + k_kn.

  Допустим, что  m < n.  Поскольку a_n не принадлежит множествам A_kn+1, ..., A_m, то согласно 5  s_kn+1 ≤ k_n, ..., s_m ≤ k_n  и тем более

s_kn+1 ≤ k_kn+1, ..., s_m ≤ k_m,  так как k_n – наименьшее из всех чисел k_i. Следовательно,   s_kn+1 + ... + s_m ≤ k_kn+1 + ... + k_n,  откуда следует, что

s₁ + ... + s_m < k₁ + ... + k_n.  А это противоречит 4.

Ответ задачи отсутствует