Рубрики

Математика | Принцип голубиных отверстий

Предположим, что стая из 20 голубей летит в набор из 19 ям с голубями, чтобы укрыться. Поскольку существует 20 голубей, но только 19, то по крайней мере у одной из этих 19 ям должно быть как минимум два голубя. Чтобы понять, почему это так, обратите внимание, что, если в каждом голубом отверстии находится не более одного голубя, можно разместить максимум 19 голубей, по одному на отверстие. Это иллюстрирует общий принцип, называемый принципом голубиного отверстия, который гласит, что если голубей больше, чем голубых, то должна быть по крайней мере одна голубая дыра, в которой есть по крайней мере два голубя.

Теорема —

I) Если «A» — это среднее число голубей на одно отверстие, где A не является целым числом, то

  • По крайней мере одно отверстие для голубей содержит голубей ceil [A] (наименьшее целое число больше или равно A)
  • Оставшиеся дырки для голубей содержат не более пола [A] (наибольшее целое число меньше или равно A) голубей

Или

II) Можно сказать, что если n + 1 объектов помещены в n блоков, то хотя бы один блок содержит два или более объектов.
Абстрактная формулировка принципа: пусть X и Y конечные множества и пусть быть функцией.

  • Если X имеет больше элементов, чем Y, то f не является взаимно-однозначным.
  • Если X и Y имеют одинаковое количество элементов и f на, то f взаимно однозначно.
  • Если X и Y имеют одинаковое количество элементов и f взаимно однозначно, то f равно.

Принцип голубиных отверстий — одна из самых простых, но наиболее полезных идей в математике. Мы увидим больше приложений, которые доказывают эту теорему.

  • Пример — 1: Если (Kn + 1) голубей держат в n отверстиях для голубей, где K — положительное целое число, то среднее значение no. голубей на голубятню?

    Решение: среднее количество голубей на лунку = (Kn + 1) / n
    = K + 1 / n
    Поэтому, по крайней мере, в голубиных ямах содержится (K + 1) голубей, т. Е. Ceil [K + 1 / n], а в остальных — не более K, то есть floor [k + 1 / n] голубей.
    т. е. минимальное количество голубей, необходимое для того, чтобы хотя бы в одном голубином отверстии содержалось (K + 1) голубей, равно (Kn + 1).

  • Пример — 2: сумка содержит 10 красных шариков, 10 белых шариков и 10 синих шариков. Какого минимума нет. мрамора вы должны выбрать случайным образом из сумки, чтобы мы получили 4 шарика одного цвета?

    Решение: применить принцип «голубиных отверстий».
    Количество цветов (ямок) n = 3
    Количество мраморов (голубей) K + 1 = 4
    Поэтому минимального нет. мрамора требуется = Kn + 1
    Упрощая, получаем Kn + 1 = 10.
    Проверка: ceil [Среднее] равно [Kn + 1 / n] = 4
    [Kn + 1/3] = 4
    Kn + 1 = 10
    т.е. 3 красных + 3 белых + 3 синих + 1 (красный или белый или синий) = 10

Прямоугольный принцип сильной формы —

Теорема: Пусть q 1 , q 2 ,. , , , q n быть положительными целыми числами.
Если q 1 + q 2 +. , , + q n — n + 1 объектов помещаются в n блоков, тогда либо 1-й блок содержит не менее q 1 объектов, либо 2-й блок содержит не менее q 2 объектов,. , ., n-й блок содержит не менее q n объектов.

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

  • Пример — 1: На факультете информатики может быть сформирован студенческий клуб, состоящий либо из 10 членов первого года обучения, либо 8 членов второго года обучения, либо 6 участников третьего года, либо 4 участников последнего года обучения. Какого минимума нет. студентов мы должны выбирать случайным образом из отдела, чтобы обеспечить создание студенческого клуба?

    Решение: мы можем непосредственно применить из приведенной выше формулы, где,
    q 1 = 10, q 2 = 8, q 3 = 6, q 4 = 4 и n = 4
    Таким образом, минимальное количество студентов, необходимое для обеспечения образования факультетского клуба, составляет
    10 + 8 + 6 + 4 — 4 + 1 = 25

  • Пример — 2: коробка содержит 6 красных, 8 зеленых, 10 синих, 12 желтых и 15 белых шаров. Какого минимума нет. шаров мы должны выбрать случайным образом из коробки, чтобы убедиться, что мы получаем 9 шаров одного цвета?

    Решение: Здесь мы не можем слепо применять принцип голубя. Сначала мы посмотрим, что произойдет, если мы применим вышеупомянутую формулу напрямую.
    Из приведенной выше формулы мы получаем ответ 47, потому что 6 + 8 + 10 + 12 + 15- 5 + 1 = 47
    Но это не правильно. Чтобы получить правильный ответ, нам нужно включить только синие, желтые и белые шары, потому что красные и зеленые шары меньше 9. Но мы выбираем случайным образом, поэтому мы включаем их после применения принципа голубя.
    т.е. 9 синих + 9 желтых + 9 белых — 3 + 1 = 25
    Так как мы выбираем случайным образом, мы можем получить все красные и зеленые шары до 25 вышеуказанных шаров. Поэтому мы добавляем 6 красных + 8 зеленых + 25 = 39
    Можно сделать вывод, что для случайного выбора 9 шаров одного цвета нужно выбрать 39 шаров из коробки.

Ссылки:
http://www2.fiit.stuba.sk/~kvasnicka/Mathematics%20for%20Informatics/Rosen_Discrete_Mathematics_and_Its_Applications_7th_Edition.pdf

Эта статья предоставлена Сайкиран Гуд Бурра . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Математика | Принцип голубиных отверстий

0.00 (0%) 0 votes