Реферат по теме: "Принцип Дирихле"

            ГБОУ лицей «Международная космическая школа

                                     им. В.Н. Челомея»

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

           Реферат по алгебре

                                                        Подготовила ученица 10а класса

                                                                    Галицкая Марина

                                                       Научный руководитель Тё Ольга    

                                                                    Владимировна

                                     Байконур 2015

Содержание:

① Введение;

② Основная часть;
а) Принцип Дирихле
б) Обобщенный принцип Дирихле
в) Принцип недостаточности
г) Раскраска                                                                                                          д) Использование принципа Дирихле в олимпиадах
③ Заключение;                                                                                             

④Список литературы.

① Введение

Математика - древняя наука. Она существовала и была актуальна ещё до нашей эры, остаётся таковой и сейчас. За время развития математики было создано много теорий, правил, формул с целью решения задач различными способами. Одним из ведущих математиков, работавших над исследованием разных способов решения задач, является немецкий математик Иоганн Петер Густав Лежён Дирихле. Ему принадлежат крупные открытия в самых разных областях математики, а также в механике и математической физике. Он вывел множество формул и принципов решения задач. Один из них так и называется - Принцип Дирихле.

 Цели работы:

1) Ознакомиться с биографией Дирихле.

2) Изучить такой метод решения олимпиадных задач, как принцип Дирихле и познакомиться с различными вариациями этого принципа.

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

4) Определить значимость принципа Дирихле для решения математических задач.

Иоганн Петер Густав Лежён Дирихле-13 февраля 1805, Дюрен, Французская империя, ныне Германия — 5 мая 1859, Гёттинген, королевство Ганновер, ныне Германия. Дирихле (с учетом этимологии его правильнее было бы называть Диришле) родился в вестфальском городе Дюрене в семье почтмейстера. Его предки были выходцами из бельгийского городка Ришле (Richelet), этим обусловлено происхождение необычной для немецкого языка фамилии. Часть фамилии «Лежён» имеет аналогичное происхождение — деда называли «молодым человеком из Ришле» (фр. Le Jeune de Richelet).

В 12 лет Дирихле начал учиться в гимназии в Бонне, спустя два года — в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом.

С 1822 по 1827 год жил в качестве домашнего учителя в Париже, где вращался в кругу Фурье.

В 1825 году Дирихле вместе с А. Лежандром доказал великую теорему Ферма для частного случая n=5. В 1827 г. молодой человек по приглашению Александра фон Гумбольдта устраивается на должность приват-доцента университета Бреслау (Вроцлав). В 1829 г. он перебирается в Берлин, где проработал непрерывно 26 лет, сначала как доцент, затем с 1831 г. как экстраординарный, а с 1839 г. как ординарный профессор Берлинского университета.

В 1831 году Дирихле женится на Ребекке Мендельсон-Бартольди, сестре знаменитого композитора Феликса Мендельсона-Бартольди.

В 1855 году Дирихле становится в качестве преемника Гаусса профессором высшей математики в Гёттингенском университете. В числе его достижений — доказательство сходимости рядов Фурье.

Он внёс существенный вклад в математический анализ, теорию функций и теорию чисел. Являлся членом Берлинской и многих других академий наук, в том числе Петербургской. Основные заслуги П. Дирихле в области математики:

-доказал теорему о том, что в арифметической прогрессии, первый член и разность которой- взаимно простые числа, содержится бесконечно много простых чисел;

-исследовал понятие условной сходимости ряда, установил признак сходимости ряда

-ввел функциональные ряды особого вида

-ввел определение функции через соответствие и т.д.

② Основная часть;

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

Знаете ли вы, что среди зрителей, сидящих в Большом театре во время спектакля, обязательно есть люди, родившиеся в один и тот же день одного и того же месяца? Подсчитаем: в зале большого театра 2000 мест. И даже если не все они заполнены (что в этом знаменитом театре бывает нечасто), можно смело утверждать, что на спектакле собралось более 366 человек. Но 366 - это максимально возможное число дней в году, считая 29 февраля. Итак, для 367-го зрителя просто не остаётся свободной от дней рождений его соседей по залу даты в году. Просто? Тем не менее это рассуждение даже имеет своё название в математике: принцип Дирихле. Рассмотрим, на чем он основан.

