Математические понятия: принцип голубей и ящиков, комбинаторика

Никогда не сбрасывайте со счетов простую идею, так как такие идеи иногда имеют большие последствия. Одной из таких идей является принцип голубей и ящиков, который впервые сформулировал немецкий математик Петер Густав Лежен Дирихле в 1834 году. Согласно этому принципу, если у вас есть три ящика и четыре голубя, и каждый голубь должен занять ящик, следовательно, в одном ящике должно быть больше одного голубя. (Принцип не говорит, сколько голубей находится в каждом ящике или что в каждом ящике находится голубь. Все четыре голубя могут находиться в одном ящике, а два остальных останутся пустыми.) Если мы захотим описать этот принцип в более общей форме, не ссылаясь конкретно на голубей (принцип также работает и с коровами, индейками, футбольными мячами или любыми другими объектами), то можно сказать, что если у нас есть Н контейнеров и М объектов и М превышает количество Н, тогда в одном из контейнеров будет как минимум один объект.

Вы можете использовать принцип голубей и ящиков для заявлений о мире. Допустим, что у вас есть пачка M&M’s, половина конфет красные, а другая половина – коричневые. Какое минимальное количество конфет вам нужно вытащить из пачки, чтобы у вас было как минимум две конфеты одного цвета? (Ответ: 3. Вы можете выбрать две конфеты одинакового цвета в самом начале. Но вы также можете выбрать одну красную и одну коричневую. В этом случае цвет третьей конфеты будет уже не важен – у вас будет пара. В таком же ключе представьте две коробки: одна для красных конфет, другая – для коричневых. Мы хотим найти минимальное количество конфет, которые мы должны вытащить из пачки, чтобы две из них оказались в одной коробке.)

Этот принцип можно использовать и чтобы определить, что два человека в Нью-Йорке имеют одинаковое количество волос на голове. У каждого человека примерно 100 000 волос на голове, а в Нью-Йорке живут примерно 8 миллионов человек. Так как существует 100 000 вероятностей количества волос на любой человеческой голове, тогда, скажем, что у нас есть 100000 ящиков. А 8 миллионов жителей Нью-Йорка соответствуют 8 миллионам голубей, следовательно, мы можем быть уверенными, что как минимум два голубя – или человека – занимают одну коробку, то есть у них одинаковое количество волос на голове.

По-английски принцип голубей и ящиков звучит как «pigeonhole principle», но иногда слово «pigeonhole» используется в контексте без ссылок на голубей и контейнеры. В Конгрессе используют словосочетание «to pigeonhole a bill», что значит «отложить законопроект в долгий ящик», грубо говоря, положить его на полку и на время о нем забыть.