Применение принципа Дирихле при решении задач ЕГЭ.
материал для подготовки к егэ (гиа) по математике (11 класс) на тему

Применение принципа Дирихле при решении задач ЕГЭ.

Принцип Дирихле: один из принципов, сформулированных немецким математиком Дирихле.

Этот принцип достаточно прост и очевиден, иногда им пользуются из соображения логики, даже не зная его формулировки. Но, зная этот принцип, легче догадаться в каких случаях его применять. Проще всего принцип Дирихле выражается в такой шуточной форме: «Если в n клетках больше, чем n + 1 зайцев, то хотя бы в одной клетке сидят не меньше двух зайцев».

В переводе на язык математики: «Если множество, состоящее из n k+1 элементов разбить на k подмножеств, то хотя бы в одном подмножестве найдется не менее чем n + 1 элементов». Формулировки принципа Дирихле.

Существует несколько формулировок данного принципа.

1. «Если в n клетках сидит m зайцев, причем m>n, то хотя бы в одной клетке сидят, по крайней мере, два зайца».

Доказывается данный принцип Дирихле методом доказательства от противного:

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

2. «Пусть в n клетках сидят m зайцев, причем n>m. Тогда найдется хотя бы одна пустая клетка».

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

Пусть нет ни одной пустой клетки. Тогда количество зайцев m должно совпадать с количеством клеток n (если в каждой клетке хотя бы по одному зайцу) или быть больше, что противоречит условию.

3.  «Если m зайцев сидят в n клетках, то найдется клетка, в которой не менее m/n зайцев».

Не надо бояться дробного числа зайцев – если получается, что в ящике не меньше 7/3 зайцев, значит, их больше двух.

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

Допустим, что в каждой клетке число зайцев меньше, чем m/n.. Тогда в n клетках вместе зайцев меньше, чем n • (m/n) = m. Противоречие!

4. «Если в n клетках сидят m зайцев и m>kn + 1 , то в какой-то из клеток сидят, по крайней мере, k + 1 заяц» (обобщенный принцип)

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

Пусть не найдется такой клетки, то есть  в каждой из n клеток сидят по k зайцев, тогда зайцев должно быть  k•n, а по условию зайцев как минимум на одного больше. Пришли к противоречию с условием. Значит, есть клетка, в которой сидят k + 1 заяц.

Доказательство принципа Дирихле можно провести, применив метод от противного.

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

 находить верное решение в нестандартной ситуации.

На апробации КИМ в 2015 году ЕГЭ по математике (базовый уровень) задача №20 решается просто, если использовать принцип Дирихле.

В корзине лежат 25 грибов:рыжики и грузди. Известно, что среди любых 11 грибов имеется хотя бы один рыжик, а среди 16 грибов хотя бы один груздь. Сколько рыжиков в корзине?

Решение.

Рассмотрим первую ситуацию: среди любых 11 грибов имеется хотя бы один рыжик, т.е.

из 11 грибов:  

Рассмотрим вторую ситуацию: среди 16 грибов хотя бы один груздь, т.е.

из 16 грибов:        

Ответ: 15 рыжиков.

На первый взгляд, непонятно, почему это совершенно очевидное предложение, тем не менее, является мощным математическим методом решения задач, причем самых разнообразных. Всё дело оказывается в том, что в каждой конкретной задаче нелегко понять, что же здесь выступает в роли «зайцев», а что — в роли «клеток». И почему надо, чтобы «зайцев» было больше, чем «клеток». Выбор «зайцев» и «клеток» часто неочевиден. Далеко не всегда по формулировке задачи можно определить, что следует применить принцип Дирихле.

Таким образом, применяя данный метод, надо:

1)   определить, что удобно в задаче принять за «клетки», а что за «зайцев»;    

2)   получить «клетки». Чаще всего «клеток» меньше (больше), чем «зайцев» на одну;

3)   выбрать для решения требуемую формулировку принципа Дирихле.