По традиции принцип Дирихле всегда объясняют на примере кроликов в клетках: если общее число кроликов больше числа клеток, в одной из этих клеток наверняка сидит более одного кролика. Также этот принцип может выглядеть следующим образом: в n клетках невозможно рассадить поодиночке n+1 кроликов, т.е найдётся клетка, где сидят не менее двух кроликов. Чтобы применить принцип Дирихле к решению задач, надо указать, что принимать за "клетки", а что за "кроликов", а также указать способ, которым надо усаживать "кроликов" в "клетки".

А теперь рассмотрим примеры задач.

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

Решение: Примем за "клетки" количество ёлок. Всего "клеток" будет 600001 (0,1,2,...600000). А за "кроликов" иголки. По принципу Дирихле получим, что найдётся "клетка", где сидят не менее двух "кроликов". А это и означает, что найдутся две ёлки имеющие одинаковое количество иголок.

Задача2. Докажите, что в Вашем классе найдутся два человека, имеющие одинаковое число друзей среди своих одноклассников.

Решение: Предположим, что в классе 30 человек, тогда за "кроликов" возьмём учеников, а за "клетки" количество друзей. Друзей у каждого человека может быть 0,1,...,29 т.е. у нас получится 30 "клеток". Но "клетки" 29 и 0 одновременно существовать не могут т.к. если человек имеет 29 друзей, то каждый из его друзей будет иметь хотя бы одного друга, значит всего может быть 29 "клеток" (0,1,...,28 или 1,2,...,29). По принципу Дирихле получим, что найдётся "клетка", где сидят не менее двух "кроликов". А это и означает, что найдутся два человека имеющие одинаковое число друзей. Можно сделать вывод, что в задачах на принцип Дирихле надо правильно распределить что будет "кроликами", а что "клетками". Также чтобы решить задачу на принцип Дирихле, надо найти правильное число "кроликов" и" клеток" исходя из условия задачи.

А теперь рассмотрим обобщенный принцип Дирихле.

Обобщенный принцип Дирихле. Чаще всего в задачах применяется не Принцип Дирихле, а некоторое его свойство, которое называется обобщённый принцип Дирихле. Рассмотрим задачи с применением не самого принципа Дирихле, а некоторого его обобщения, которое сформулировано ниже, и которое обычно встречается в задачах.

Формулировка 1.

Пусть даны n клеток и nk + 1 кроликов размещены в эти клетки. Тогда найдется клетка, где сидят не менее k + 1 кроликов.

Формулировка 2.

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

Доказательство: если бы в каждой клетке сидело не более k зайцев, то во всех клетках было бы не более nk зайцев, что противоречит условию. Обобщение принципа используют, когда требуется выявить несколько (три и более) объектов, обладающих некоторым свойством. Разберём несколько примеров.

ПРИМЕРЫ ЗАДАЧ

Задача.

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

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

Дано:                                           Решение:

n=8

nk+1=20

k-?

Задача.

В пяти классах школы учатся 160 человек. Доказать, что найдутся 4 человека, у которых день рождения приходится на одну и туже неделю.

Решение: В году может быть максимально 53 недели. Их и примем за "клетки" а, за "кроликов" примем ребят. Рассаживаем "кроликов" по тем "клеткам", которые соответствуют их дням рождения. В силу принципа Дирихле найдётся "клетка" по меньшей мере с четырьмя "кроликами", а это и означает, что найдётся неделя, когда день рождения сразу у четырёх человек.

Дано:                                                  Решение:

n=53

nk+1=160

k-?

Задача. У человека на голове не более 400000 волос, в Москве более 8 млн. жителей. Докажите, что найдутся 20 москвичей с одинаковым числом волос.

Решение: По условию на голове у каждого из москвичей может быть от 0 до 400000 волос имеем всего 400001 возможность. Предположим, что утверждение задачи неверно. Тогда лысых москвичей найдется не более 19, имеющих 1 волос тоже не более 19, ..., имеющих 400000 волос тоже не более 19. Но тогда всего москвичей не более 19 ×400001 = 7600019, что меньше 8 миллионов противоречие.

Дано:

n=400001

nk+1=8000000

k-?

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

1) Применить метод доказательства от противного и вычислить количество необходимых значений.

2) Выбирать, что принять за "клетки" и что взять за "кроликов". Применяя непосредственно принцип Дирихле, устанавливая существование того, что искали.

Также с помощью принципа Дирихле можно решать задачи на комбинаторику, в которых, например, надо достать какое-либо количество предметов разного цвета или типа (пары носков или перчаток разных цветов). Данные задачи приведены ниже.

