Теорема о мощности множества, содержащего необходимое количество элементов данных конечных непересекающихся множеств | Статья в журнале «Юный ученый»

Отправьте статью сегодня! Журнал выйдет 1 февраля, печатный экземпляр отправим 5 февраля.

Опубликовать статью в журнале

Автор:

Научные руководители: ,

Рубрика: Математика: алгебра и начала анализа, геометрия

Опубликовано в Юный учёный №5 (8) октябрь 2016 г.

Дата публикации: 25.07.2016

Статья просмотрена: 41 раз

Библиографическое описание:

Мацокина В. В., Лисова Е. А., Кравченко Г. Г. Теорема о мощности множества, содержащего необходимое количество элементов данных конечных непересекающихся множеств // Юный ученый. — 2016. — №5. — С. 57-60. — URL https://moluch.ru/young/archive/8/531/ (дата обращения: 24.01.2020).



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

«В коробке лежат 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 шаров.

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

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

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

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

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

Теорема. Пусть M1, M2, …, Mn — конечные непересекающиеся множества, т. е. Mi ∩ Mj = , i ≠ j.

Если множество G M1 M2 Mn и содержит не менее p1 элементов множества M1, не менее p2 элементов множества M2, …, не менее pn элементов множества Mn, то

|G| |M1| + |M2| + … +|Mn| – min{|M1| – p1; |M2| – p2; …; |Mn| – pn}.

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

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

Введем обозначения: |M1| = m1; |M2| = m2;; |Mn| = mn.

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

В множество G могут попасть все элементы одного из множеств M1 или M2, тогда в него должно попасть p2 элементов множества M2или p1 элементов множества M1 соответственно. Следовательно, |G| ≥ max{m1 + p2; m2 + p1} = max{m1 + m2(m2 – p2); m2 + m1(m1 – p1)} = = m1 + m2 – min{(m1 – p1); (m2 – p2)}.

Таким образом, |G|m1 + m2 – min{m1 – p1; m2 – p2}.

  1. Предположим, что неравенство справедливо для n = k, то есть |G| ≥ |M1| + |M2| + … +|Mk| – min{|M1| – p1; |M2| – p2; …; |Mk| – pk}.
  2. Покажем, что неравенство выполняется для n = k + 1.

Обозначим L = M1 M2 Mk, |L | = |M1| + |M2| + … +|Mk|.

Так как в множество G должно попасть не менее p1 элементов множества M1, не менее p2 элементов множества M2, …, не менее pk элементов множества Mk, то, по индуктивному предположению, из множества L должно попасть не менее |M1| + |M2| + … +|Mk| – min{|M1| – p1; |M2| – p2; …; |Mk| – pk} элементов, то есть pL |M1| + |M2| + … +|Mk| – min{|M1| – p1; |M2| – p2; …; |Mk| – pk},

Для двух множеств L и Mk + 1 имеем:

|G| |L| + |Mk+1| – min{|L| – pL; |Mk+1| – pk+1}.

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

|G| |L| + |Mk+1| – min{|L| – pL; |Mk+1| – pk+1} ≥

|M1| + |M2| + … +|Mk| + |Mk+1| – min{((|M1| + |M2| + … +|Mk|)

(|M1| + |M2| + … +|Mk| – min{|M1| – p1; |M2| – p2;…; |Mk| – pk}));|Mk+1| – pk+1} ≥

|M1| + |M2| +… +|Mk| + |Mk+1| – min{min{|M1| – p1; |M2| – p2;; |Mk| – pk};|Mk+1| – pk+1} =

=|M1| + |M2| + … + |Mk| + |Mk+1| – min{|M1| – p1; |M2| –p2; ;|Mk| –pk; |Mk+1| –– pk+1}.

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

|G| |M1| + |M2| + … + |Mk| + |Mk+1| – min{|M1| – p1; |M2| – p2; ;|Mk| – pk; |Mk+1| – pk+1}.

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

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

Пример 1.

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

Имеем:

|G|= |M1| + |M2| +|M3| – min{|M1| – p1; |M2| – p2; |M3| – p3} =

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

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

Пример 2.

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

Имеем:

|G|= |M1| + |M2| +|M3| +|M4| – min{|M1| – p1; |M2| – p2; |M3| – p3; |M4| – p4} =

= 5 + 7 + 4 +10 – min{51; 70; 4 – 33; 102} = 26 – min{4; 7;1; 8} = 26 – 1 = 25.

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

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

