Фантазии по принципу "ящиков"

МУНИЦИПАЛЬНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА «ЮНОСТЬ»

МУНИЦИПАЛЬНЫЙ КОНКУРС

ЮНОШЕСКИХ ИССЛЕДОВАТЕЛЬСКИХ РАБОТ «ДЕНЬ НАУКИ»

ПРОЕКТНАЯ РАБОТА

по направлению «Математика и информатика»

на тему: «Фантазии по принципу «ящиков»»

Выполнил

Караев Денис

Дмитриевич

Класс: 8

Научный руководитель:

Федулова Наталья

Борисовна

Должность:

учитель математики

г. Клин, 2015 г.

Оглавление:

1. Введение 3-4 стр

2. Что такое «Schubfach­prinzip»? 4- 6 стр.

3. Доказательство существования 6-9 стр.

4. Принцип Дирихле для младших школьников 9- 11 стр.

5. Задачи по комбинаторике 11-12 стр.

6. Геометрические задачи 12-13 стр.

7. Олимпиадные задачи 13-17 стр.

8. Заключение 17 стр.

9. Список использованной литературы и электронных ресурсов 18 стр.

“Многие вещи нам непонятны не потому, что наши понятия слабы; но потому, что сии вещи не входят в круг наших понятий”. Козьма Прутков.

1. Введение.

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

Оказывается, принцип Дирихле придумал немецкий математик Дирихле Петер Густав Лежен, родившийся в 1805 году в небольшом немецком городке Дюрен. С 1822-1827 Дирихле был обычным домашним учителем в Париже. Там он ходил в кружок молодых ученых, которые

группировались вокруг Ж. Фурье. В 1827 году, Дирихле уехал в Бреславль, где занял место доцента. Переехав в 1829 году в Берлин, он продолжил свою работу. Начиная с 1831 и заканчивая 1855, Петер Густав Дирихле являлся профессором Берлинского университета, а после смерти К. Гаусса в 1855 году он стал профессором Геттингенского университета. Умер Дирихле 5 мая 1859 года в Геттингене. Основные труды Петер Густава Дирихле были сосредоточены в области теории чисел и математического анализа. Талантливый математик доказал теорему о существовании бесконечно большого числа простых чисел, впервые точно сформулировал и исследовал понятие условной сходимости ряда, дал строгое доказательство возможности разложения в ряд Фурье функции, имеющей конечное число максимумов и минимумов. Значительные его работы были посвящены механике и математической физике. [4]

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

Задачи:

1. Изучить литературу о жизни Дирихле и его принципе.

2. Рассмотреть различные формулировки и доказательства принципа Дирихле.

3. Выяснить на практике, в игровой форме применение принципа Дирихле.

4. Применить данный принцип при решении разнообразных задач.

5. Выяснить важность, интерес и пользу от этого метода. Узнать возможность применения его в повседневной жизни и возможность развития логического мышления.

6.Убедить вас, что некоторые олимпиадные задачи решаются, используя этот удивительный принцип.

2. Что такое «Schubfach­prinzip»?

Самым же первым и основным названием принципа Дирихле являлось «Schubfach­prinzip», которое и придумал сам создатель. В переводе с немецкого «Schubfach­prinzip» означает “принцип ящиков”. В комбинаторике, «Schubfach­prinzip» - это утверждение, которое Дирихле сформулировал связь между объектами, то есть зайцами и контейнерами – клетками. А в английском и многих других языках этот принцип носит еще одно название – «Pigeonholeprinciple», что в переводе означает “принцип голубей и ящиков” и является еще одной формулировкой принципа Дирихле. Но помимо этих двух основных формулировок, люди придумали и другие. [5]

Моё видение данного принципа в рассуждениях, которые я сам придумал:

• На моем андройд смартфоне на рабочем столе имеется 48 мест для ярлыков. Известно, что мне нужно расположить на нем 49 ярлыков, то по принципу Дирихле на одном месте расположатся 2 ярлыка. И, так как Google, по-моему, знал принцип Дирихле, то на том месте, где должны были располагаться 2 ярлыка, автоматически создастся папка, в которой и будут эти самые 2 ярлыка.

• В банкетном зале работники расставили вокруг столов 127 стульев. Известно, что на свадьбу пришли 128 гостей, то по принципу Дирихле, на одном стуле, на празднике будут сидеть два человека, а так как такого быть не может, то этот 128 человек - или тамада, или он ошибся залом.