Задача. В ящике лежат 10 пар чёрных и 10 пар красных перчаток одного размера. Сколько перчаток надо вытащить из ящика наугад, чтобы наверняка среди них были: а) Две перчатки одного цвета; б) Одна пара перчаток одного цвета?

Решение: а) Если за "клетки" принять цвета перчаток, то, взяв любые три печатки, получится, что в одной из "клеток" находятся два "кролика"- перчатки. А это и требуется.

б) Можно взять 20 перчаток на одну руку, но из них нельзя будет выбрать одноцветную пару перчаток, поэтому искомое число не меньше 21. Доказать, что число 21 является искомым. Примем за "клетки" цвета перчаток (их два). В качестве "кроликов" возьмём перчатки. Согласно обобщённому принципу Дирихле в одной из "клеток" будет не меньше 11 "кроликов". Это означает, что найдётся 11 пар перчаток одного цвета. Но имеется только 10 пар перчаток одного цвета, поэтому все они не могут быть на одну руку. Значит, среди этих 11 пар перчаток найдётся одна пара перчаток одного цвета.

Дано:                                              Решение:

n=2

nk+1=21

k+1-?

Принцип недостаточности.

У принципа Дирихле есть аналогичные ему принципы. Таковым является принцип недостаточности. Судя по названию, эта формула основывается на недостаточности какого-то количества предметов. Так и есть. Ниже приведена формула принципа недостаточности и её доказательство.

Если разместить не более () кроликов в n клеток , то найдутся хотя бы две клетки, в которых сидят по одинаковому числу кроликов.

Доказательство. Допустим, что в каждой из n клеток по разному числу кроликов. Это означает, что во всех этих клетках находится не менее 0+1+2+...+(n – 1) кроликов. Подсчитаем эту сумму. Для этого будем складывать пары 0+n-1, 1+(n-2), 2+(n-3)... . Замечаем, что сумма этих пар постоянна и равна n - 1. Количество пар равно n/2 , если n чётное; если же n- нечётное, то можем рассматривать только (n−1)/2 пар и прибавить к ним средний член, который равен (n−1)/2 . В сумме получается число, не зависящее от чётности n, и оно равно ((n−1)/ 2) × 𝑛, т.е. кроликов должно быть больше чем у нас есть. Значит сделанное предположение неверно, т.е. найдутся две клетки, где сидят по одинаковому числу кроликов. Рассмотрим примеры некоторых задач.

Задача. 15 мальчиков собрали 100 орехов. Доказать, что два из них собрали одинаковое число орехов (каждый набрал хотя бы по одному ореху).

Решение: Принимая за "клетки" корзинки мальчиков, за "кроликов" - орехи и применяя принцип недостаточности (n=15), получаем, что в каких- то двух "клетках" находится по равному числу кроликов. Это и означает, что найдутся два мальчика, которые собрали по одинаковому числу орехов.

Дано:                                                                Решение:

k=100(количество кроликов- орехов)

n=15(количество клеток- мальчиков)

Доказать, что два                                                                                                                   из них собрали одинаковое                                                                                                                       число орехов,

т.е. ()к

Раскраска.

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

Формула раскраски. Если рассадить n кроликов в n-1 клеток, то найдётся по крайней мере одна свободная клетка. Также может использоваться и другая формулировка: если число клеток больше числа кроликов, то как минимум одна клетка пуста.

Задача. Каждая грань куба раскрашена в чёрный или белый цвет. Доказать, что найдутся одинаково раскрашенные грани, имеющие общее ребро. Решение: Рассмотрим любую вершину куба. В ней пересекаются три грани. Примем за "клетки" цвета, а за кроликов грани, пересекающиеся в одной вершине (их три). Поэтому согласно принципу Дирихле, найдутся два "кролика" в одной "клетке", а это и означает, что найдутся две грани имеющие общее ребро (так как они имеют общую точку) и окрашенные одинаково.

Задача. В прямоугольнике 5×6 закрашено 19 клеток. Докажите, что в нём можно выбрать квадрат 2×2, в котором закрашено не менее трёх клеток. 
Решение 

Разделим прямоугольник на 6 частей по 5 клеток (Cм. рисунок). Согласно принципу Дирихле, в одной из этих частей будет закрашено не менее 4 клеток. Тогда в квадрате 2×2, содержащемся в этой части, закрашено либо 3, либо 4 клетки. Это и будет искомый квадрат.

А теперь рассмотрим задачи, встречающиеся в различных олимпиадах с применением принципа Дирихле.

