На площадке 20 собак восьми разных пород

Принцип Дирихле

Цели занятия:

1. Образовательная цель: познакомить учащихся с принципом Дирихле и типами задач, решаемых этим методом
2. Развивающая цель: через решение задач с помощью метода Дирихле развивать умение анализировать, синтезировать, обобщать
3. Воспитательная цель: посредством организации занятия воспитывать усидчивость, настойчивость в достижении цели, интерес к математике.

План занятия:

1. Вступительная беседа
2. Объяснение нового материала
3. Закрепление
4. Итог занятия
5. Малая олимпиада
6. Домашнее задание

Вступительная беседа.

Что отличает урок математики от других уроков? Книгу по математике от книг по какому-то другому предмету? Большое количество вычислений? Формул? Но они есть и в других учебниках: в естествознании, физике, химии, астрономмии. Наличие доказательств – вот что прежде всего отличает математику от других областей знания. Конечно, доказательства встречаются и в других сферах человеческой деятельности, например, в юриспруденции. Однако математические доказательства убедительнее тех, которые можно слышать в суде. Математичекие доказательства признаются эталоном бесспорности.

Что же такое доказательство в математике? Доказательство – это такое рассуждение, которое убеждает нас настолько, что мы готовы убеждать других, используя то же рассуждение. В математике большое значение имеют так называемые доказательства существования. Самый простой способ доказатьсуществование объекта с заданными свойствами – это указать его и, разумеется, убедиться, что он обладает нужными свойствами. Например, чтобы убедиться, что уравнение имеет решение, достаточно привести какое-либо его решение. Такие доказательства называются прямыми. Но бывают и косвенные доказательства, когда обоснование того, что объект существует, происходит без прямого указания на сам объект.

Объяснение нового материала.

Рассмотрим пример. В классе 34 ученика. Докажите, что среди них обязательно найдутся по крайней мере два ученика, у которых фамиля начинается с одной буквы.

Доказательство простое. В русском языке алфавит содержит 33 буквы. Предположим, что нет таких учеников, у которых бы фамилия начиналась с одной буквы. Тогда учеников должно быть не более 33, а их 34.

Логический прием, который был использован прирешении этой задачи, называется принципом Дирихле. Дирихле Петер Август Лежен (1805-1859) – немецкий математик, иностранный член Петербургской  Академии наук, член многих академий. Дирихле –автор многих достижений в области математики, одна из его заслуг – принцип доказательства, названный его именем.

Существует несколько формулировок этого принципа. Самая популярная следующая: «Если в п клетках сидят т зайцев, причем т>п, то хотя бы в одной клетке сидят, по крайней мере, два зайца»

Например, если 4 кролика разместить в 3 клетках, то найдется хотя бы одна клетка, в которой будет не менее 2 кроликов (сделать рисунок). Предположим, что не существует клетки, где сидят два кролика. Тогда в трех клетках окажется не более 3 кроликов (сделать рисунок), а их 4 – противоречие.

Запишем принцип Дирихле: если по N разложить предметы,число которых  M больше N, то найдется ящик, в котором будет находится больше одного предмета.

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

Вернемся к первой задаче. Что в ней предметы? (ученики, M=34). Что в ней ящики? (количество букв в алфавите, N =33). M>N, то по принципу Дирихле хотя бы на одну букву будет приходится две фамилии.

Вернемся ко второй задаче. Что в ней предметы? (кролики, M= 4). Что в ней ящики? (клетки, N=3).M>N, то по принципу Дирихле хотя бы в одной клетке окажется два кролика.

Закрепление

1тип  «Сколько нужно взять?..»

1.В мешке лежат шарики двух разных цветов.Какое наименьшее число шариков нужновынуть из мешка, чтобы среди ни обязательно оказались два шарика одного цвета?

Решение:

Здесь роль предметов играют шарики (М=?), роль ящиков – цвета (N=2).Чтобы  M>N, т.е. в одном  ящике  оказалось два предмета, их должно быть больше двух, т.е. М=3

2.В коробке лежат карандаши: 7 красных и 5 синих. В темноте берут карандаши. Сколько карандашей надо взять, чтобы среди них было не менее 2 красных и не менее 3 синих?

Решение: Если предположить, что сначала будут попадаться только красные карандаши, то для того, чтобы было 3 синих, нужно взять 7(красные)+3(N)=10. Это «худший» варианнт развития событий, т.к. красных карандашей больше.

3.В мешке лежат 10 черных и 10 белых шаров. Они тщательно перемешены и неразлечимы на ощупь. Какое наименьшеее количество шаров нужно вынуть из мешка, чтобы среди них наверняка оказались два шара 1) одного цвета, 2)разного цвета, 3) белого цвета.

Решение:1)Если предположить, что предметы – шарики, которые нужно взять (М=?), а количество ящиков – цвета  N=2, то по принципу Дирихле М=3

2)если предположить, что сначала будут попадаться шары только одного цвета, то  N=10,следовательно, М=11

3)если предположить, что все время будут попадаться шары черного  цвета, то М=12.

2тип «Докажите, что найдутся двое…»

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

Решение: Дней в году N=365 или 366,то принципу Дирихле М= 366 или 367.

5.В лесу растет миллион елок. Известно, что на каждой из них не более 600 000 иголок. Докажите, что в лесу найдутся хотя бы две елки с одинаковым числом иголок.

Решение: Если предположить, что у всех елок разное количество иголок, то таких елок 600 000 (это ящики, N= 600 000), а по условию елок 1000 000=М, то М>N,по принципу Дирихле найдутся хотя бы две елки «в одном ящике», т.те с одинаковым количеством иголок.

6.В городе Санкт-Петербурге живет более 4млн. человек. Докажите, что у каких-то двух из них одинаковое количество волос на голове, если известно, что у любого человека на голове  не более миллиона волос.