Например, более распространенной является следующая формулировка:

Если кролики рассажены в клетки, а число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.

А вот более обобщенная, формулировка:

Если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее кроликов, а также хотя бы в одной клетке находится не более кроликов.

Но существуют еще несколько формулировок для частных случаев:

Если число клеток больше, чем число кроликов, то, как минимум одна клетка пуста.

Но все же самая популярная и на мой взгляд самая простая формулировка - это: "Если в n клетках сидит n+1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца". Но должен заметить, что вместо зайцев можно использовать какие-нибудь предметы, математические объекты (числа, отрезки, места в таблице и т.д.) И у принципа Дирихле есть несколько названий: "принцип кроликов и клеток", "принцип ящиков и объектов", "принцип ящиков и голубей". [1]

3. Доказательство существования.

Дирихле очень успешно и часто использовал свой метод доказательства ''от противного''. Возможно, многие знают, что это за метод, но я все же расскажу. Доказательство ''от противного'' – это доказательство с помощью исключения чего-либо. Мы с вами говорим о принципе Дирихле, который гласит: «Нельзя посадить 7 кроликов в 3 клетки, чтобы в каждой было не больше 2 кроликов».

Итак, доказательство:

Докажем принцип Дирихле методом

«от противного». Пусть после того, как мы

рассадили всех кроликов по клеткам, в

каждой из них сидит не более одного кролика.

Тогда во всех N клетках не может сидеть более чем N кроликов. Но по условию, рассаженных кроликов не меньше, чем N+1. Возникает противоречие. Следовательно, хотя бы в одной клетке сидит не меньше двух кроликов. [6]

Да, возможно для кого-то этот принцип покажется слишком легким, очевидным, и может даже глупым, но, несмотря на это, он является очень эффективным методом решения логических задач. Однако во всех этих задачах нелегко догадаться, что принимать за ''зайцев'', а что за ''клетки''. Но если вы догадались, что есть что, то вы без проблем решите эту задачу.

Чтобы применять принцип Дирихле в решении задач нужно:

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

2) научиться получать “клетки”, которых чаще всего меньше или больше, чем “зайцев” на одну (или более);

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

Оказывается, принцип Дирихле используется и в теоремах. А это значит, что принципом Дирихле пользовались и ученые-математики, создававшие теоремы. Одну из них мы сейчас и рассмотрим. Ее разбирают в школьном курсе алгебры, только без доказательства, но мы сейчас с вами рассмотрим и доказательство к ней. Итак, начнем. Теорема звучит следующим образом:

ТЕОРЕМА 1.Пусть p, q - натуральные числа, pq. Если обыкновенную дробь p/q обратить в десятичную, то получится либо конечная, либо бесконечная периодическая десятичная дробь, причём длина периода не превосходит q-1.

Доказательство. Доказательство данной теоремы заключается в делении чисел “в столбик”, а это значит, что на протяжении почти всего доказательства мы будем делить p на q "в столбик" и следить за остатками. Если на каком-то шаге нашего с вами деления остаток будет нулевым, то мы получим конечную дробь. Если же все остатки будут больше нуля или, проще говоря, больше нуля, то рациональное число p/q запишется в виде бесконечной десятичной дроби. Теперь, докажем, что она будет периодической. Итак, как вы видите на рисунке, каждый раз при нахождении очередной цифры частного у нас получается в остатке одно из чисел 1, 2, ..., q-1. Эти возможные значения остатков мы и примем за "клетки", так что всего имеется q-1 "клеток". Ну а "зайцами" у нас будут остатки, которые получаются в действительности при выполнении деления. А сейчас, давайте рассмотрим первых q "зайцев". Из-за того, что их на 1 больше, чем число "клеток", то по принципу Дирихле хотя бы два "зайца" попадут в одну "клетку". Другими словами, не более, чем через q - 1 шагов начнут повторяться остатки, а вслед за этим - и цифры в частном. А ведь и правда, если на некотором шаге повторился остаток, то, если мы припишем как обычно к нему 0, то получим то же число, что было прежде, а, значит, мы снесём в частное ту же цифру, что и раньше; вот именно из-за этого наши действия начнут повторяться. Таким образом, получится периодическая десятичная дробь с периодом длиной не более q - 1.