Составители вступительных экзаменов в сильные математические школы очень любят включать в свои варианты олимпиадные задачи на принцип Дирихле.

     

Например:

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

Решение. Принимая за "клетки" школы района, а за "кроликов" компьютеры, которые распределили между школами, применяя принцип недостаточности (n=15 ), получаем, что в каких-то двух "клетках" находится по равному числу кроликов. Это и означает, что найдутся две школы, которые получили по одинаковому числу компьютеров.

Механико-математический факультет МГУ имени М.В. Ломоносова проводит занятия математических кружков. Один из таких кружков называется «Малый мехмат МГУ». На «Малом мехмате» работают кружки для школьников 1–11 классов. А на занятиях «Малого мехмата» школьники знакомятся с интересными математическими задачами, приучаются к логически строгим рассуждениям, постигают красоту и гармонию математики. Тематика кружков весьма разнообразна и, как правило, почти не связана со школьной программой по математике. В 5–8 классах решаются задачи на такие классические «кружковые» темы, как принцип Дирихле, инварианты, делимость, логика, комбинаторика и т.д.

Давайте рассмотрим некоторые задачи, которые решают школьники на «Малом мехмате».

В финальном матче школьного чемпионата по баскетболу команда 5А забила 9 мячей. Докажите, что найдутся два игрока этой команды, забившие поровну мячей. (В команде по баскетболу 5 игроков.)

Решение. Предположим, что такие два игрока не найдутся. Тогда все пять игроков забили разное количество мячей. Пусть первый игрок ничего не забил, второй забил один мяч, третий — два, четвёртый — три, пятый — четыре. Тогда всего игроки забили 10 мячей. Если же кто-то забил больше, чем мы предположили, то и всего мячей было забито больше. Но поскольку по условию игроки забили 9 мячей, наше предположение неверно. Значит, есть два игрока, забившие поровну.

На сайте МФТИ я посмотрела статистику тех тем, которые встречаются в их олимпиадах за 2014-2015 года.

По этой статистике из 10 олимпиадных заданий, одно будет на принцип Дирихле. Также на сайте МФТИ, создатели олимпиад предлагают список всех тем на основе которых будут базироваться олимпиады. Вот этот список:

Рекомендуемые темы по математике.

1) Индукция и метод математической индукции

2) Доказательство от противного

3) Элементы комбинаторики

4) Применение производной и интеграла при решении задач

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

6) Соответствие

7) Графы

8) Инварианты

9) Делимость и остатки, алгоритм Эвклида

10) Уравнения в целых числах.

11) Четность

Следующую задачу, которую мы здесь рассмотрим я взяла из олимпиады «Физтех», которую проводит МФТИ.

10 баллов.

 Имеется 2n (n>2) батареек, n из которых заряжено, а n разряжено. Радио работает только от двух заряженных батареек. За одну операцию разрешается вставить любые две батарейки в радио, и проверить - работает ли оно. За какое наименьшее количество операций, можно вставить в радио две гарантированно заряженные батарейки?

Решение: за n+3.

Занумеруем все батарейки. Пусть в радио будут вставляться следующие пары: 1-2, 2-3, 1-3 и 4-5, 5-6, 4-6. Остальные 2n-6 батареек разобьем на пары. Если среди первой или второй тройки будет две работающие батарейки, то задачу можно считать решенной. Если нет, то на оставшиеся 2n-6 батареек придется n-2 работающие. По принципу Дирихле, получим, что в какой-то из оставшихся пар (их n-3) будет 2 работающие батарейки.  За n+2 операции такие две батарейки указать нельзя. Покажем это по индукции. Для n=3 это очевидно. Пусть мы для всех наборов из 2k<2n батареек и k+2 пар (или операций) умеем приводить такой пример разбиения батареек на заряженные и незаряженные, что в каждой паре будет хотя бы одна разряженная. По принципу Дирихле, найдется батарейка, которую вставляли в радио не более одного раза. Пусть у неё будет номер 2n, а у той, с которой её вставляли 2n-1. Батарейку с номером 2n будем считать заряженной, а с номером 2n-1 разряженной. Для остальных батареек воспользуемся предположением индукции и так разобьем их на работающие и неработающие, что никакая из пар с ними работать не будет.

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

Задачи на принцип Дирихле могут попасться вам на региональных олимпиадах, на вступительных экзаменах в математические лицеи и ВУЗы.