Решение: Если предположить, что у всех людей разное количество волос, то таких людей N=1000 000 (ящики),  а по условию людей М=4 000 000. М>N, то по принципу Дирихле найдутся хотя бы два человека в одинаковым количеством волос.

3 тип. Обобщенный принцип Дирихле: если по N ящикам разложить предметы, число которых М больше, чем N (где к – натуральное число), то найдется ящик, в котором находятся более к предметов.

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

Решение. 25:3=8 (ост.1). 25=8*3+1. к=3, N=8, M>N, то принципу Дирихле найдутся хотя бы один ящик, в котором находятся более, чем к=3 предметов, т.е. 4 предмета.

8.На площадке 20 собак восьми разных пород. Докажите, что среди них есть не менее трех собак одной породы.

Решение: 20:8=2(ост. 4), 20=8*2+4. к=2,N=8, М>N, то по принципу Дирихле найдутся хотя бы три собаки одной породы.

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

Решение: В году 12 месяцев. 27:12=2(ост.3), 27=12*2+3. к=2,N=12,M>N, то по принципу Дирихле найдутся хотя бы три ученика, у которых дни рождения в одном месяце.

Итог урока.

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

1)Определить, что удобно взадаче принять за «предметы», а что за «ящики».

2)получит «ящики».Чаще всего, их должнобыть больше,чем предметов.

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

Малая олимпиада.

1. В ящике лежат носки четырех цветов. Какое  наименьшеее количество носков надо вытащить, чтобы из них можно было составить хотя бы одну пару?

Решение: N=4 (это количество цветов), То М=5.

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

Решение: Если предположить (худший вариант), что подряд попадаются ботинки на одну ногу (20), а затем ботинок на другую ногу, то20+1=21, среди них будут ботинки на одну ногу.

3.В школе учится 1200 учеников. Найдется ли день, в который отмечают свои дни рождения не меньше, чем 4 ученика данной школы?

Решение:  1200:366 =3(ост. 102),к = 3, N=366-количество дней в високосном году, M>N, то по обощенному принципу Дирихле найдутся хотя бы 4>к ученика, у которых дни рождения в один день.

4.В классе 26 учеников, из них более половины мальчики. Докажите, что какие-то 2 мальчика сидят за одним столом (в классе 13 столов).

Решение: Мальчиков более половины, т.е. более 13, М>13, то М :13=1(остатка есть), М=13*1+ ост, к=1, N=13 – количество столов , то по обощенному принципу Дирихле хотя бы 2 мальчика сидят за одним столом.

Домашнее задание.

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

Решение. Обозначив комнаты как предметы (М), а гостей как ящики (N), получим М>N, то по принципу Дирихле найдутся хотя бы две комнаты, в которые должен был прийти один и тот же гость, т.е.пустые комнаты.

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

Решение: 37:12=3(ост. 1),37=12*3+1. к=3, N=12-количество месяцев в году. M>N, то по обощенному принципу Дирихле найдется болеек, т.е.более  3,значит,4 ученика с днем рождения в одном месяце.

3. В доме живут 5 кошек. У них 16 котят. Докажите, что хотя бы у одной кошки не менее четырех котят.

Решение. 16:5=3(ост.1), 16=5*3+1. к=3, N=5. M>N, то по обощенному принципу Дирихле найдется хотя бы две кошки, у которых более 3, т.е. не менее 4 котят.

4.В ящике 25 белых шаров, 25 черных, 20 синих и 10 красных. На ощупь шары неотличимы друг от друга. Шары вынимают из ящика в темноте. Какое наименьшее количество шаров нужно вынуть, чтобы среди них обязательно оказалось: 1)10 шаров одного цвета;   2) 10 белых шаров?

Решение: 1)в худшем случае это будут 9 белых шаров+9 черных шаров+9 синих+9 красных=36 шаров. В любом случае, следующий шар будет иметь цвет, который станет 10. М=37.

2)В худшем случае это будут 25 черных + 20 синих + 10 красных + 10 белых шаров =65 шаров.

Задания для решения на занятии

1.В мешке лежат шарики двух разных цветов. Какое наименьшее число шариков нужновынуть из мешка, чтобы среди ни обязательно оказались два шарика одного цвета?

2.В коробке лежат карандаши: 7 красных и 5 синих. В темноте берут карандаши. Сколько карандашей надо взять, чтобы среди них было не менее 2 красных и не менее 3 синих?

3.В мешке лежат 10 черных и 10 белых шаров. Они тщательно перемешены и неразлечимы на ощупь. Какое наименьшеее количество шаров нужно вынуть из мешка, чтобы среди них наверняка оказались два шара 1) одного цвета, 2)разного цвета, 3) белого цвета.

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

5.В лесу растет миллион елок. Известно, что на каждой из них не более 600 000 иголок. Докажите, что в лесу найдутся хотя бы две елки с одинаковым числом иголок.

6.В городе Санкт-Петербурге живет более 4млн. человек. Докажите, что у каких-то двух из них одинаковое количество волос на голове, если известно, что у любого человека на голове  не более миллиона волос.

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

8.На площадке 20 собак восьми разных пород. Докажите, что среди них есть не менее трех собак одной породы.

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

Малая олимпиада.

1. В ящике лежат носки четырех цветов. Какое  наименьшеее количество носков надо вытащить, чтобы из них можно было составить хотя бы одну пару?

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

3.В школе учится 1200 учеников. Найдется ли день, в который отмечают свои дни рождения не меньше, чем 4 ученика данной школы?

4.В классе 26 учеников, из них более половины мальчики. Докажите, что какие-то 2 мальчика сидят за одним столом (в классе 13 столов).