Давайте знакомиться: принцип Дирихле! Проектную работу выполнила ученица 6 «А» класса МОУ «СОШ 17 г. Вольска» Кальбина Кристина Руководитель Сафронова Вера Николаевна,учитель математики Консультант Дерина Юлия Владимировна, учитель информатики

Стояло солнце высоко, Бежали зайцы по дороге От льва, лисы, - неважно от кого Косые уносили ноги.

Существенно одно: Их было ровно m. Устали зайцы, жажда одолела. Увидели морковь – Решенье всех проблем, Хоть в клетках та морковь, - Совсем не в этом дело.

А дело в том, что Клеток ровно n. Вбежали зайцы в клетки, Утоляют жажду. Известно отношенье: n

Как утверждает принцип Дирихле, Хотя бы в одной клетке Грызут морковь, не вспоминая о лисе По крайней мере, зайца два, Словно приятели в беседке.

Приглашаю вас, друзья, На турнир сегодня я: Илью, Ладу, Женю тоже,- Дирихле вам всем поможет Новые решать задачи. Я желаю всем удачи! Ясность мысли тут нужна, Чтоб понять, где ложь, где истина. А ведущей на турнире буду я – Ваша одноклассница Кальбина Кристина.

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

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

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

I. Вводные задачи (Объяснение ведущей) 1. Математический кружок посещают 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц.

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

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

Решение. Перед нами миллион «зайцев» (елок) и, всего лишь «клетка» с номерами от 0 до Каждого «зайца» (елку) сажаем в клетку с номером, равным количеству иголок на этой елке. Так как «зайцев» гораздо больше, чем «клеток», то в какой-то «клетке» сидят, по крайней мере, 2 «зайца», а если два «зайца» - елки «сидят в одной клетке», то количество иголок у них одинаково.

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

Решение. Имеем 3 «клетки» (сорта), 34=3×11+1. В каждую «клетку» (сорт) мы можем «посадить» 11 «зайцев» (ящиков) и еще у нас есть один ящик. Значит, в какую-то «клетку» (сорт) мы посадим еще одного «зайца»(ящик).Таким образом, можно утверждать, что, по крайней мере, в 12 ящиках находятся яблоки одного сорта.

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

Решение. Обозначим 35 учеников за «зайцев», за буквы за «клетки». В русском алфавите 33 буквы. Фамилии не могут начинаться на Ъ и Ь. Так как 35 больше 31, то, по принципу Дирихле, найдется 2 ученика, у которых фамилии начинаются с одной буквы.

2. В городе живет 200 тысяч жителей. Докажите, что в городе найдутся хотя бы 2 человека с одинаковым числом волос на голове. Считайте, что у человека на голове не больше 150 тысяч волос.

Решение. Примем жителей за «зайцев», их 200 тысяч. А клеток лишь 150 тысяч с номерами от 0 до 150 тысяч. Так как «зайцев» - жителей гораздо больше, чем «клеток», то, по крайней мере, в одной «клетке» окажется 2 «зайца», то есть в городе найдутся 2 человека с одинаковым числом волос на голове.

3. В коллекции имеется 25 монет по 1, 2, 3, 5 копеек. Имеется ли среди них 7 монет одинакового достоинства?

Решение. Имеем 4 «клетки» (монет разного достоинства), 25=4×6+1. В каждую «клетку» мы можем «посадить» 6 «зайцев» (монет одного достоинства) и еще останется одна монета. Значит, в какую-то «клетку» мы посадим еще одного «зайца» (монету). Таким образом, среди 25 монет, по крайней мере, имеется 7 монет одинакового достоинства.

II. Вводные задачи (Объяснение ведущей) 1. Дано 12 целых чисел. Докажите, что из них можно выбрать 2, разность которых делится на 11.

Решение. Примем числа за «зайцев». Так как их 12, то «клеток» должно быть меньше. Пусть «клетки» - это остатки от деления целого числа на 11. Всего «клеток» будет 11: 0, 1, 2, 3, 4, 5, 6, 7, 8,9, 10. Тогда, по принципу Дирихле, найдется «клетка», в которой будут сидеть на менее чем 2 «зайца», то есть найдутся 2 целых числа с одним остатком. А разность двух чисел с одинаковым остатком от деления на 11, будет делиться на 11. Действительно, пусть а=11m+r, b=11n+r? тогда а- b=11m+r-(11n+r)=11m+r-11n-r=11m-11n=11(m-n). А 11(m-n) делится на 11.

2. В ковре размером 3×3 метра Коля проделал 8 дырок. Докажите, что из него можно вырезать коврик размером 1×1 метр, не содержащий внутри себя дырок. (Дырки можно считать точечными).

Решение. В данной задаче для решения необходимо применить другую формулировку принципа Дирихле: «Пусть в n клетках сидят m зайцев, причем n>m. Тогда найдется хотя бы одна пустая клетка. В этой задаче дырки будут «зайцами». Разрежем ковер на 9 ковриков размером 1×1 метр. Так как ковриков – «клеток» 9, а дырок- «зайцев» - 8, то найдется хотя бы одна «клетка», в которой не будет «зайцев», то есть найдется коврик без дырок внутри.

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