В ходе работы были изучены различные научные материалы на принцип Дирихле, решено много интересных задач. Мы ознакомились с различными вариациями принципа Дирихле, такие как раскраска или принцип недостаточности. В ходе этой работы были рассмотрены разные способы решения задач. Был приобретён опыт решения данных задач, некоторые из них были взяты из олимпиад ведущих ВУЗов России и олимпиад краевого уровня. Все поставленные цели и задачи были достигнуты. Материал данного реферата в дальнейшем поможет учащимся разных классов при решении задач на принцип Дирихле и аналогичные ему принципы. Использованные в реферате задачи и их решения являются прекрасным практическим материалом для подготовки к олимпиадам и другим математическим конкурсам. Также эти данные можно использовать на уроках занимательной математики, что позволит развивать у ребят логическое мышление. Эта тема актуальна потому что многие из рассмотренных мною задач были взяты из олимпиад тех вузов, которые стали приезжать к нам в течении последних двух лет. Это - турнир Ломоносова, олимпиада «Физтех». Учащиеся нашей школы всегда показывали неплохие результаты как на уровне города, так и на Всероссийском уровне. Я надеюсь, что приобретенные знания помогут учащимся в случае, если им попадется задача на принцип Дирихле.

Список литературы:

http://mipt.ru/diht/abiturients/extra_olymp/arhiv_olimp/olimpiada2009_1/reshenie.php

http://ermine.narod.ru/MATH/STAT/DIRIHLET/sect1.htm

http://mipt.ru/

http://mmmf.msu.ru/

https://ru.wikipedia.org/wiki/

http://festival.1sept http://ru.wikipedia.org/wiki/ Дирихле_Петер_Густав_Лежён

 ember.ru/articles/635403/

http://lib.repetitors.eu/matematika/41-2009-12-06-17-47-09/2431

http://www.smekalka.pp.ru/math_dir.html

http://moikrug.ru/companies/730851604/

http://zadachi.mccme.ru/2012/#&page1

• 1 слайд

  Принцип Дирихле
  Галицкая Марина. 10 А
  ГБОУ лицей «МКШ» имени В.Н. Челомея
  2015г.
  

• 2 слайд

  
  
  
  Содержание:
  ① Введение
  ② Основная часть
  а) Принцип Дирихле
  б) Обобщенный принцип Дирихле
  в) Принцип недостаточности
  г) Раскраска
  д) Использование принципа Дирихле в олимпиадах
  ③ Заключение
  

• 3 слайд

  Цели работы:
  
  ①Ознакомиться с биографией Дирихле.
  
  ②Изучить такой метод решения олимпиадных задач, как принцип Дирихле и познакомиться с различными вариациями этого принципа.
  
  ③Показать, как принцип Дирихле можно применять при решении логических или олимпиадных задач и задач повышенного уровня.
  
  ④Определить значимость принципа Дирихле для решения математических задач.
  
  
  

• 4 слайд

  Иоганн Петер Густав Лежён Дирихле .(13 февраля 1805— 5 мая 1859).
  
  Основные заслуги П. Дирихле в области математики:
  -доказал теорему о том, что в арифметической прогрессии, первый член и разность которой, взаимно простые числа, содержится бесконечно много простых чисел;
  -исследовал понятие условной сходимости ряда, установил признак сходимости ряда;
  -ввел функциональные ряды особого вида;
  -ввел определение функции через соответствие и т.д.
  
  

• 5 слайд

• 6 слайд

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

• 7 слайд

  Решение. Примем за "клетки" количество ёлок. Всего "клеток" будет 600001 (0,1,2,...600000). А за "кроликов" иголки. По принципу Дирихле получим, что найдётся "клетка", где сидят не менее двух "кроликов". А это и означает, что найдутся две ёлки имеющие одинаковое количество иголок.
  В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.
  

• 8 слайд

  Обобщенный принцип Дирихле.
  Даны n клеток и nk + 1 кроликов размещены в эти клетки. Тогда найдется клетка, где сидят не менее k + 1 кроликов.
  

• 9 слайд

  В пяти классах школы учатся 160 человек. Доказать, что найдутся 4 человека, у которых день рождения приходится на одну и туже неделю.
  Дано: Решение:
  n=53 k=159:53
  nk=159 k=3 => (3+1)
  nk+1=160
  Доказать что у Ответ: Найдётся «клетка» по меньшей мере с (3+1) «кроликами», а значит
  4 человек день рождения найдётся неделя, когда день рождения сразу у четырёх человек.
  приходится на одну
  и туже неделю.
  
  