Рассмотрим действенность принципа Дирихле на задачах.

4. Принцип Дирихле для младших школьников. [7],[8]

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

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

Решение. В русском алфавите 33 буквы. Учеников в классе – 35. Примем буквы алфавита за “клетки”, а учеников – за “зайцев”, то по принципу Дирихле найдутся хотя бы два ученика, чьи фамилии начинаются в одной и той же буквы.

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

Решение. В году может быть максимум 366 дней, то по принципу Дирихле учеников может быть максимум n+1, то есть 366+1=367 учеников.

Задача 3. 15 детей собрали 100 орехов. Докажите, что, хотя бы два из них собрали одинаковое число орехов.

Решение. При решении этой задачи мы должны использовать метод “от противного”. Предположим, что каждый из детей собрал бы разное число орехов, то орехов должно было бы быть не меньше 0+1+2+3…+14 = (15·14):2 = 105 орехов, значит, наше предположение неверно, т.е. хотя бы двое собрали одинаковое число орехов.

Задача 5. Сто человек сидят за круглым столом, причем более половины из них – мужчины. Докажите, что найдутся два мужчины, сидящие друг напротив друга.

Решение. Число пар, сидящих друг напротив друга равно 50. Так как мужчин как минимум n+1, то есть 50+1, то по принципу Дирихле найдется хотя бы одна пара мужчин, сидящих друг напротив друга.

Задача 6. В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

Решение: 25 ящиков - «кроликов» рассадим по 3 клеткам-сортам. Так как 25 = 3 • 8 + 1, то применим «обобщенный принцип Дирихле» для N = 3, k = 8 и получим, что в какой-то клетке-сорте не менее 9 ящиков.

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

А сейчас мы решим уже более современные задачки.

Задача 7. Есть 6 человек в случайной группе Facebook. Доказать, что есть либо 3 человека, которые все друзья, или 3 человека, которые все чужие.

Решение. В данной задаче мы не можем применить принцип Дирихле непосредственно. Выберем любое лицо А и рассмотрим другие 5 человек, которые будут наши голуби. Среди оставшихся пяти обязательно найдутся либо трое (как минимум) знакомых с ним, либо трое (как минимум) незнакомых с выбранным. Например, возьмём любых трёх человек . Среди этих троих людей либо найдутся двое знакомых – тогда они вместе с выбранным нами человеком А образуют нужную тройку, либо они все трое попарно незнакомы.

5. Задачи по комбинаторике.

Задача 8. Какое наибольшее число королей можно расставить на шахматной доске так, чтобы они не били друг друга? [3]

Решение. Начнем с того, что на шахматной доске 64 клетки. Король может ходить в любую сторону, но только на одну клетку. Всего на шахматной доске можно расположить 16 королей так, как показано на рисунке 1. Теперь докажем, почему 16 – это максимальное число королей, которые мы можем расположить на шахматной доске. Тут мы воспользуемся методом “от противного”. Предположим, что мы можем разместить на доске 17 королей, разбив доску на 16 равных квадратов, как показано на рисунке 2. Давайте примем эти квадраты за “ящики”, а королей – за “зайцев”, то по принципу Дирихле хотя бы в одном “ящике” будет больше одного короля, то есть на одной клетке располагаются 2 короля, а такое невозможно, то на шахматной доске можно разместить не больше 16 королей.

Особенностью следующей задачи является то, что в ней принцип Дирихле применяется последовательно несколько раз.

Задача 9. Восемь футбольных команд провели турнир (каждая сыграла с каждой один раз). При этом не было «ничьих». Докажите, что можно выделить такие четыре команды А, В, С, D, что А выиграла у В, С и D; В выиграла у С и D; С выиграла у D. [9]

Решение. Так как по условию в турнире участвовали 8 команд, каждая из них сыграла с каждой по одному разу, и не было “ничьих”, то всего было произведено …матчей, каждый из которых заканчивались победой какой-либо команды. Распределим все 28 побед между 8 командами, приняв победы за “кроликов”, а 8 команд – за “ящики”, то по принципу Дирихле найдется хотя бы одна команда A, у которой не меньше n+1=3+1=4 побед. Эти четыре команды провели между собой 6 матчей, то было 6 побед. И снова, воспользовавшись “принципом ящиков и кроликов” примем 4 команды за “ящики”, а 6 побед – за “кроликов”, то по принципу Дирихле найдется такая команда B, одержавшая не менее 2-ух побед над командами C и D. Теперь предположим, что в матче между командами C и Dпобедили команда C, то получим: A победила B, C и D. B победила C и D. И C победила D.

