Задачи на принцип Дирихле

ПРИНЦИП ДИРИХЛЕ

Принцип Дирихле гласит:Пусть в клетках сидит не меньше, чем N+1 кроликов. Тогда найдется клетка, в которой сидит не меньше двух кроликов.

Оказ, что это простое утв помог в реш самых разных задач. Гл понять, что в дан задаче клетки, а что √ кролики.

Иногда исп обобщ принцип Дирихле: Пусть в N клетках сидит k кроликов. Тогда найдется клетка, в которой сидит не меньше k/N кроликов, и найдется клетка, в которой сидит не больше k/N кроликов.

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

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

• Пусть задана функция на конечных множествах A и B, причём | A | n | B | , где . Тогда некоторое своё значение функция f примет по крайней мере n+1 раз.

Сущ обобщ данного принц на сл бескон мн-в: не сущ инъекции б мощного множества в менее мощн

Попробуйте применить эти принципы в следующих задачах.

Вводные задачи

3.1. Шесть школьников съели семь конфет.

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

б) Верно ли, что кто-то съел ровно две конфеты?

3.2. У человека на голове не более 400000 волос, в Москве более 8 млн жителей. Докажите, что найдутся 20 москвичей с одинаковым числом волос.

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

3.4. Петя хочет написать на доске 55 разл двузн чисел так, чтобы среди них не было двух чисел, дающих в сумме 100. Сможет ли он это сделать?

3.5. В ковре размером 4 х 4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1 х 1 метр, не содержащий внутри себя дырок. (Дырки считаются точечными).

Задачи для самостоятельного решения

3.6. Докажите, что среди любых трех целых чисел можно найти два, сумма которых четна.

3.7. В некот классе учится 30 не оч грамо учеников. Во время диктанта один ученик сделал 14 ошибок, но зато ост меньше. Докажите, что в классе имеются но кр мере три ученика, сделавшие в диктанте одинаковое количество ошибок.

3.8*. Док, что в Вашем классе найдутся два чел, имеющ одинак число друзей среди своих однокласс.

3.9. В клетк шахм доски 8 х 8 запис числа 1, 2, 3, ..., 62, 63, 64. Док, что найд две такие сосед клетки, что числа, запис в них, отлич не меньше, чем на 9. (Сосед счит клетки, имеющ общ сторону или вершину).

3.10. На далекой план Зям-лям, имеющ форму шара, суша заним б половины поверхн планеты. Док, что м прорыть прямой туннель, проход через ц планеты и соединяющий сушу с сушей.

Применения

1. Принцип Дирихле в теории линейных и нелинейных диофантовых приближений.
   Теорема Хинчина о квадратичных приближениях. Понятие об аналитических методах.

2. Аппарат цепных дробей. Иррегулярности распределения в диофантовых приближениях.
   Невозм «слишком хорошо» прибл иррац числа рациональ.Теорема об осцилляции.

3. Равномерно распредел посл-ти.
   Последовательности с логарифмическим отклонением.
   Последовательность Ван дер Корпута.
   Теорема Островского.

4. Иррегулярности распределения. Теорема Рота-Шмидта.