• 10 слайд

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

• 11 слайд

  В ящике лежат 10 пар чёрных и 10 пар красных перчаток одного размера. Сколько перчаток надо вытащить из ящика наугад, чтобы наверняка среди них были: а) Две перчатки одного цвета; б) Одна пара перчаток одного цвета?
  При взятии трёх перчаток мы получим:
  
  
  
  
  При взятии двух перчаток мы получим:
  
  

• 12 слайд

  Принцип недостаточности.
  Если разместить не более n(n−1)/2 − 1 кроликов в n клеток , то найдутся хотя бы две клетки, в которых сидят по одинаковому числу кроликов.
  

• 13 слайд

  Задача. 15 мальчиков собрали 100 орехов. Доказать, что два из них собрали одинаковое число орехов (каждый набрал хотя бы по одному ореху).
  

• 14 слайд

  Раскраска.
  
  Если рассадить n кроликов в n-1 клеток, то найдётся по крайней мере одна свободная клетка. Также может использоваться и другая формулировка: если число клеток больше числа кроликов, то как минимум одна клетка пуста.
  

• 15 слайд

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

• 16 слайд

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

• 17 слайд

  В финальном матче школьного чемпионата по баскетболу команда 5А забила 9 мячей. Докажите, что найдутся два игрока этой команды, забившие поровну мячей. (В команде по баскетболу 5 игроков.)
  
  2 3 4 5
  
  
  
  1 2 3 4 5
  

• 18 слайд

• 19 слайд

• 20 слайд

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

• 21 слайд

  Спасибо за внимание!
  

                            Под редакцией М.А. Галицкой

                 Сборник задач на тему:

                                                5-11 класс

                               Байконур 2015 

Содержание:

① Краткое ознакомление с теорией;

② Задачи;

③ Решения и ответы.

Вступительное слово:

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

Иоганн Петер Густав Лежён Дирихле – родился 13 февраля 1805, Дюрен, Французская империя, ныне Германия Гёттинген, королевство Ганновер, ныне Германия. Он внёс существенный вклад в математический анализ, теорию функций и теорию чисел. Являлся членом Берлинской и многих других академий наук, в том числе Петербургской.

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

Если общее число кроликов больше числа клеток, в одной из этих клеток наверняка сидит более одного кролика. Также этот принцип может выглядеть следующим образом: в n клетках невозможно рассадить поодиночке n+1 кроликов, т.е. найдётся клетка, где сидят не менее двух кроликов. Чтобы применить принцип Дирихле к решению задач, надо указать, что принимать за "клетки", а что за "кроликов", а также указать способ, которым надо усаживать "кроликов" в "клетки".

Обобщенный принцип Дирихле.

Даны n клеток и nk + 1 кроликов размещены в эти клетки. Тогда найдется клетка, где сидят не менее k + 1 кроликов.

Принцип недостаточности.

Если разместить не более n(n−1) / 2 − 1 кроликов в n клеток, то найдутся хотя бы две клетки, в которых сидят по одинаковому числу кроликов.

Раскраска.

Если рассадить n кроликов в n-1 клеток, то найдётся по крайней мере одна свободная клетка. Также может использоваться и другая формулировка: если число клеток больше числа кроликов, то как минимум одна клетка пуста.

На этом заканчивается теоретическая часть и мы переходим к следующей главе: «Задачи».

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

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

Задача 3. В классе учится 29 человек. Саша Иванов допустил в диктанте 13 ошибок, и никто другой не сделала большего числа ошибок. Доказать, что по крайней мере трое учащихся сделали одинаковое число ошибок.

Задача 4. В клетки прямоугольника 5×41 раскрашены в два цвета. Доказать, что можно выбрать три строки и три столбца так, чтобы все 9 клеток, стоящие на пересечение этих строк и столбцов, были одного цвета.

Задача 5. В саду растёт 10 яблонь. Общее количество яблок на них 43. Доказать, что найдётся две яблони на которых растут по одинаковому числу яблок (на каждом дереве растёт хотя бы по одному яблоку).

Задача 6. На улице 30 домов. В одном из них живёт пять человек, а в любом другом не более пяти человек (в каждом доме живёт хотя бы один человек). Доказать, что найдутся 8 домов в которых живут по одинаковому числу человек.

