Представьте, что десять голубей летят в ваш самодельный голубятник, но вы сделали только 9. Куда летит последний голубь? Какова история всего принципа голубятника?
Поскольку население Лондона превышает максимальное количество волос на голове человека, принцип голубятника требует, чтобы по крайней мере два человека в Лондоне имели одинаковое количество волос на голове. Этот математический принцип существует с 1624 года.
Принцип голубятника
Принцип голубятника — один из самых базовых, но ценных концептов математики. Он был зафиксирован еще в 1624 году. Он обычно известен как принцип ящика Дирихле или принцип ящика Дирихле. (Source: Jeff 560)
В самом простом объяснении принцип гласит, что если десять голубей собираются в девять голубятников, по крайней мере один из голубятников будет содержать более одного голубя.
В теореме: если X — среднее количество голубей на ячейку, и X не является целым числом, то по крайней мере один голубятник содержит максимальное допустимое количество голубей, а остальные голубятники, скорее всего, будут иметь минимальное количество голубей. (Source: Geeks For Geeks)
Для дальнейшего объяснения, если n + 1 объект помещается в n контейнеров, то по крайней мере один контейнер будет содержать два или более предмета. Принцип голубятника используется, чтобы показать, что результаты должны быть верны, потому что они “слишком велики, чтобы потерпеть неудачу.” Это означает, что по крайней мере два объекта будут иметь или разделять свойство для любого значительного количества вещей с ограничением или определённым числом свойств. И применения этого принципа интересны, удивительны и вызывают размышления. (source: Stanford)
Некоторые примеры принципа
Первый пример, как указано выше, демонстрирует принцип голубятника следующим образом: население Лондона без лысых людей составляет около 7,5 миллиона. Максимальное количество волос у среднего человека — около 150 000. Принцип подразумевает, что примерно 50 человек будут иметь одинаковое количество волос. (Source: Maths Careers)
Далее, предположим, что два или более человек читают эту статью и у них будет один и тот же день рождения. Принцип гласит, что в високосном году существует 366 возможных дней рождения. В этой статье более 367 читателей. Следовательно, двое из вас имеют один и тот же день рождения.
Другим примером может служить колода обычных игральных карт. Если человек выбирает пять карт из 52 карт в стандартной колоде, то как минимум две из этих пяти карт будут одной масти. Для пояснения, в обычной колоде есть четыре масти – трефы, пики, черви и бубны. Каждая из пяти карт должна принадлежать одной из четырёх мастей. Следовательно, две из этих карт будут одной масти. (Источник: Mind Your Decisions)
Есть ли практическое применение этого принципа?
Принцип Дирихле помогает доказать без потерь сжатие, используемое в науке о данных. Сжатие данных – это теория, согласно которой реальные данные можно сжать, просто устраняя избыточность.
Это важная теория, используемая в современном мире в виде передачи данных, будь то передача через сеть, DVD, флеш‑накопители или электронную почту, назовём несколько примеров.
Идея без потерь сжатия состоит в замене каждой битовой строки информации более короткой битовой строкой. Однако после распаковки более короткой битовой строки она всё равно раскрывает полную информацию исходной битовой строки. (Источник: Stanford)
Принцип Дирихле доказывает без потерь сжатие, при котором возможно сжать только сильно повторяющиеся данные, когда два «голубя», кусочка данных, занимают один «гнёздо» или место в битовой строке. (Источник: Stanford)
