Теорема о мощности множества, содержащего необходимое количество элементов данных конечных непересекающихся множеств



Впервые с этой темой я столкнулась на дополнительных летних занятиях по физике и математике, где мы разбирали задачи на логику и комбинаторику. На одном из занятий мы познакомились с задачами, которые учительница назвала так: «задачи на худший случай». Первая задача звучала следующим образом:

«В коробке лежат 5 красных шаров и 2 черных шара. Сколько нужно вытащить шаров, чтобы в коробке обязательно оказался 1 черный шар?»

Ответ является, если немного подумать, простым и очевидным. Для нахождения ответа необходимо найти «худший случай», то представить вариант, при котором задействовано как можно больше шаров, но притом минимальный из обязательно возможных вариантов. Если в «худшем случае» первые пять шаров мы достанем красного цвета, то шестой обязательно окажется черным. Ответ: 6 шаров.

Задачи подобного типа возможны и с большим количеством множеств. Например: «В коробке лежат 5 красных, 7 желтых и 4 черных шаров. Сколько нужно вытащить шаров, чтобы в коробке обязательно оказались 2 черных шара и 2 красных шара?»

И снова необходимо найти «худший случай», только теперь нам нужно пересмотреть большее количество вариантов. К примеру, первые 7 желтых шаров, потом 4 черных и 2 красных, или 7 желтых шаров, потом 5 красных и 2 черных. Теперь, чтобы определить подходящий случай, мы должны их сложить и выбрать большее число. В первом случае получается 13, а во втором 14, следовательно, верным является второй случай. Ответ: 14 шаров.

Теперь рассмотрим задачу, в которой будут четыре множества. «В коробке лежат 5 красных, 7 желтых, 4 черных и 10 зеленых шаров. Сколько нужно вытащить шаров, чтобы в коробке обязательно оказались 3 черных шара, 1 красный и 2 зеленых шара?».

Будем действовать тем же методом. Проверив возможные варианты, мы получим следующие результаты: 18 шаров, 25 шаров и 22 шара. Выбираем наибольшее: 25 шаров. Ответ: 25 шаров.

Разбирая подобные задачи, я предположила, что для их решения может существовать закономерность, и попыталась ее найти.

Полученные результаты я оформила в виде научно-исследовательской работы под названием «Теорема расчета случайности», моим научным руководителем была учитель информатики Лисова Елена Александровна.

В Кубанском государственном университет я познакомилась с доцентом факультета математики и компьютерных наук Кравченко Григорием Григорьевичем. Он прочитал мою научно-исследовательскую работу, результаты его заинтересовали, и Кравченко Г. Г. стал моим научным консультантом.

Он предложил мне изучить некоторые разделы математики, в частности, некоторые разделы теории множеств и метод математической индукции.

Результаты исследования были сформулированы в виде следующей теоремы:

Теорема. Пусть M₁, M₂, …, M_n — конечные непересекающиеся множества, т. е. M_i ∩ M_j = , i ≠ j.

Если множество G  M₁  M₂  …  M_n и содержит не менее p₁ элементов множества M₁, не менее p₂ элементов множества M₂, …, не менее p_n элементов множества M_n, то

|G|  |M₁| + |M₂| + … +|M_n| – min{|M₁| – p₁; |M₂| – p₂; …; |M_n| – p_n}.

Доказательство.

Доказательство проведем методом математической индукции.

Введем обозначения: |M₁| = m₁; |M₂| = m₂; …; |M_n| = m_n.

1. Рассмотрим случай n = 2.

В множество G могут попасть все элементы одного из множеств M₁ или M₂, тогда в него должно попасть p₂ элементов множества M₂или p₁ элементов множества M₁ соответственно. Следовательно, |G| ≥ max{m₁ + p₂; m₂ + p₁} = max{m₁ + m₂ – (m₂ – p₂); m₂ + m₁ – (m₁ – p₁)} = = m₁ + m₂ – min{(m₁ – p₁); (m₂ – p₂)}.

Таким образом, |G| ≥ m₁ + m₂ – min{m₁ – p₁; m₂ – p₂}.

2. Предположим, что неравенство справедливо для n = k, то есть |G| ≥ |M₁| + |M₂| + … +|M_k| – min{|M₁| – p₁; |M₂| – p₂; …; |M_k| – p_k}.
3. Покажем, что неравенство выполняется для n = k + 1.