Задача 7. В тире стреляли в квадрат 5×5, и произвели 24 выстрела. Найдётся ли в этой фигуре квадрат 1×1, в котором нет дырки от пули?

Задача 8. В клетках таблицы 3×3 расставлены числа: -1, 0 и 1. Рассмотрим восемь сумм: суммы трёх чисел в каждой строке, в каждом столбце и по двум диагоналям. Могут ли быть все эти суммы различны?

Задача 9. Из любых трёх целых чисел можно выбрать два, сумма которых чётна. Докажите это.

Задача 10. В квадрате, составленном из 100 клеток, закрашено менее 50. Доказать, что на не закрашенные клетки можно положить кость домино, покрывающую ровно две клетки.

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

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

Задача 13*. Десять учителей математики составили для проведения математической олимпиады 35 задач. Известно, что среди них было по одному учителю, которые составили одну, две и три задачи. Докажите, что среди них найдется хотя бы один учитель, который составил не менее пяти задач.

Задача 14. В квадратном ковре со стороной 4 метра моль проела 15 дырок. Докажите, что из этого ковра можно вырезать коврик со стороной 1 метр, в котором дырок не будет.

Задача 15. В самолёте летят 380 пассажиров. Докажем, что, по крайней мере, двое из них родились в один и тот же день года.

Задача 16*. В шахматной партии чёрные сдались после 15-го хода белых. Требуется доказать, что, хотя бы одна из чёрных фигур ни разу не покидала своего поля (к фигурам отнесём и пешки).

Задача 17*. В строку выписано 5 натуральных чисел: a1, a2, a3, a4, a5. Докажите, что-либо одно из них делится на 5, либо сумма нескольких рядом стоящих чисел делится на 5.

Решения и ответы.

Задача 1.  Возьмём за "клетки" школьников, а за "кроликов" конфеты. Используя принцип Дирихле получим, что найдётся "клетка", где сидят не менее двух "кроликов". А это и означает, что найдётся школьник, который съел хотя бы две конфеты.

Задача 2. Пусть "клетками" будут месяцы, а "кроликами" - ученики. Используя принцип Дирихле получим, что найдётся "клетка", где сидят не менее двух "кроликов". А это и означает, что найдётся месяц, в котором отмечают свои дни рождения хотя бы два ученика.

Задача 3. Примем за "клетки" всевозможные варианты количества ошибок. Их 14, так как школьники могут сделать 0, 1, ..., 13 ошибок. А за "кроликов" примем школьников, которые писали диктант. Их по условию 29. Каждого из них сажаем в клетку, которая соответствует количеству ошибок, сделанных им. Тогда получим, что найдётся "клетка", в которой сидят по меньшей мере три "кролика", а это и означает, что найдутся трое школьников, сделавших одинаковое число ошибок.

Задача 4. Получим, что в любом из столбцов будет не менее трёх клеток одного (из двух) цветов. Можно воспользоваться принципом Дирихле, приняв за "клетки" цвета, а за "кроликов" - столбцы; "кролика" сажаем в ту "клетку", которая соответствует цвету большинства его раскрашенных клеток. Тогда получим, что в 21 столбце (из 41) будет по три раскрашенные одним цветом клетки (допустим - первым). В каждом из этих столбцов три раскрашенные клетки можно расположить 10 способами. Снова в силу принципа Дирихле получаем, что в трёх столбцах (из 21) закрашенные клетки будут располагаться одинаково. Проведём прямые через эти столбцы и через три одинаково закрашенные клетки. Эти 9 клеток пересечения и будут искомыми.

Задача 5. За "клетки" примем яблони, а за кроликов яблоки. Применяя принцип недостаточности получим, чтобы не было двух "клеток", в которых сидят по одинаковому числу "кроликов", всего "кроликов" должно быть не менее 44. По условию задачи их 43, значит найдутся две "клетки" в которых сидят по одинаковому числу кроликов. А это и означает, что в саду растёт две яблони, имеющие по одинаковому числу яблок.

Задача 6. За "клетки" примем количество человек, живущих в каждом доме (их 4), а за "кроликов" - количество домов на улице (их 29 так как дом, в котором живут пять человек учитывать не будем, потому что такой дом всего один). Применяя обобщенный принцип Дирихле, получим, что в одной из "клеток" будет не менее 8 "кроликов", а это и значит, что найдётся 8 домов, в которых живёт одинаковое количество человек.

