Принцип Дирихле (Принцип голубятни) в комбинаторике

Привет, Вы узнаете о том , что такое принцип дирихле, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое принцип дирихле, принцип голубятни , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

В комбинаторике принцип дирихле — утверждение, сформулированное немецким математиком Дирихле в 1834 году, оно устанавливает связь между объектами («кроликами») и контейнерами («клетками») при выполнении определенных условий.

В английском и некоторых других языках утверждение известно как «принцип голубей и ящиков» (англ. Pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики. В немецком оно называется «принцип ящиков» (нем. Schubfachprinzip).

Принцип Дирихле нередко применяется при доказательстве теорем, особенно в дискретной математике; в частности, в теории диофантовых приближений и при анализе разрешимости систем линейных неравенств.

Принцип Дирихле. Если в n клетках сидит n+1 или больше кроликов, то найдется клетка, в которой сидят по крайней мере два кролика. Давайте обсудим

примеры

1. Шесть школьников съели семь конфет. Докажите, что один из них съел не менее двух конфет.

2. В классе 15 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем два ученика этого класса?

3. В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

9 клеток содержат 7 голубей, по принципу Дирихле хотя бы одна клетка (фактически даже больше одной) не содержит голубей

9 клеток содержат 10 голубей, по принципу Дирихле хотя бы в одной клетке находятся более одного голубя

Формулировки

Наиболее распространена следующая формулировка этого принципа:

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

Варианты более общих формулировок :

• При любом распределении или более предметов по ящикам в каком-нибудь ящике окажется не менее чем предмет.
• Если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее кроликов, а также хотя бы в одной клетке находится не более кроликов. Здесь уголки Айверсона и округляют заключенное в них выражение до целого, соответственно в бо́льшую и меньшую сторону.
• Пусть задана функция на конечных множествах A и B, причем , где . Тогда некоторое свое значение функция примет по крайней мере раз.

Встречаются также формулировки для частных случаев:

Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста.

Примеры применения

Теорема 1. При любом выборе пяти точек внутри единичного квадрата найдется пара точек, удаленных одна от другой не более чем на

Доказательство. Теорема на первый взгляд кажется сложной и неочевидной, но с помощью принципа Дирихле доказывается без труда . Разделим квадрат на 4 четверти, как показано на рисунке. По крайней мере две из пяти выбранных точек попадут в одну четверть, а тогда расстояние между ними будет не больше, чем диагональ четверти, равная ■

Теорема 2. Часть компании из людей обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатий .

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

Теорема 3. Для любого положительного иррационального числа существует бесконечно много дробей , отличающихся от менее, чем на (это одна из версий теоремы Дирихле о диофантовых приближениях) .

Доказательство. Об этом говорит сайт https://intellect.icu . Для произвольного натурального числа составим набор из значения:

, где обозначает целую часть числа.

Все эти числа принадлежат интервалу от 0 до 1. Распределим их в ящиков: в первый ящик поместим числа от 0 до во второй — от до и т. д. Но поскольку этих чисел больше, чем число ящиков, то по принципу Дирихле в одном из ящиков будет не менее двух разностей: и

Значения разностей по построению отличаются менее чем на Полагая получим:

или: (поскольку )

В силу произвольности числа близость дроби к числу можно сделать сколь угодно малой, поэтому количество дробей бесконечно. ■

принцип голубятни

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

• Китайская теорема об остатках.
• Книга Н. Б. Алфутовой и А. В. Устинова .
• Книга М. Айгнера М. и Г. Циглера .

Обобщения

Существует обобщение данного принципа на случай бесконечных множеств: не существует инъекции более мощного множества в менее мощное. Пример: если несчетное множество голубей содержится в счетном множестве ящиков, тогда хотя бы в одном из ящиков содержится несчетное множество голубей.

Ряд современных обобщений принципа Дирихле приведены в Теория Рамсея.

Примеры

Сбор носков

Предположим, что в ящике есть смесь черных и синих носков, каждый из которых можно носить на любой ноге, и что вы вытаскиваете из ящика несколько носков, не глядя. Какое минимальное количество натянутых носков необходимо, чтобы пара была одного цвета? Используя принцип ячеек, чтобы иметь хотя бы одну пару одного цвета ( m = 2 отверстия, по одному на цвет), используя по одному ящику для каждого цвета, вам нужно вытащить из ящика только три носка ( n = 3 предмета). Либо у вас есть три предмета одного цвета, либо у вас есть два предмета одного цвета и один другого цвета .

Рукопожатие

Если есть n человек, которые могут пожать друг другу руки (где n > 1 ), принцип ячейки показывает, что всегда есть пара людей, которые пожмут руку одинаковому количеству людей. В этом применении принципа «дыра», к которой приписывается человек, - это количество рук, которые он пожимает. Поскольку каждый человек пожимает руку некоторому количеству людей от 0 до n - 1 , существует n возможных отверстий. С другой стороны, либо отверстие '0', либо отверстие ' n - 1', либо оба должны быть пустыми, поскольку это невозможно (если n > 1) для кого-то, чтобы пожать друг другу руки, в то время как кто-то никому не пожимает руки. Это оставляет n человек, которые должны быть помещены не более чем в n - 1 непустую дырку, так что принцип применим.

Этот пример рукопожатия эквивалентен утверждению, что в любом графе с более чем одной вершиной есть по крайней мере одна пара вершин с одинаковой степенью . Это можно увидеть, связав каждого человека с вершиной, а каждое ребро - с рукопожатием.

Подсчет волос

Можно продемонстрировать, что в Лондоне должно быть как минимум два человека с одинаковым количеством волос на голове, следующим образом. Так как типичная человеческая голова имеет в среднем около 150 000 волос, разумно предположить (в качестве верхней границы), что ни у кого на голове не более 1 000 000 волос ( m = 1 миллион дырок). В Лондоне проживает более 1000000 человек ( nбольше 1 миллиона единиц). Назначив ячейку для каждого количества волос на голове человека и распределив людей по ячейкам в соответствии с количеством волосков на голове, должно быть как минимум два человека, назначенных на одну ячейку с помощью 1 000 001-го задания (потому что у них есть одинаковое количество волосков на голове) (или, n > m ). Предполагая, что в Лондоне проживает 8,9 миллиона человек ^[10], можно даже утверждать, что по крайней мере девять лондонцев имеют такое же количество волос, поскольку восемь лондонцев в каждой из 1 миллиона ячеек составляют всего 8 миллионов человек.

Для среднего случая ( m = 150 000 ) с ограничением: наименьшее количество перекрытий, будет не более одного человека, назначенного на каждую ячейку, и 150 001 человек, назначенный на ту же ячейку, что и кто-то еще. При отсутствии этого ограничения могут быть пустые ячейки, потому что «столкновение» происходит перед 150 001-м человеком. Принцип просто доказывает наличие перекрытия; в нем ничего не говорится о количестве совпадений (которое подпадает под распределение вероятностей ).

В «Истории афинского общества» есть мимолетный сатирический намек на эту версию принципа с приставкой «Дополнение к афинскому оракулу: сборник оставшихся вопросов и ответов в древнеафинских Меркуриях». (Отпечатано для Эндрю Белла, Лондон, 1710 г.). ^[11] Кажется, возникает вопрос , были ли в Мире какие-либо два человека с одинаковым количеством волос на голове? был выращен в Афинском Меркурии до 1704 года. ^{[12] [13]}

Возможно, первое письменное упоминание о появляется принцип закуток в 1622 в коротком предложении латинской работы Selectæ Propositiones , французского иезуита Жан Леерчон , , где он писал : «Необходимо , чтобы два человека имеют одинаковое количество волос, écus или другие вещи, как друг друга ". ^[14] Полный принцип был изложен двумя годами позже с дополнительными примерами в другой книге, которую часто приписывают Лерешону, но, возможно, написанной одним из его учеников.

Проблема дня рождения

В задаче о дне рождения задается набор из nслучайно выбранные люди, какова вероятность того, что у какой-то пары из них будет один день рождения? По принципу «ящика», если в комнате 367 человек, есть по крайней мере одна пара, у которой один день рождения, так как есть только 366 возможных дней рождения на выбор (включая 29 февраля, если есть). «Парадокс» дня рождения относится к результату, когда даже если группа состоит всего из 23 человек, вероятность того, что есть пара людей с одинаковым днем ​​рождения, все равно превышает 50%. Хотя на первый взгляд это может показаться удивительным, это интуитивно имеет смысл, если учесть, что на самом деле сравнение будет проводиться между всеми возможными парами людей, а не фиксировать одного человека и сравнивать его исключительно с остальной частью группы.

Командный турнир

Представьте себе семь человек, которые хотят сыграть в командном турнире ( n = 7 предметов) с ограничением выбора только четырьмя командами ( m = 4 лунки). Принцип «ящика» говорит нам, что все они не могут играть за разные команды; должна быть хотя бы одна команда, в которую входят как минимум двое из семи игроков:

Сумма подмножества [ править ]

Любое подмножество размера шесть из множества S = {1,2,3, ..., 9} должно содержать два элемента, сумма которых равна 10. Ячейки будут помечены двумя подмножествами элементов {1,9}, {2 , 8}, {3,7}, {4,6} и синглтон {5}, всего пять ячеек. Когда шесть «голубей» (элементы поднабора размера шесть) помещаются в эти ячейки, и каждый голубь входит в ячейку, на этикетке которой он содержится, по крайней мере, одна из ячеек, помеченных двухэлементной подгруппой, будет иметь две ячейки. голуби в нем. ^[15]

Использование и применения

Этот принцип может быть использован для доказательства того, что любой алгоритм сжатия без потерь , при условии, что он делает некоторые входные данные меньше (как следует из названия сжатия), также будет увеличивать некоторые другие входные данные. В противном случае набор всех входных последовательностей до заданной длины L можно было бы сопоставить (намного) меньшему набору всех последовательностей длиной меньше L без коллизий (поскольку сжатие без потерь), возможность, которую исключает принцип ящика.

Заметная проблема в математическом анализе является, при фиксированном иррациональным числом а , чтобы показать , что множество {[ па ]: п представляет собой целое число} из дробных частей является плотное в [0, 1]. Оказывается, нелегко явно найти такие целые числа n , m , что | на - м | < e , где e > 0 - небольшое положительное число, а a - произвольное иррациональное число. Но если взять M такое, что 1 / M < e, по принципу "голубятни" должно быть n ₁ , n ₂ ∈ {1, 2, ..., M + 1 } такое, что n ₁ a и n ₂ a находятся в одном целочисленном подразделении размера 1 / M (есть только M таких делений между последовательными целыми числами). В частности, можно найти n ₁ , n ₂ такие, что n ₁ a находится в ( p + k / M , p + ( k + 1) /M ) , и n ₂ a находится в ( q + k / M , q + ( k + 1) / M ) для некоторых p , q целых чисел и k в {0, 1, ..., M - 1 }. Тогда легко проверить, что ( n ₂ - n ₁ ) a находится в ( q - p - 1 / M , q - p + 1 / M ). Отсюда следует, что [ na ] <1 / M < e , где n = n ₂ - n ₁ или n = n ₁ - n ₂ . Это показывает, что 0 является предельной точкой {[ na ]}. Затем можно использовать этот факт для доказательства случая для p в (0, 1] : найти n такое, что [ na ] <1 / M < e ; тогда, если p ∈ (0, 1 / M ], доказательство завершено. В противном случае p ∈ (j / M , ( j + 1) / M ], и, полагая k = sup { r ∈ N : r [ na ] < j / M }, получаем | [( k + 1) na ] - p | <1 / M < e .

Варианты встречаются в ряде доказательств. В доказательстве леммы о накачке для обычных языков используется версия, в которой смешиваются конечные и бесконечные множества: если бесконечно много объектов помещается в конечное число ящиков, то существуют два объекта, которые разделяют ящик. ^[16] В решении Фиском проблемы Художественной галереи используется своего рода обратное: если n объектов помещаются в k ящиков, то получается ящик, содержащий не более n / k объектов. ^[17]

Альтернативные формулировки

Ниже приведены альтернативные формулировки принципа «ящика».

1. Если n объектов распределены по m местам, и если n > m , то в какое-то место попадают как минимум два объекта.
2. (эквивалентная формулировка 1). Если n объектов распределены по n местам таким образом, что ни одно место не принимает более одного объекта, то каждое место получает ровно один объект.
3. Если n объектов распределены по m местам, и если n < m , то какое-то место не получает никакого объекта.
4. (эквивалентная формулировка 3). Если n объектов распределены по n местам таким образом, что ни одно место не принимает ни одного объекта, то каждое место получает ровно один объект. ^[18]

Сильная форма

Пусть q ₁ , q ₂ , ..., q _n - натуральные числа. Если

объекты распределяются по n ящикам, тогда либо первый ящик содержит не менее q ₁ объектов, либо второй ящик содержит не менее q ₂ объектов, ..., либо n- й ящик содержит не менее q _n объектов. ^[19]

Простая форма получается отсюда, если q ₁ = q ₂ = ... = q _n = 2 , что дает n + 1 объект. Принятие q ₁ = q ₂ = ... = q _n = r дает более количественную версию принципа, а именно:

Пусть n и r - натуральные числа. Если n ( r - 1) + 1 объектов распределены в n ящиков, то хотя бы один из ящиков содержит r или более объектов. ^[20]

Это также можно сформулировать так: если k дискретных объектов должны быть распределены по n контейнерам, то по крайней мере один контейнер должен содержать по крайней мере объекты, где - функция потолка , обозначающая наименьшее целое число, большее или равное x . Точно так же по крайней мере один контейнер должен вмещать не более объекты, где - функция пола , обозначающая наибольшее целое число, меньшее или равное x .

Обобщения принципа ячейки

Вероятностное обобщение принципа голубятни гласит, что если n голубей случайным образом помещаются в m почтовых ящиков с одинаковой вероятностью 1 / m , то по крайней мере одна голубятня будет содержать более одного голубя с вероятностью

где ( m ) _n - падающий факториал m ( m - 1) ( m - 2) ... ( m - n + 1) . Для n = 0 и для n = 1 (и m > 0 ) эта вероятность равна нулю; Другими словами, если есть только один голубь, не может быть конфликта. Для n > m (больше голубей, чем ячеек) он равен единице, и в этом случае он совпадает с обычным принципом ячейки. Но даже если количество голубей не превышает количества почтовых ящиков ( n ≤ m), из-за случайного характера распределения голубей по ящикам часто существует значительная вероятность столкновения. Например, если 2 голубя случайным образом распределены по 4 ячейкам, существует 25% -ная вероятность, что хотя бы одна ячейка будет содержать более одного голубя; для 5 голубей и 10 лунок эта вероятность составляет 69,76%; а для 10 голубей и 20 лунок - около 93,45%. Если количество отверстий остается фиксированным, всегда больше вероятность пары, когда вы добавляете больше голубей. Более подробно эта проблема рассматривается в парадоксе дня рождения .

Дальнейшее вероятностное обобщение состоит в том, что, когда действительная случайная величина X имеет конечное среднее значение E ( X ) , тогда вероятность отлична от нуля того, что X больше или равно E ( X ) , и аналогично вероятность отлична от нуля, что X равно меньше или равно E ( X ) . Чтобы увидеть, что это подразумевает стандартный принцип ячеек, возьмите любое фиксированное расположение n голубей в m отверстий и пусть X будет числом голубей в ямке, выбранным равномерно случайным образом. Среднее значение Xравно n / m , поэтому, если голубей больше, чем нор, среднее значение больше единицы. Следовательно, X иногда не меньше 2.

Бесконечные наборы

Принцип голубятни можно распространить на бесконечные множества, сформулировав его в терминах кардинальных чисел : если мощность множества A больше, чем мощность множества B , то инъекции из A в B нет . Однако, в такой форме принцип тавтологическое , так как смысл утверждения о том , что мощность множества A больше , чем мощность множества B точно , что нет инъективно от A до B . Однако добавления хотя бы одного элемента к конечному набору достаточно для увеличения мощности.

Другой способ сформулировать принцип ячеек для конечных множеств похож на принцип, согласно которому конечные множества конечны по Дедекинду : пусть A и B - конечные множества. Если есть сюръекция из A в B, которая не является инъективной, то никакая сюръекция из A в B не является инъективной. Фактически, никакая функция любого вида от A до B не является инъективной. Это неверно для бесконечных множеств: рассмотрим функцию натуральных чисел, которая переводит 1 и 2 в 1, 3 и 4 в 2, 5 и 6 в 3 и так далее.

Аналогичный принцип действует и для бесконечных множеств: если несчетное количество голубей помещено в счетное количество ячеек, будет существовать по крайней мере один ящик, в который помещено несчетное количество голубей.

Однако этот принцип не является обобщением принципа ячейки для конечных множеств: в общем случае он неверен для конечных множеств. В техническом плане это говорит , что если и B конечные множества такие , что любая Сюръекция от A до B не инъективно, то существует элемент Ь из В таких , что существует взаимно однозначное соответствие между прообраза Ь и А . Это совершенно другое утверждение, абсурдное для больших конечных мощностей.

Квантовая механика

Якир Ааронов и др. представили аргументы в пользу того, что принцип «ящика» может быть нарушен в квантовой механике , и предложили интерферометрические эксперименты для проверки принципа «ящика» в квантовой механике. Однако более поздние исследования поставили этот вывод под сомнение. В январе 2015 года в препринте arXiv исследователи Аластер Рэй и Тед Форган из Университета Бирмингема выполнили теоретический анализ волновой функции полета электронов с различными энергиями через интерферометр с использованием стандартного принципа «голубятни».. Если бы у электронов вообще не было силы взаимодействия, каждый из них давал бы один идеально круглый пик. При высокой силе взаимодействия каждый электрон дает четыре различных пика, всего 12 пиков на детекторе; эти пики являются результатом четырех возможных взаимодействий, которые может испытать каждый электрон (по отдельности, только вместе с первой другой частицей, только вместе со второй другой частицей, или все три вместе). Если бы сила взаимодействия была довольно низкой, как это было бы во многих реальных экспериментах, отклонение от картины нулевого взаимодействия было бы почти незаметным, намного меньше, чем период решетки.атомов в твердых телах, таких как детекторы, используемые для наблюдения этих закономерностей. Это сделало бы очень трудным или даже невозможным отличить слабую, но ненулевую силу взаимодействия от вообще никакого взаимодействия, и, таким образом, дало бы иллюзию трех электронов, которые не взаимодействовали, несмотря на то, что все три проходили по двум путям.

Вау!! 😲 Ты еще не читал? Это зря!

• Аксиома выбора
• Теорема Блихфельдта
• Комбинаторные принципы
• Комбинаторное доказательство
• Дедекинд-бесконечное множество
• Парадокс Гильберта в Гранд Отеле
• Полиномиальная теорема
• Теорема Рамсея
• Символ Поххаммера

Данная статья про принцип дирихле подтверждают значимость применения современных методик для изучения данных проблем. Надеюсь, что теперь ты понял что такое принцип дирихле, принцип голубятни и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.