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

Подготовили студенты 402 группы:
Куделько Марина

Бобровская Яна

Матросова Елена

При решении задач на “доказательство” часто бывает полезен так называемый “принцип Дирихле”.

В комбинаторике при́нцип Дирихле́ (нем. Schubfachprinzip, «принцип ящиков») — утверждение, сформулированное немецким математиком Дирихле в 1834 году, устанавливающее связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках утверждение известно как «принцип голубей и ящиков» (англ. Pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики.

В самом простом варианте этот принцип можно пояснить так: если 11 кроликов рассадить в 10 клеток, то, по крайней мере, в одной клетке окажутся 2 кролика. Или другими словами: нельзя посадить 11 кроликов в 10 клеток так, так чтобы в каждой клетке находилось не больше одного кролика.

Более общая формулировка звучит так:

Если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее кроликов, а также хотя бы в одной клетке находится не более кроликов (где, обязательно m>n !!!!!).

Следствие из принципа Дирихле:

Если сумма n чисел равна S, то среди них есть как число, не большее , так и числа, не меньшее . Конечно же, ведь если, например, все числа больше , то их сумма больше S, что противоречит условию. Или, если все числа меньше , то их сумма меньше S, что также противоречит условию.

Принцип Дирихле можно использоваться в таких задачах как:

· “Клетки” и “кролики”

· Следствие из принципа Дирихле

· Наверняка

· Знакомства

· Принцип Дирихле и делимость

· Точки, многоугольники и принцип Дирихле

Самое главное - это понять, что в задаче клетки, а что кролики.

Попробуем применить эти принципы на практике.

В аудитории:

“Клетки” и “кролики”

№1

В школе 30 классов и 1000 учащихся. Докажите, что есть класс, в котором не менее 34 учеников.
Наводящие вопросы:

· Что можно взять в данной задачи за “кроликов” и за “клетки”??

· Как можно рассадить кроликов по клеткам??

Решение:

За “кроликов” нужно взять учащихся, а за “клетки” − классы. Тогда имеем:

1)1000:30=33 ,
Получили, что каждый класс будет обязательно иметь по 33 ученика. Остался 1 ученик, его можно распределить в любой класс, таким образом, доказано, что имеется класс, в котором не менее 34 ученика.

№2

В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

Решение:

За “кроликов” нужно взять ящики, а за “клетки” – сорт яблок. Тогда имеем:

1) 25:3=8

Получается, что в 8 ящиках лежат яблоки каждых сортов. Всего 24 ящика. И остается один ящик одного сорта. Поэтому, можно найти 9 ящиков с яблоками одного сорта.

№3

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

Б) В школе 400 учеников. Можно ли утверждать, что среди учащихся этой школы обязательно найдутся хотя бы два ученика, отмечающие день рождения в один день?

В) В школе 735 учащихся. Можно ли утверждать, что, по крайней мере, три ученика должны отмечать день своего рождения в один и тот же день?

Наводящие вопросы:

· Что можно взять в данной задачи за “кроликов”, а что за “клетки”??

· Как можно рассадить кроликов по клеткам??

· Сколько месяцев в году?

· Сколько дней в году? А в високосном?

№4

Докажите, что из любых 52 натуральных чисел можно выбрать 2 числа так, что либо их сумма, либо их разность делится на 100. Верно ли это утверждение для 51 числа?

Решение:

Построим 51 «клетку»:
«клетка» 0 – для чисел, оканчивающихся на 00;

«клетка» 1 – для чисел, оканчивающихся на 01 или 99;

«клетка» 2 − оканчивающихся на 02 или 98;

…;

«клетка» 49 − оканчивающихся на49 или 51;

«клетка» 50 − оканчивающихся на 50.

Какие-то 2 числа из 52 данных попадут в одну клетку.

Тогда либо их сумма, либо их разность оканчиваются на 00.

А вот среди 51 числа такой пары может не быть. Например, среди чисел 1,2, 3…, 50, 100 – всего 51 число, нет двух чисел, чтобы их сумма или разность оканчивалась на 00, следовательно делилась бы на 100.