Задача 7. Всего без наложений квадрат 5×5 можно покрыть 25 квадратиками 1×1. Возьмём за "клетки" квадратики 1×1 (их 25), а за "кроликов" - выстрелы (их 24). Применяя формулу раскраски получим, что по крайней мере одна из "клеток" будет свободна. А это и значит, что найдётся квадратик 1×1, в котором нет дырки от пули.

Задача 8. Предположим, что "клетками" будут все различные значения всех трех чисел, каждое из которых принимает значение 0, 1 или -1. Этих значений будет 7: -3, -2, -1, 0, 1, 2, 3. А "кроликами" будут наборы из трёх чисел, расположенные в одном столбце, или в одной строке, или по одной из двух диагоналей таблицы. Рассаживаем кроликов в клетки, где значение суммы равно сумме чисел этого "кролика"-набора. Тогда согласно принципу Дирихле, найдётся "клетка", где сидят не менее двух кроликов. А это значит, что найдутся две рассматриваемые тройки чисел, для которых суммы равны. Итак, все суммы различными быть не могут.

Задача 9. За "клетки" примем чётность чисел, их две (чётные числа и нечётный). За "кроликов" - числа. Используя принцип Дирихле получим, что в какой-то из двух "клеток" будет по одинаковому числу "кроликов". Это означает, что найдутся два числа одинаковой чётности. А если имеется два числа одинаковой чётности, то сумма этих чисел будет чётной.

Задача 10. Чтобы не было свободной пары клеток, в любой строке должно быть не менее пяти закрашенных клеток. Значит всего должно быть не менее закрашенных 50 клеток, чтобы было невозможно выделить свободный участок 1×2. Поскольку закрашенных клеток менее 50, в силу предложения 1 такой участок существует.

Задача 11. Предположим, что такой туннель прорыть нельзя. Тогда напротив каждого участка суши должен находится участок воды, значит суша должна занимать не более половины планеты. А по условию на планете Зям-лям суша занимает более половины поверхности планеты. Получили противоречие с условием задачи, значит наше предположение неверно, и прямой туннель, который соединяет сушу с сушей прорыть можно.

Задача 12. Примем за "клетки" сорта яблок, а за "кроликов" ящики с яблоками. Применяя обобщённый принцип Дирихле получим, что в одной из "клеток" будет не менее 9 "кроликов". А это и означает, что найдутся 9 ящиков с яблоками одного сорта.

Задача 13. Так как трое учителей вместе составили 6 задач, то оставшиеся 29 задач составили 7 учителей. Приняв задачи за «зайцев», а учителей – за «клетки», имеем 29= 4х7+1. Тогда, по обобщенному принципу Дирихле, найдется как минимум один учитель, который составил не менее пяти задач.

Задача 14. Разобьём ковёр на 16 маленьких ковриков размером 1×1. Так как дырок всего 15, хотя бы один квадратик окажется без дырок. Его и можно вырезать.

Задача 15. Всего в году 365 или 366 дней, а пассажиров в самолёте 380 – значит, их дни рождения не могут приходиться только на различные даты. Вообще, если пассажиров больше, чем 366, то хотя бы у двоих дни рождения совпадают. А вот если пассажиров 366, не исключено, что все они родились в разные дни года, но это маловероятно. (Согласно теории вероятностей, в случайно выбранной группе численностью свыше 22 человек совпадение дней рождения у некоторых из них более вероятно, нежели то, что у всех дни рождения приходятся на разные дни года).

Задача 16. Если шахматный ход не рокировка (обмен местами), то передвигается одна фигура, в случае рокировки – две. Чёрные успели сделать 14 ходов (так как первыми ходят белые), и по правилам игры лишь один из них мог быть рокировкой. Поэтому самое большое количество чёрных фигур, сделавших ходы, - 15. Всего же чёрных фигур 16. Значит, по крайней мере, какая-то из них не сделала ни одного хода.

Задача 17.

Рассмотрим 5 чисел:

 а1,                                                

   а1+а2,                                                      

      а1+а2+а3,                                                   

           а1 +а2+а3+а4,                                                      

                а1 +а2+а3+а4+а5.                          

Если одно из них делится на 5, то всё в порядке, утверждение справедливо. В противном случае при делении на 5 они дают в остатке какие-то из четырёх чисел: 1,2,3,4. По принципу Дирихле остатки, по крайней мере, двух из выписанных 5 чисел совпадают. Разность их делится на 5. Но эта разность – одно из чисел, данных в задаче, или сумма нескольких из них, стоящих рядом.

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

Краткое описание документа:

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