Содержание
-
Принцип Дирихле
-
Знаете ли вы, что среди зрителей, сидящих в Большом театре во время спектакля, обязательно есть люди, родившиеся в один и тот же день одного и того же месяца? В зале Большого театра 2000 мест. И даже если не все они заполнены, можно смело утверждать, что на спектакле собралось более 366 человек. Но 366 — это максимально возможное число дней в году, считая 29 февраля. Итак, для 367 — го зрителя просто не остается свободной от дней рождений его соседей по залу даты в году. Просто? Тем не менее это рассуждение даже имеет свое название в математике: принцип Дирихле.
-
В комбинаторике при́нцип Дирихле́ — утверждение, сформулированное немецким математиком Дирихле в 1834 году, устанавливающее связь между объектами и контейнерами при выполнении определённых условий. Самая популярная формулировка принципа Дирихле такова: «Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят по крайней мере два зайца». В английском и некоторых других языках утверждение известно как «принцип голубей и ящиков», когда объектами являются голуби, а контейнерами — ящики. В немецком оно называется «принцип ящиков»
-
Отметим, что не важно, в какой именно коробке находятся по крайней мере два предмета. Также не имеет значение, сколько предметов в этой коробке, и сколько всего таких коробок. Важно то, что существует хотя бы одна коробка с не менее чем двумя предметами (два или более).
-
Решение задач
Задача 1. В хвойном лесу растут 800000 елей. На каждой ели - не более 500000 иголок. Доказать, что существуют хотя бы две ели с одинаковым числом иголок.
-
Предположим противное, то есть, предположим, что в этом лесу не существуют две ели с одинаковым числом иголок. Тогда существует не более одной ели (одна ель или ни одной), имеющей одну иголку. Аналогичным образом, существует не более одной ели с двумя иголками и т.д., не более одной ели с 499999 иголками, не более одной ели с 500000 иголками. Таким образом, не более 500000 елей обладают числом иголок от 1 до 500000. Поскольку всего растут 800000 елей, значит, что одна из них должна иметь 700000 иголок, другая - 600000, но по условию каждая ель имеет не более 500000 иголок, следует, что найдутся хотя бы две ели с одинаковым числом иголок. Легко заметить, что решение в сути не зависит от конкретных чисел 800000 (количество елей) и 500000 (наибольшее число иголок). Принципиально был использован тот факт, что число 800000 строго больше 500000. В доказательстве предполагалось, что нет ни одной ели без иголок, хотя задача и доказательство справедливы и в этом случае.
-
Также существует обобщение данного принципа на случай бесконечных множеств: не существует инъекции (отображение f множества Х в множество Y, при котором разные элементы множества Х переводятся в разные элементы множества Y) более мощного множества в менее мощное. Пример: если несчётное множество голубей содержится в счётном множестве ящиков, тогда хотя бы в одном из ящиков содержится несчётное множество голубей.
-
Конец
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.