Презентация к уроку: Принцип Дирихле


Чтобы посмотреть презентацию с оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов:

Содержание 1. Принцип Дирихле2. Задачи на принцип Дирихле3. Графы4. Задачи на графы5. Четность6. Задачи на четность7. Делимость и остатки8. Задачи на делимость9. Остатки10. Задачи на остатки11. Геометрические задачи Сформулируем принцип Дирихле: Пусть в n коробок помещены k предметов. Если количество предметов больше количества коробок (k > n), тогда существует хотя бы одна коробка, в которой бы находилось 2 предмета.Примечание. Отметим, что не важно, в какой именно коробке находятся по крайней мере два предмета. Также не имеет значение, сколько предметов в этой коробке, и сколько всего таких коробок. Важно то, что существует хотя бы одна коробка с не менее чем двумя предметами (два или более).Очевидно, слова «коробки» и «предметы» нужно понимать в обобщенном смысле ; вовсе не обязательно, чтобы они означали реальные коробки и предметы Принцип Дирихле Часто это предложение формулируют в шуточной форме: Если по n клеткам рассадить зайцев, число которых больше n, то найдется клетка, в которой находится больше одного зайца. Доказательство принципа чрезвычайно просто, в нем используется тривиальный подсчет кроликов в клетках. Если бы в каждой клетке сидело не более одного кролика, то всего в наших n клетках сидело бы не более n кроликов, что противоречило бы условиям. Таким образом, мы доказали принцип Дирихле методом «от противного». Справедлив также обобщенный принцип Дирихле:Если по n ящикам разложить предметы, число которых больше n*k( где k – натуральное число), то найдется ящик, в котором находится больше k предметов. Задача 1. В мешке лежат шарики двух цветов: черного и белого. Какое наименьшее число шарикрв нужно достать из мешка вслепую, чтобы среди них заведомо оказались два шарика одного цветаРешение.Задача 2. В хвойном лесу растут 800000 елей. На каждой ели - не более 500000 иголок. Доказать, что существуют хотя бы две ели с одинаковым числом иголокРешение.Задача 3. В международном симпозиуме участвуют 17 человек. Каждый знает не более трех языков и любые два участника могут общаться между собой. Доказать, что хотя бы три участника, знают один и тот же язык.Решение.Задача 4. Доказать, что среди шести целых чисел найдутся два числа, разность которых делится на 5.собственным знакомым).Решение. Задача 5. В зале находятся n человек (n ≥ 2). Доказать, что среди них найдутся два человека с одинаковым числом знакомых (предполагается, что если человек A является знакомым человека B, то и B является знакомым A; никто не считается своимРешение.Задача 6. Доказать, что для любого натурального числа n ≥ 1, существует натуральное число, состоящее из цифр 0 и 5, делящееся на n.Решение.Задача 7. В доме живут 40 учеников. Существует ли такой месяц в году, когда хотя бы 4 ученика празднуют свой день рождения.Решение.Задача 8. Доказать, что из n+1 различных натуральных чисел, меньших 2n, можно выбрать 3 числа так, чтобы одно число было равно сумме двух других.Решение. Задача 9. В 500 коробках лежат яблоки. Известно, что в каждой коробке находятся не более 240 яблок. Доказать, что существуют хотя бы 3 коробки, которые содержат одинаковое количество яблок.Решение.Задача 10. В коробке лежат 10 красных карандашей, 8 синих, 8 зеленых и 4 желтых. Наугад (произвольно) из коробки вынимают n карандашей. Определить наименьшее число карандашей, которые необходимо вынуть, чтобы среди них было:a)не менее 4 карандашей одного цвета;b)по одному карандашу каждого цвета;c)хотя бы 6 карандашей синего цвета.Решение.Задача 11. 15 белок собрали 100 орехов. Докажите, что какие-то две из них собрали одинаковое количество орехов. Решение. Задача 12. Точки на плоскости раскрашены двумя цветами. Показать, что существуют две точки одинакового цвета, расположенные на расстоянии 1м.Решение.Задача 13. На плоскости даны 25 точек таким образом, что две точки из любых трех расположены на расстоянии меньше 1. Доказать, что существует круг радиуса 1, содержащий не менее 13 из данных точек.Решение.Задача 14. Пусть a1,a2, ... ,an - перестановка чисел 1,2,3,...,n. Доказать, что произведение (a1 - 1)(a2 - 2)...(an - n) будет четным, если n – нечетно.Решение. Решение. Достаем из мешка 3 шарика. Если среди этих шариков было не более одного шарика каждого из цветов – это очевидно, и противоречит тому, что мы достали три шарика. С другой стороны, понятно что двух шариков может и не хватить. Ясно, что кроликами в этой задаче являются шарики, а клетками – цвета: черный и белый. Решение. Решим эту задачу, используя принцип Дирихле. Пусть имеются 500000 коробок, соответственно пронумерованных 1,2,3,...,500000. Помещаем (мысленно) в эти коробки 800000 елей следующим образом: в ящик с номером s помещаем ели, на которых ровно s иголок. Поскольку елей, то есть "предметов", больше, чем коробок, следует, что по крайней мере одна коробка будет содержать не менее двух предметов, то есть, не менее двух елей. Так как в одной и той же коробке находятся ели с одинаковым числом иголок, приходим к выводу, что существуют хотя бы две ели с одинаковым числом иголок. Решение. Пусть A - один из участников. Он может общаться с каждым из 16 участников на не более одном из трех известных ему языков. Тогда существует язык, на который Aговорит с не менее чем шестью участниками. Пусть B - любой из них. Ясно, что среди остальных 5 участников есть 3, с которыми B может общаться на одном языке (назовем его "второй язык"). Если среди этих троих участников хотя бы два, скажем C и D, могут говорить на "втором языке", то B, C и D и есть те три человека, говорящие на одном языке. Решение. Рассмотрим 5 коробок, пронумерованных 0,1,2,3,4, - цифрами, представляющими собой остатки от деления на 5. Распределим в эти коробки шесть произвольных целых чисел в соответсвии с остатком от деления на 5, то есть, в одну и ту же коробку помещаем числа, имеющие одинаковый остаток от деления на 5. Поскольку чисел ("предметов") больше, чем коробок, согласно принципу Дирихле, существует одна коробка, содержащая более одного предмета. То есть, существуют (по крайней мере) два числа, помещенные в одну и ту же коробку. Следовательно, существуют два числа с одинаковым остатком от деления на 5. Тогда, разность этих чисел делится на 5. Решение. Обозначим через m количество человек, которые имеют хотя бы одно знакомство в зале (это и будут "предметы"). Каждый из этих m человек может иметь 1,2,...,m-1 знакомых ("коробки" - число знакомых).Согласно принципу Дирихле, сущетсвуют два человека с одинаковым числом знакомых. Решение. Рассмотрим натуральные числаи распределим эти "предметы" в "коробки" пронумерованные 0,1,...,n-1 (цифрами, представляющими собой остатки от деления на n). В коробку s помещаем число ak, которое имеет остаток от деления на n, равный s.Если в коробке с номером 0 находится один "предмет" (то есть, одно число), тогда задача решена. В противном случае n "предметов" находятся в n-1 "коробках". Согласно приципу Дирихле, существуют два "предмета" (числа), находящиеся в одной и той же коробке. То есть, существуют два числа, имеющие одинаковый остаток от деления на n. Их разность будет делится на n, и как легко заметить, разность чисел, состоящих из цифр 0 и 5, также будет числом, состоящим из 0 и 5. Решение. Пусть "коробками" будут месяцы, а "предметами" - ученики. Распределяем, "предметы" по "коробкам" в зависимости от месяца рождения. Так как число месяцев, то есть, коробок, равно 12, а число учеников, то есть, предметов 40 = 12·3+4, согласно принципу Дирихле существует коробка (месяц) с по крайней мере 3+1=4 предметами (учениками). Решение. Пусть a1 < a2 < ... < an+1 - данные числа. Рассмотрим разностиa2 - a1,a3 - a1,...an+1 - a1.Эти числа различны, положительны и меньшие, чем 2n. Согласно принципу Дирихле, хотя бы два числа совпадают. Более того, одно из этих чисел принадлежит множеству {a2 -a1, ... ,an+1 - a1}. Пусть это будут числа ak и am - a1. Отсюда ak = am - a1, и, следовательно, am = ak + a1. Решение. Пусть в первых 240 коробках находится различное количество яблок (1,2,...,240) , в следующих 240 коробках - аналогично Таким образом, остались 500 - 2·240 = 20 коробок, в которые необходимо поместить яблоки от 1 до 240. Решение. a) Пусть вынули 13 карандашей. Так как у нас всего 4 цвета, согласно принципу Дирихле (карандаши будут "предметами", а цвета - "коробками"), по крайней мере 4 карандаша будут одинакового цвета.Докажем, что n = 13 является наименьшим числом. С этой целью покажем ситуацию, при которой условия задачи не выполняются. Например, когда вынуто по 3 карандаша каждого цвета (12 карандашей). Отметим, что эта ситуация возможна, так как в коробке находится не менее 3 карандашей каждого цвета. Случаи b) и с) решаются аналогично. Решение. Пусть все белки собрали разное число орехов : 1, 2, 3, …, 15. Так как сумма числа орехов (1+15):2*15=120 больше 100, то какие-то две белки собрали одинаковое число орехов. Решение. Рассмотрим равносторонний треугольник со стороной 1м. Вершины треугольника будут "предметами", а цвета - "коробками". Так как число "предметов" больше числа "коробок", следует, что существуют две вершины одного цвета. Поскольку треугольник равносторонний, расстояние между вершинами составляет 1м.Отметим, что эта задача может быть решена и другим методом - от противного. Пусть A - одна из точек плоскости, и предложим, что все точки плоскости, расположенные на растоянии 1м от A, окрашены в цвет, отличный от цвета точки A. Тогда получаем окружность радиуса 1 из точек одинакового цвета. Очевидно, что в этой окружности существует хорда длиной 1м. Следовательно, концами хорды будут точки одного цвета, расположенные на растоянии 1м. Решение. Пусть A - одна из данных точек. Если остальные точки находятся внутри круга S1 радиуса 1 с центром в точке A, тогда задача решена. Пусть B - одна из точек, лежащих вне круга S1. Рассмотрим круг S2 радиуса 1 с центром в точке B. Среди точек A, B, C, где C - произвольная из данных точек, существуют две, расстояние между которыми меньше 1. Более того, этими точками не могут быть A и B.Таким образом, круги S1 и S2 содержат все исходные точки. То есть, один из этих кругов содержит не менее 13 точек. Решение. Пусть n = 2k + 1. Во множестве рассмотренных чисел k + 1 чисел будут нечетными. В исходном произведении среди уменьшаемых и вычитаемых будут (k + 1) + (k + 1) = 2(k + 1) = n + 1 нечетных чисел. Поскольку произведение состоит из n сомножителей, один (по крайней мере) из них будет содержать только нечетные числа (и уменьшаемое и вычитаемое будут нечетными). Таким образом, этот множитель будет четным, и произведение также будет четным.

Приложенные файлы

  • ppt 12345678
    Размер файла: 459 kB Загрузок: 0

Добавить комментарий