Решение. Примем числа за «зайцев». Пусть «клетки» - это остатки от деления целого числа на 9. Всего «клеток» будет 9: 0, 1, 2, 3, 4, 5, 6, 7, 8. Тогда, по принципу Дирихле, найдется «клетка», в которой будут сидеть на менее чем 2 «зайца», то есть найдутся 2 целых числа с одним остатком. А разность двух чисел с одинаковым остатком от деления на 9, будет делиться на 9.

2. В ковре размером 4×4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1×1 метр, не содержащий внутри себя дырок. (Дырки считаются точечными).

Решение. Разрежем ковер тремя вертикальными и тремя горизонтальными разрезами на 16 одинаковых ковриков размером 1×1 метр. Поскольку 16>15, то один из ковриков будет без дыр.

3. Шесть школьников съели семь конфет. Докажите, что один из них съел не менее двух конфет.

Решение. Если 7 «зайцев» - конфет рассадим по 6 клеткам, то в одной клетке окажется по крайней мере 2 кролика, т.е. один ученик съел как минимум 2 конфеты. (7=6×1+1).

III. Вводные задачи (Объяснение ведущего) Некоторые из задач, решаемых с помощью принципа Дирихле, также можно решить, используя метод доказательства от противного. 1. В классе 30 человек. В диктанте Саша Иванов сделал 13 ошибок, а остальные - меньше. Докажите, что по крайней мере три ученика сделали ошибок поровну (может быть, по 9 ошибок).

Решение. Здесь "зайцы" - ученики, "клетки" - число сделанных ошибок. В клетку 0 "посадим" всех, кто не сделал ни одной ошибки, в клетку 1 - тех, у кого одна ошибка, в клетку 2 - две,... и так до клетки 13, куда попал один Саша Иванов. Докажем утверждение задачи от противного. Предположим, никакие три ученика не сделали по одинаковому числу ошибок, то есть в каждую из клеток 0, 1,..., 12 попало меньше трех школьников. Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не больше 26 человек. Добавив Сашу Иванова, все равно не наберем 30 ребят.Противоречие. Следовательно, утверждение задачи верно.

2. В ящике лежат носки одного и того же размера. Белых носков вполне достаточно, чтобы составить 5 пар, черных - для 10 пар и коричневых - для 15 пар. Какое самое маленькое количество носков нужно вытащить из ящика (не заглядывая туда), так, чтобы наверняка у вас в руках оказалась пара носков? (Между левым и правым носком нет никакой разницы.)

Решение. Предположим, вышел худший случай: мы достали 3 носка разных цветов. Но четвёртый носок, какого цвета он ни был, сделает пару с каким-нибудь из взятых ранее носков.

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

Решение Пусть «зайцы» – игроки команды, клетки – дни недели. Сколько игроков в футбольной команде? – 11, а дней недели – 7. Рассуждаем от противного: если бы такого дня недели не нашлось, то в каждый из 7 дней недели родилось не более одного игрока команды. Значит, всего футболистов в команде будет не более 7. Но 11>7. Противоречие доказывает утверждение задачи.

В ящике лежат цветные карандаши: 10 красных, 8 синих и 4 желтых. В темноте берем из ящика карандаши. Какое наименьшее число карандашей надо взять, чтобы среди них заведомо было: а) не менее 4-х карандашей одного цвета? б) не менее 6-ти карандашей одного цвета? в) хотя бы 1 карандаш каждого цвета? г) не менее 6-ти синих карандашей?

Решение. а) В худшем случае возьмем по 3 карандаша красного, синего и желтого цветов. А 10-ый карандаш, какого цвета он ни был, будет 4-ым по счету для какой-то тройки карандашей, взятой ранее. б) В худшем случае возьмем по 5 карандашей красного, синего цветов и 4 желтых карандаша. А 15-ый карандаш, какого цвета он ни был, будет 6-ым по счету для какой-то пятерки карандашей, взятой ранее. в) В худшем случае возьмем 10 красных и 8 синих карандашей, тогда 19-ый карандаш будет желтого цвета. г) В худшем случае возьмем 10 красных, 4 желтых и 5 синих карандашей, тогда 20-ый карандаш будет 6-ым карандашом синего цвета.

Маугли положил 3 различных типа фруктов в мешок, всего в мешке 30 штук этих фруктов. Чтобы наверняка вынуть из мешка апельсин, (не заглядывая в мешок), Маугли должен вынуть из него 19 фруктов. Чтобы наверняка вынуть из мешка кокос, Маугли должен вынуть 24 фрукта. Сколько фруктов должен вынуть из мешка Маугли (не заглядывая в него), чтобы быть уверенным, что он вынет по крайне мере один фрукт каждого вида?

Решение. Если, чтобы наверняка вынуть из мешка апельсин, надо вытащить 19 фруктов (и 19-ый - апельсин), то в мешке 12 апельсинов. По такому же правилу можно вычислить, что в мешке 7 кокосов. (30-23=7). А других фруктов =11. Чтобы вынуть по одному фрукту каждого вида, надо вытащить =24 фрукта. И даже если не очень повезет, и мы вынем сначала 12 апельсинов, потом 11 "других" фруктов, то все равно будет хотя бы 1 кокос!