Обозначим L = M₁  M₂  …  M_k, |L | = |M₁| + |M₂| + … +|M_k|.

Так как в множество G должно попасть не менее p₁ элементов множества M₁, не менее p₂ элементов множества M₂, …, не менее p_k элементов множества M_k, то, по индуктивному предположению, из множества L должно попасть не менее |M₁| + |M₂| + … +|M_k| – min{|M₁| – p₁; |M₂| – p₂; …; |M_k| – p_k} элементов, то есть p_L ≥ |M₁| + |M₂| + … +|M_k| – min{|M₁| – p₁; |M₂| – p₂; …; |M_k| – p_k},

Для двух множеств L и M_{k + 1} имеем:

|G| ≥ |L| + |M_k+1| – min{|L| – p_L; |M_k+1| – p_k+1}.

Отсюда получаем, что

|G| ≥ |L| + |M_k+1| – min{|L| – p_L; |M_k+1| – p_k+1} ≥

≥ |M₁| + |M₂| + … +|M_k| + |M_k+1| – min{((|M₁| + |M₂| + … +|M_k|) –

– (|M₁| + |M₂| + … +|M_k| – min{|M₁| – p₁; |M₂| – p₂;…; |M_k| – p_k}));|M_k+1| – p_k+1} ≥

≥ |M₁| + |M₂| +… +|M_k| + |M_k+1| – min{min{|M₁| – p₁; |M₂| – p₂; …; |M_k| – p_k};|M_k+1| – p_k+1} =

=|M₁| + |M₂| + … + |M_k| + |M_k+1| – min{|M₁| – p₁; |M₂| –p₂; … ;|M_k| –p_k; |M_k+1| –– p_k+1}.

Таким образом,

|G| ≥ |M₁| + |M₂| + … + |M_k| + |M_k+1| – min{|M₁| – p₁; |M₂| – p₂; …;|M_k| – p_k; |M_k+1| – p_k+1}.

Теорема доказана.

Проиллюстрируем теорему на приведенных выше примерах для трех и четырех множеств.

Пример 1.

«В коробке лежат 5 красных, 7 желтых и 4 черных шаров. Сколько нужно вытащить шаров, чтобы в коробке обязательно оказались 2 черных шара и 2 красных шара?».

Имеем:

|G|= |M₁| + |M₂| +|M₃| – min{|M₁| – p₁; |M₂| – p₂; |M₃| – p₃} =

= 5 + 7 + 4 – min{5 – 2; 7 – 0; 4 – 2} = 16 – min{3; 7;2} = 16 – 2 = 14.

Ответ совпадает с приведенным выше.

Пример 2.

«В коробке лежат 5 красных, 7 желтых, 4 черных и 10 зеленых шаров. Сколько нужно вытащить шаров, чтобы в коробке обязательно оказались 1 красный шар, 3 черных шара и 2 зеленых шара?»

Имеем:

|G|= |M₁| + |M₂| +|M₃| +|M₄| – min{|M₁| – p₁; |M₂| – p₂; |M₃| – p₃; |M₄| – p₄} =

= 5 + 7 + 4 +10 – min{5 – 1; 7 – 0; 4 – 3₃; 10 –2} = 26 – min{4; 7;1; 8} = 26 – 1 = 25.

Ответ также совпадает с приведенным выше.

Эта работа была представлена на следующих конференциях: «Обретенное поколение — Наука, Творчество, Духовность», «Шаги в науку — ЮГ», «Созидание и Творчество», где заняла первое место.

Литература:

1. Виленкин Н. Я. Комбинаторика. — М.: Наука, 1969. — 328 с.
2. Виленкин Н. Я. Индукция. Комбинаторика. Пособие для учителей. — М.: Просвещение, 1976. — 48 с.
3. Кравченко Г. Г., Иванисова О. В., Сухан И. В. Комбинаторика. — Краснодар: Кубанский государственный университет, 2015. — 138 с.
4. Шевелев Ю. П. Дискретная математика. — СПб.: Лань, 2008. — 592 с.
5. Липский В. Комбинаторика для программистов. — М.: Мир, 1988. — 213 с.