Приветствую Вас, Гость

Занятие 7

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

Работа по теме занятия

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

  1. В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих  дни рождения в один месяц. Решение Пусть 15 учеников будут «зайцы». Тогда «клетки» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как минимум, одна клетка, в которой будет сидеть, по крайней мере, 2 «зайца». То есть, найдется месяц, в котором будут отмечать дни рождения не менее 2 учеников класса. А это и требовалось доказать. Также задача легко решается с использованием метода доказательства от противного.

  2. Внутри равностороннего треугольника со стороной 1 см расположено 5 точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5 см. Решение Пусть 5 точек будут «зайцами». Так как «клеток» должно быть меньше, и чаще всего на 1, то их должно быть 4. Как получить эти 4 «клетки»?  Так как в условии задачи есть еще 2 числа: 1 и 0,5; причем второе меньше первого в 2 раза, то можно получить 4 «клетки», разбив равносторонний треугольник с помощью проведения отрезков, соединяющих середины сторон. Тогда получим 4 равносторонних  треугольника со сторонами по 0,5 см, которые и будут у нас «клетками»

  3. Дано 12 целых чисел. Докажите, что из них можно выбрать 2, разность которых делится на 11

  4. В ковре размером 3 на 3 метра.  Коля проделал 8 дырок. Докажите, что из него можно вырезать  коврик размером 1 на 1 метр, не содержащий внутри себя дырок. (Дырки можно считать точечными.).  В данной задаче необходимо применить другую формулировку принципа Дирихле: «Пусть в п клетках сидит м зайцев, причем п>м. Тогда найдется хотя бы одна пустая клетка».

       Решение Здесь дырки будут «зайцами». Разрежем ковер на 9 ковриков размерами 1 на 1 метр. Так как ковриков – «клеток» -9 , а дырок – «зайцев» -8, то найдется хотя бы одна «клетка», в которой не будет «зайцев», то есть найдется коврик без дырок внутри.

Выводы:

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

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

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

Самостоятельная работа

     5. Дано 9 целых чисел. Докажите, что из них можно выбрать2, разность которых делится на 8.

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

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

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

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

Задачи – шутки

  1. Как одним мешком пшеницы, сломав ее, наполнить два таких же мешка?

  2. Что это: две головы, две руки, шесть ног, а идут или бегут только четыре?

  3. Как-то в праздник один мой знакомый сказал мне: «позавчера мне было 40 лет, а в будущем году исполнится43 года». Могло ли такое быть?