Литература:

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


Похожие статьи

Применение метода математической индукции к решению...

В математических олимпиадах часто встречаются достаточно трудные задачи на доказательство делимости натуральных чисел. Перед школьниками возникает проблема: как найти универсальный математический метод, позволяющий решать подобные задачи?

Решение логической задачи разными способами и сравнение их...

Данная задача трехмерная, следовательно, нужно найти соответствия между множествами

Ответ: Тамара – красные туфли, красное платье; Валя – белые туфли, голубое платье; Лида

Решение данной задачи с помощью таблицы после ее построения сразу дает наглядный ответ.

Комбинаторика. Ее изучение в школе | Статья в журнале...

Если множество состоит из элементов, а множество — из элементов, причем эти множества не имеют общих элементов, то их

Применение метода математической индукции к решению задач на... Возможно, что в целой части может оказаться одна цифра, а в дробной...

Об использовании метода инварианта, основанного на идее...

При решении некоторых математических задач применяется совокупность

Решение. Ответ: нельзя. Так как число чисел в таблице нечетно, а после каждой операции число чисел (+ 1) в таблице четно.

Применение метода математической индукции к решению задач...

Логические задачи на математических кружках в основной школе

Из условия задачи можно выделить два множества: множество оценок и множество имен. Каждое множество состоит из трех элементов.

Ответ: пистолет — синяя коробка, мишка — красная коробка, кукла — зеленая коробка, машинка — желтая коробка.

О спутниках τ-замкнутых n-кратно Ω-расслоенных формаций...

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

Обозначим через пересечение всех τ-замкнутых -расслоенных формаций, содержащих множество групп ; — пересечение всех -расслоенных формаций, содержащих и...

К вопросу о реализации решения задачи открытого...

Применение метода математической индукции к решению задач на... В математических олимпиадах часто встречаются достаточно

Ключевые слова: доминирование, доминирующее множество, число доминирования, задачи размещения, методы дискретной оптимизации...

Развитие логического мышления посредством решения...

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

О роли нестандартных задач в развитии логического мышления...

В связи с развитием наукоемких и высокотехнологичных производств в современной России повышается потребность в квалифицированных кадрах с высоким уровнем математического образования.

Похожие статьи

Применение метода математической индукции к решению...

В математических олимпиадах часто встречаются достаточно трудные задачи на доказательство делимости натуральных чисел. Перед школьниками возникает проблема: как найти универсальный математический метод, позволяющий решать подобные задачи?

Решение логической задачи разными способами и сравнение их...

Данная задача трехмерная, следовательно, нужно найти соответствия между множествами

Ответ: Тамара – красные туфли, красное платье; Валя – белые туфли, голубое платье; Лида

Решение данной задачи с помощью таблицы после ее построения сразу дает наглядный ответ.

Комбинаторика. Ее изучение в школе | Статья в журнале...

Если множество состоит из элементов, а множество — из элементов, причем эти множества не имеют общих элементов, то их

Применение метода математической индукции к решению задач на... Возможно, что в целой части может оказаться одна цифра, а в дробной...

Об использовании метода инварианта, основанного на идее...

При решении некоторых математических задач применяется совокупность

Решение. Ответ: нельзя. Так как число чисел в таблице нечетно, а после каждой операции число чисел (+ 1) в таблице четно.

Применение метода математической индукции к решению задач...

Логические задачи на математических кружках в основной школе

Из условия задачи можно выделить два множества: множество оценок и множество имен. Каждое множество состоит из трех элементов.

Ответ: пистолет — синяя коробка, мишка — красная коробка, кукла — зеленая коробка, машинка — желтая коробка.

О спутниках τ-замкнутых n-кратно Ω-расслоенных формаций...

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

Обозначим через пересечение всех τ-замкнутых -расслоенных формаций, содержащих множество групп ; — пересечение всех -расслоенных формаций, содержащих и...

К вопросу о реализации решения задачи открытого...

Применение метода математической индукции к решению задач на... В математических олимпиадах часто встречаются достаточно

Ключевые слова: доминирование, доминирующее множество, число доминирования, задачи размещения, методы дискретной оптимизации...

Развитие логического мышления посредством решения...

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

О роли нестандартных задач в развитии логического мышления...

В связи с развитием наукоемких и высокотехнологичных производств в современной России повышается потребность в квалифицированных кадрах с высоким уровнем математического образования.

Задать вопрос