Вот мы и нашли четыре команды, удовлетворяющие условию задачи.

6. Геометрические задачи.

Попробуем применять принцип Дирихле к площадям.

Но прежде чем мы начнем их решать, я расскажу вам о еще одной формулировке, применяемой к фигурам:

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

А для площадей применяют следующую формулировку:

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

Задача 10. Внутри равностороннего треугольника со стороной 1 расположено 5 точек. Доказать, что расстояние между некоторыми двумя из них меньше 0,5. [10]

Решение.

Проведем 3 отрезка, соединяющие середины противоположных сторон треугольника. Эти отрезки делят треугольник 1х1х1 на четыре равных треугольника со сторонами 0,5. Представим, что треугольники – это “клетки”, а точки – “зайцы”, то по принципу Дирихле хотя бы две точки окажутся в одном из четырех треугольников. Расстояние между этими двумя точками будет меньше, чем 0,5, так как они не лежат в вершинах маленьких треугольников.

Задача 11. Доказать, что если прямая l, расположенная в плоскости треугольника ABC, не проходит ни через одну из его вершин, то она не может пересечь все три стороны треугольника. [9]

Решение.

Полуплоскости, на которые прямая l разбивает плоскость треугольника ABC, обозначим через q₁ и q₂. Полуплоскости q₁ и q₂ будем считать открытыми, так как они не содержат точек прямой l. Представим, что вершины рассматриваемого треугольника (точки A, B, C) – это "зайцы", а полуплоскости q₁ и q₂ - "клетки". Каждый "заяц" попадает в какую-нибудь "клетку" так как прямая l не проходит ни через одну из точек A, B, C. Учитывая то, что "зайцев" трое, а "клеток" только две, то найдутся два "зайца", попавшие в одну "клетку", то есть, найдутся такие две вершины треугольника ABC, которые принадлежат одной полуплоскости.

7. Олимпиадные задачи.

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

1. Среди любых n + 1 целых чисел найдутся два числа, которые при делении на n дают одинаковые остатки.

Доказательство. Пусть заданные n + 1 чисел выступят в качестве кроликов, а остатки при делении этих чисел на n в качестве клеток. Всего может получиться n различных остатков: 0, 1, …, n – 1 (клеток), поэтому, хотя бы два числа будут иметь одинаковые остатки.

2. Среди любых n + 1 целых чисел найдутся два числа таких, что их разность делится на n.

Доказательство. Применяя первую формулировку, по крайней мере, два числа из n + 1 дают одинаковый остаток при делении на n.

Пусть это будут c = n·a + r и d = n·b + r.

Тогда их разность делится на n: c – d = n(a – b).

Решим задачу олимпиадного характера, применяя доказанные формулировки.

Задача 13. Доказать, что среди n целых чисел можно выбрать несколько чисел (может быть, одно), сумма которых делится на n. [3]

Доказательство. Рассмотрим n следующих сумм:

S₁ = x₁, S₂ = x₁ + x₂, ..., S_n = x₁ + x₂ + x₃ + ... + x_n. Если какая-то одна из этих сумм делится на n, то берём её.

Пусть ни одно n из чисел S₁, S₂, ... , S_n (зайцев) не делится на n. Тогда при делении этих сумм на n может быть n – 1 остатков (клеток): 1,…, n – 1. То два из них при делении на n обязательно дадут равные остатки (по доказанному выше). Пусть это S_k и S_m (k m), тогда разность S_m – S_k = (x₁ +. . .+ x_m) – (x₁ +. . .+ x_k) = x_{k + 1}+. . .+ x_m делится на n, и поэтому сумма x_{k + 1}+. . .+ x_m является искомой.

Задача 14. Мистер и миссис Смит пригласили к себе в дом четыре пары гостей. Некоторые из приглашенных были друзьями миссис Смит, а некоторые друзьями мистера Смита. Когда гости прибыли, те, кто знали друг друга ранее, пожали руки. Когда всё это произошло, мистер Смит говорит: «Как интересно! Если не считать меня, то здесь никто не поздоровался за руку одинаковое количество раз». Вопрос: сколько раз пожала руку миссис Смит? [2]

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

