Как связаны математика и кролики? Принцип Дирихле

Как связаны математика и кролики? Принцип Дирихле

МАОУ СОШ №4 г.Черняховска

Небольсина Н.А.

Актуальность темы исследования

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

Цели проекта:

• Познакомиться с принципом Дирихле
• Научиться применять его на практике

Задачи проекта:

• Познакомиться с различными формулировками принципа Дирихле
• Привести математическое доказательство
• Разобрать примеры использования
• Определить значимость данного принципа в науке

• Иоганн Дирихле  — немецкий математик, внёсший существенный вклад в математический анализ, теорию функций и теорию чисел. Член Берлинской и многих других академий наук, в том числе Петербургской (1837)

• Принцип Дирихле — утверждение, устанавливающее связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий.

• Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.
• При любом распределении nk+1 или более предметов по n ящикам в каком-нибудь ящике окажется не менее чем  k+1 предмет.
• Если  m  кроликов рассажены в  n  клеток, то хотя бы в одной клетке находится не менее M:N  кроликов, а также хотя бы в одной клетке находится не более  M:N  кроликов.
• Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста.

Доказательство

• Принцип Дирихле можно доказать методом от противного. Пусть имеется N клеток и (N+1) кролик. Предположим, что в каждой клетке не более одного кролика.

N 1 ≤1

N 2 ≤1

N 3 ≤1

…… ..

N n ≤1

N 1 +N 2 +N 3 +…+N n ≤1+1+1=N

• Противоречие.

• Теорема 1 . При любом выборе пяти точек внутри единичного квадрата найдётся пара точек, удалённых одна от другой менее чем на sqrt2/2

• Доказательство
• Разделим квадрат на 4 четверти, как показано на рисунке. По крайней мере две из пяти выбранных точек попадут в одну четверть, а тогда расстояние между ними будет меньше, чем диагональ четверти, равнаяsqrt2/2. 

Задача

100 человек сидят за круглым столом, причем более половины из них — мужчины.

Докажите, что какие-то двое мужчин сидят друг напротив друга

Решение:

Разобьем всех на 50 пар людей, сидящих друг напротив друга. Тогда мы получаем, что у нас есть 50 пар («клетки»), в которые нужно рассадить не менее 51 мужчины («кролики»). Из принципа Дирихле следует, что в одной из этих пар-«клеток» оба человека —мужчины-«кролики

Задача

В клетках таблицы 3Х3расставлены числа -1 , 0, 1. Докажите, что какие-то две из восьми сумм по всем строкам, всем столбцам и двум главным диагоналям будут равны.

-1

0

0

1

1

1

-1

0

0

Пример произвольной расстановки чисел

Решение

Каждая из этих восьми сумм может принимать лишь семь разных значений: от до 3, значит, по принципу Дирихле какие-то две суммы совпадут.

• Задача
• Докажите, что на шахматной доске нельзя расставить более 8 ладей так, чтобы никакие две из них не били друг друга.

Решение

• На одной горизонтали не может стоять больше одной ладьи — иначе они будут бить друг друга. Значит, ладей можно поставить не больше, чем горизонталей у доски, их 8. Следовательно, больше 8 ладей поставить на доску нельзя.

Задачи на обобщенный принцип Дирихле

• Задача
• Имеется 101 пуговица одного из 11 цветов. Докажите, что либо среди этих пуговиц найдутся 11 пуговиц одного цвета, либо 11 пуговиц разных цветов.

• Решение
• Предположим, что среди данных пуговиц нет 11 пуговиц разных цветов. Тогда каждая пуговица окрашена в один из 10 цветов. Если пуговиц каждого цвета не более 10, то всего пуговиц не более 100, и это противоречит условию. Таким образом, пуговиц какого-то одного цвета не менее 11, что и нужно было доказать.

• Задача:
• Докажите, что из любых семи натуральных чисел можно выбрать три числа, сумма которых делится на 3.

• Решение
• По принципу Дирихле из семи чисел можно выбрать три, дающие одинаковые остатки при делении на 3 (так как имеется лишь три различных остатка — 0, 1 и 2). Их сумма, очевидно, делится на 3.

Выводы:

• Принцип Дирихле используется при доказательстве теорем, особенно в дискретной математике, а также в сложнейших математических теориях. Его обобщения, число которых весьма велико, используются по отношению к бесконечным множествам. Данный принцип позволяет упрощать решение олимпиадных задач

Используемая литература:

• Алфутова Н. Б, Устинов А. В.  Алгебра и теория чисел. Сборник задач для математических школ.
• Знак Е. И.  Разбиение математических решеток и принцип Дирихле
• Учебник Фоксфорд «Олимпиадная математика»
• https://ru.wikipedia.org