Основные виды задач.

1. В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы.

«ЗАЙЦЫ» - 35 учеников

«КЛЕТКИ»- Буквы русского алфавита. Исключая Ъ,Ь,Ы, таких букв 30.

Задача свелась к тому, чтобы рассадить 35 зайцев в 30 клеток. Количество зайцев больше количества клеток. Используя принцип Дирихле (формулировка 1), можно сделать вывод, что найдутся хотя бы 2 ученика, фамилии, которых начинаются с одной буквы.

Или от противного: Пусть каждый ученик начальной буквой своей фамилии имеют различные буквы алфавита. Так как учеников 35, то и букв в алфавите должно быть не меньше. А мы точно знаем, что их 33. поэтому такая ситуация невозможна. Значит,  будут существовать хотя бы два ученика, чьи фамилии начинаются с одной буквы.

2. На дискотеку в студенческое общежитие, в котором 42 комнаты, пришли 36 гостей. Докажите, что найдется комната, в которую не пришел ни один гость.

«ЗАЙЦЫ» - 36 гостей

«КЛЕТКИ»- 42 комнаты.

Теперь необходимо рассадить 36 «зайцев» в 42 «клетки». Так как «зайцев» меньше, чем «клеток», то, используя принцип Дирихле (формулировка 2), можно сделать вывод, что найдется хотя бы одна пустая комната. На самом деле их как минимум 42-36=6.

Или от противного: Пусть в каждую комнату пришел гость, тогда гостей в общежитии должно быть как минимум 42, что противоречит условию. Значит, найдется комната, в которую не пришел ни один гость.  

3. В классе 40  учеников. Докажите, что среди них найдутся 4 ученика, отмечающие день рождения в одном месяце.

«ЗАЙЦЫ» - 40 учеников

«КЛЕТКИ»- 12 месяцев

Нам нужно рассадить 40 «зайцев» в 12 «клеток». Используя принцип Дирихле (формулировка 3), можем сделать вывод, что найдется «клетка», в которой сидят не менее 40/12=3 1/3 «зайцев», то есть как минимум 4 «зайца». Значит, можно утверждать, что найдутся 4 ученика, отмечающие день рождения в одном месяце.

Или от противного: Пусть нет 4 учеников, отмечающих день рождения в одном месяце. Тогда их должно быть 3, получается, что в классе должно быть не больше  12·3=36 учеников, что противоречит условию задачи.

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

«ЗАЙЦЫ» - 26 ящиков

«КЛЕТКИ»- 3 сорта

Осталось рассадить 26 «зайцев» в 3 «клетки». Так как 26> 3·8+1, то, используя принцип Дирихле (формулировка 4), можем утверждать, что в какой – то из «клеток» сидят 8+1=9 «зайцев». Значит,  найдутся 9 ящиков одного сорта.

От противного: Пусть ящиков одного сорта будет не больше 9, то есть 8. Тогда должно быть всего не более 8·3=24 ящиков яблок. Что противоречит условию.

Вернемся к задаче:

В классе 30 учеников. В диктанте Вова сделал 13 ошибок, а остальные -  меньше. Докажите, что по крайней мере 3 ученика сделали одно и то же число ошибок.

Количество ошибок может быть записано числами от 0 до 12, то есть 13 различных вариантов, их и примем за «КЛЕТКИ». Учеников, кроме Вовы, 29 – их примем за «ЗАЙЦЕВ». Осталось рассадить 29 «зайцев» в 13 «клеток». Так как 29> 13·2+1, то, согласно обобщенному принципу Дирихле, существует «клетка», в которой сидят, по крайней мере, 2+1=3 «зайца». Таким образом, можно утверждать, что в классе есть 3 человека, сделавших одинаковое количество ошибок.

При решении задач был использован принцип Дирихле и различные его формулировки. Задачи были решены 2 способами: принципом Дирихле и способом доказательства от противного.

.