1) Каждый человек вечеринки будет представлен отдельной вершиной (рис. 3.4). Ребра графа на нарисованном нами рисунке будут соответствовать рукопожатиям. Семейные пары будут обосабливаться рамкой. Пока что нам известно лишь то, что все присутствующие кроме мистера Смита совершили различное количество рукопожатий. Максимальное количество рукопожатий, которые могло быть совершено равно 8, так как всего гостей десять, а со своим спутником никто не здоровался, отсюда и следует, что 8 – максимум. Поэтому все вершины мы пронумеруем числами от 0 до 8, а одну вершину мы обозначим просто как Смит, так как мы еще не знаем сколько рукопожатий он совершил. Самих же гостей мы пронумеруем по количеству сделанных ими рукопожатий, то есть, если мы будем говорить фразу “четвертый человек”, то это будет означать, что он совершил 4 рукопожатия.

2) Итак, рассмотрим поподробнее 8-ого гостя (рис. 3.5) Он не здоровался лишь с одним человеком с одной какой-то стороны, а с другой стороны, он скорее всего не здоровался со своей парой. Еще, мы точно знаем точно, что он не здоровался с нулевым гостем, так как количество рукопожатий нулевого гостя равно нулю, следовательно, нулевой гость и есть его спутник. Со всеми остальными гостями восьмой гость поздоровался.

3) Теперь давайте примемся за 7-го гостя (рис.3.6). Он не поздоровался за руку сего партнёром и нулевым гостем. Ведь нулевой гость не может быть партнёром 7-ого гостя, так как нулевой и восьмой гости образуют пару. На графе показано, что первый гость поздоровался с восьмым гостем, но так как мы знаем, что восьмой гость в принципе поздоровался лишь с одним человеком, то он не мог поздороваться с седьмым гостем. Значит, первый и седьмой гости образуют пару, а седьмой гость поздоровался со всеми гостями, кроме нулевого и первого гостя.

4) По такому же принципу мы можем узнать, что шестой гость не здоровался с гостями 0, 1 и 2, и что 2-ой гость является его спутником. Отсюда можно

аналогично получить, что пятый гость не здоровался с гостями 0, 1, 2 и 3, и что третий гость является его спутником. Результат представлен на рисунке 3.7

Ответ. Вот мы и нашли пару для всех людей, кроме четвертого. А единственной возможной парой для четвертого человека стал мистер Смит. Из этого следует, что четвертый человек – это миссис Смит, и она пожала руку ровно четырем людям.

8. Заключение.

И вот, мой рассказ о принципе Дирихле подошел к концу. А это значит, что пора подвести итоги. В данном проекте, я познакомился с таким способом решения задач, как принцип Дирихле. Я узнал, что создателем данного принципа являлся талантливый немецкий математик Дирихле Петер Густав Лежен, имеющий много научных открытий в разных областях. Я научился пошагово разбирать и решать задачи с применением принципа Дирихле, выяснил его действенность. Я убедился в использовании данного метода при решении олимпиадных задач и в том, что данный метод дает нам возможность обобщать. И вообще, я считаю, что открытие такого легкого в использовании метода решения задач заслуживает уважения к его создателю.

А закончу я, пожалуй, словами Георга Лихтенберга:“Великий гений редко делает открытия, следуя по чужому пути. Если он делает открытие, то он обычно открывает и пути, ведущие к нему”.

Список использованной литературы и электронных ресурсов:

1. Мерзляков А.С., “Принцип Дирихле. Факультативный курс”, Ижевск: НПЦ Бизнес Старт, 1993. — 87 с.

2. Болтянский В.Г., Леман А.А. «Сборник задач московских математических олимпиад» , М.: Просвещение , 1965 г.-384 с.

3. Бабинская И. Л. “Задачи математических олимпиад.” М.: Наука, 1975. – 112 с.

4.http://www.people.su/64140

5.http://demonstrations.wolfram.com/ThePigeonholePrincipleDiskCoverings/

6. http://www.slideshare.net/rasparin/ss-6848149

7. http://www.mccme.ru/courses/dirihle.html

8. http://www.zaba.ru/cgi-bin/tasks.cgi?tour=books.mk1.dirikhle

9.http://www.problems.ru/articles/216.php

10. http://bars-minsk.narod.ru/teachers/dirichle.html