Принцип Дирихле

1.

Принцип Дирихле

2.

Знаете ли вы, что среди зрителей,
сидящих в Большом театре во время
спектакля, обязательно есть люди,
родившиеся в один и тот же день
одного и того же месяца? В зале
Большого театра 2000 мест. И даже
если не все они заполнены, можно
смело утверждать, что на спектакле
собралось более 366 человек. Но 366 —
это максимально возможное число дней
в году, считая 29 февраля. Итак, для
367 — го зрителя просто не остается
свободной от дней рождений его
соседей по залу даты в году. Просто?
Тем не менее это рассуждение даже
имеет свое название в
математике: принцип Дирихле.

3.

В комбинаторике при́нцип Дирихле́ —
утверждение, сформулированное немецким
математиком Дирихле в 1834 году,
устанавливающее связь между объектами
и контейнерами при выполнении
определённых условий.
Самая популярная
формулировка принципа
Дирихле такова: «Если в n клетках сидит
m зайцев, причем m > n, то хотя бы в одной
клетке сидят по крайней мере два зайца».
В английском и некоторых других языках
утверждение известно как «принцип
голубей и ящиков», когда объектами
являются голуби, а контейнерами —
ящики. В немецком оно называется
«принцип ящиков»

4.

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

5.

Решение задач
Задача 1. В хвойном лесу
растут 800000 елей. На каждой
ели - не более 500000 иголок.
Доказать, что существуют хотя
бы две ели с одинаковым числом
иголок.

6.

Предположим противное, то есть, предположим, что в этом лесу не существуют две
ели с одинаковым числом иголок. Тогда существует не более одной ели (одна ель
или ни одной), имеющей одну иголку. Аналогичным образом, существует не более
одной ели с двумя иголками и т.д., не более одной ели с 499999 иголками, не более
одной ели с 500000 иголками. Таким образом, не более 500000 елей обладают
числом иголок от 1 до 500000. Поскольку всего растут 800000 елей, значит, что одна
из них должна иметь 700000 иголок, другая - 600000, но по условию каждая ель
имеет не более 500000 иголок, следует, что найдутся хотя бы две ели с одинаковым
числом иголок.
Легко заметить, что решение в сути не зависит от конкретных чисел 800000
(количество елей) и 500000 (наибольшее число иголок). Принципиально был
использован тот факт, что число 800000 строго больше 500000. В доказательстве
предполагалось, что нет ни одной ели без иголок, хотя задача и доказательство
справедливы и в этом случае.

7.

Также существует обобщение данного принципа на случай
бесконечных множеств: не существует инъекции (отображение f
множества Х в множество Y, при котором разные элементы множества
Х переводятся в разные элементы множества Y) более мощного
множества в менее мощное. Пример: если несчётное
множество голубей содержится в счётном множестве ящиков, тогда
хотя бы в одном из ящиков содержится несчётное множество голубей.

8.

Конец