Презентация на тему "принцип дирихле". Принцип Дирихле. Задачи и решения Рассмотрим примеры различных задач, решаемых с помощью принципа Дирихле

Гипотеза: применение соответствующих формулировок принципа Дирихле – наиболее рациональный подход при решении задач. Наиболее применяема формулировка: "Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х "кроликов " Гипотеза: применение соответствующих формулировок принципа Дирихле – наиболее рациональный подход при решении задач. Наиболее применяема формулировка: "Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х "кроликов " Цель: изучить, один из основных методов математики, принцип Дирихле

Этот принцип утверждает, что, если множество из N элементов разбито на п непересекающихся частей, не имеющих общих элементов, где N>n то, по крайней мере, в одной части будет более одного элемента Наиболее часто принцип Дирихле формулируется в одной из следующих форм: Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х "кроликов"

У1. "Если в n клетках сидят не более n-1 "кроликов", то есть пустая клетка" У1. "Если в n клетках сидят не более n-1 "кроликов", то есть пустая клетка" У2. "Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х "кроликов" " У3. "Если в n клетках сидят не более nk-1 "кроликов", то в какой-то из клеток сидят не более k-1 "кроликов " У4. "Если в n клетках сидят не менее n k+1 "кроликов", то в какой-то из клеток сидят не менее k+1 "кроликов""

У5. "Непрерывный принцип Дирихле. "Если среднее арифметическое нескольких чисел больше a, то, хотя бы одно из этих чисел больше a"; У6. "Если сумма n чисел меньше S, то по крайней мере одно из этих чисел меньше S/n". У7. "Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток".

Задача. В хвойном лесу растут 800000 елей. На каждой ели - не более 500000 иголок. Доказать, что существуют хотя бы две ели с одинаковым числом иголок. Научная классификация Царство: Растения Отдел: Голосеменные Класс: Хвойные Семейство: Сосновые Вид: Ели

Геометрическая задача Внутри равнобедренной трапеции со стороной 2 расположено 4 точки. Доказать, что расстояние между некоторыми двумя из них меньше 1. Решение. Разобьем трапецию со стороной 2 на три треугольника со стороной 1. Назовем их "клетками", а точки – "кроликами". По принципу Дирихле из четырех точек хотя бы две окажутся в одном из трех треугольников. Расстояние между этими точками меньше 1, поскольку точки не лежат в вершинах треугольников

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

Задача Дано n+1 различных натуральных чисел. Доказать, что из них можно выбрать два числа А и В, разность которых делится на n Задача Докажите, что среди n+1 различных натуральных чисел найдутся хотя бы два числа А и В такие что, число А2 - В2 делится на n. Докажем, что (А – B)(A+B) кратно n Задача Докажите, что среди n+1 различных натуральных чисел найдутся хотя бы два числа А и В такие что, число А3 – В3 делится на n. Докажем, что (А – B)(A2+AB +B2) кратно n

Малая теорема Ферма Если p - простое число, a - целое число, не делящееся на p, то a p-1 при делении на p даёт остаток 1 Доказательство Каждое из p - 1 чисел a, 2a, . . ., (p-1) a ("кроликов") даёт при делении на p ненулевой остаток (ведь a не делится на p)

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

Дирихле родился в вестфальском городе Дюрене в семье почтмейстера. В 12 лет Дирихле начал учиться в гимназии в Бонне, спустя два года в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом. С 1822 по 1827 г. жил в качестве домашнего учителя в Париже, где вращался в кругу Фурье. Биография

В 1827г. устраивается на должность приватдоцента университета Бреслау (Вроцлав). - В 1829 г. он перебирается в Берлин, где проработал непрерывно 26 лет, сначала как доцент. - Затем с 1831 г. как экстраординарный профессор. - С 1839 г. как ординарный профессор Берлинского университета. В 1855 г. Дирихле становится в качестве преемника Гаусса профессором высшей математики в Гёттингенском университете. Биография

Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят, по крайней мере, два зайца. n, то хотя бы в одной клетке сидят, по крайней мере, два зайца."> n, то хотя бы в одной клетке сидят, по крайней мере, два зайца."> n, то хотя бы в одной клетке сидят, по крайней мере, два зайца." title="Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят, по крайней мере, два зайца."> title="Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят, по крайней мере, два зайца.">

Если в n клетках сидит m голубей, причем m

N, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев." title="Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев." class="link_thumb"> 9 Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев. n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев."> n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев."> n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев." title="Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев."> title="Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев.">

12, то, по принципу Дирихле, найдется, как миним" title="В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц. Решение: Пусть 15 учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как миним" class="link_thumb"> 10 В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц. Решение: Пусть 15 учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как минимум, одна «клетка», в которой будет сидеть, по крайней мере, 2 «зайца». Ответ: Найдется месяц, в котором будут отмечать дни рождения не менее 2 учеников класса. Задача 1. 12, то, по принципу Дирихле, найдется, как миним"> 12, то, по принципу Дирихле, найдется, как минимум, одна «клетка», в которой будет сидеть, по крайней мере, 2 «зайца». Ответ: Найдется месяц, в котором будут отмечать дни рождения не менее 2 учеников класса. Задача 1."> 12, то, по принципу Дирихле, найдется, как миним" title="В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц. Решение: Пусть 15 учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как миним"> title="В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц. Решение: Пусть 15 учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как миним">

В ковре размером 3х3 метра Коля проделал 8 дырок. Докажите, что из него можно вырезать коврик размером 1х1 метр, не содержащий внутри себя дырок. Решение: Разрежем ковер на 9 ковриков размерами 1х1 метр, Так как ковриков - «клеток» - 9, а дырок - «голубей» - 8. Ответ: Найдется коврик без дырок внутри. Задача 2.

В 3А классе учится 27 школьников, знающих всего 109 стихотворений. Докажите, что найдется школьник, знающий не менее 5 стихотворений. Решение: Предположим, что каждый школьник знает не более 4 стихотворений. Значит, 27 школьников знают не более 427=108(стихотворений) Ответ: Значит найдется школьник, знающий не менее 5 стихотворений. Задача 3.

В городе 15 школ. В них обучается 6015 школьников. В концертном зале городского Дворца культуры 400 мест. Доказать, что найдётся школа, ученики которой не поместятся в этот зал. Решение: Предположим, что в каждой школе не более 400 учеников. Значит во всех школах = 6000(школьников). Ответ: Поэтому ученики этой школы не поместятся в зал на 400 мест. Задача 4.

В школе 5 восьмых классов: 8А, …, 8Д. В каждом из них учится по 32 человека. Докажите, что найдутся 14 человек, родившихся в один месяц. Решение: Предположим, что в каждом месяце родилось не более 13 учеников. Значит за 12 месяцев родилось 1213=156(школьников). Но по условию в школе обучается 532=160(человек). Ответ: Значит, найдется месяц, в котором родилось больше, чем 13 учеников, то есть хотя бы 14. Задача 5.

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

4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек." title="2 1 4 3 Треугольники – «клетки», 5 точек – 5 «зайцев». 5>4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек." class="link_thumb"> 16 Треугольники – «клетки», 5 точек – 5 «зайцев». 5>4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек. 4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек."> 4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек."> 4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек." title="2 1 4 3 Треугольники – «клетки», 5 точек – 5 «зайцев». 5>4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек."> title="2 1 4 3 Треугольники – «клетки», 5 точек – 5 «зайцев». 5>4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек."> Выводы: Таким образом, применяя данный метод, надо: Определить, что удобно в задаче принять за «клетки», а что за «зайцев». Получить «клетки»; чаще всего «клеток» меньше (больше), чем «зайцев» на одну (или более). Выбрать для решения требуемую формулировку принципа Дирихле. Принцип Дирихле важен, интересен, полезен. Его можно применять в повседневной жизни, что развивает логическое мышление. Многие олимпиадные задачи решаются, используя это специальный метод. Он дает возможность обобщать.

Принцип Дирихле. Задачи и решения

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

Обобщенная формулировка принципа: «Если множество, которое состоит из Nk+1 элементов разбить на k множеств, то хотя бы в одном подмножестве окажется не меньше N+1 элементов» или «Если множество, которое состоит из m элементов, разбить на k подмножеств, то хотя бы в одном подмножестве окажется не менее m/k элементов»

Принцип Дирихле имеет геометрическую формулировку: А) если отрезок длиной l разбить на n отрезков (которые не имеют общих внутренних точек), то длина наибольшего отрезка не менее l/n, а длина наименьшего отрезка не больше l/n Б) если фигуру площадью S разбить на n частей (которые не имеют общих внутренних точек), то площадь наибольшей фигуры не менее чес S/n, а площадь наименьшей не более чем S/n

Задачи и примеры решений Задача 1. На плоскости дано шесть точек общего положения (никакие три из них не лежат на одной прямой). Любые две точки соединены отрезком, каждый отрезок покрашено либо в красный, либо в синий цвет. Доказать, что найдется треугольник с вершинами в данных точках, все стороны которого имеют один цвет. Решение. Обозначим данные точки А1, А2, А3, А4, А5, А6. Из точки А1 выходит 5 отрезков двух цветов. По принципу Дирихле среди этих отрезков есть 3 отрезка одного цвета. Пускай для конкретности это отрезки А1 А2, А1 А3 , А1 А4 красного цвета. Рассмотрим отрезки А2 А3, А3 А4, А2 А4. Возможные случаи: А) среди этих отрезков есть красный, например А2 А3. Тогда в треугольнике А1 А2 А3 все стороны красные; Б) среди этих отрезков нет красных. Тогда в треугольнике А2, А3, А4 все стороны синие.

Задача 2. В квадрате, сторона которого равна 6 см, размещена 1991 точка. Доказать, что квадратом, сторона которого равна 5 см, можно покрыть хотя бы 664 из этих точек. Решение. Нетрудно заметить, что 664 составляет приблизительно треть от 1991, а именно 1991 = 3*663+2. Поэтому при любом разбитии множества, состоящего из 1991 точки, на три подмножества, хотя бы в одно из этих подмножеств попадет 664 или более точек. Значит, для решения задачи достаточно показать, что квадрат со стороной 6 см можно разбить на три части, каждую из которых можно покрыть квадратом со стороной 5 см. Это видно по рисунку, в котором AK=5см, BO=3v2cм

Решение. Допустим, что в некотором выпуклом 2n-угольнике каждая диагональ параллельна некоторой стороне. Идея получения противоречия такова: выберем наибольшую группу взаимно параллельных диагоналей и покажем, что такое количество диагоналей нельзя разместить внутри выпуклого 2n-угольника. Значит, разобьем все диагонали на группы взаимно параллельных диагоналей. Таких групп не более чем 2n (некоторые стороны могут быть параллельны между собой). Количество всех диагоналей равно = 2n*(n – 1,5), поэтому в некоторой группе есть не менее чем (n - 1) диагоналей. Эти (n - 1) диагонали параллельны некоторой стороне А1 А2 и лежат относительно нее в одной полуплоскости. Но тогда на эту сторону и на эти (n - 1) диагоналей приходиться 2n вершин, т.е. та из диагоналей, которая лежит как можно дальше от стороны А1 А2 , должна быть стороной 2n-угольника. Противоречие. значит, предположение неверное, поэтому найдется диагональ, которая не параллельна ни одной из сторон. Задача 3. Доказать, что в произвольном выпуклом 2n-угольнике найдется диагональ, которая не параллельна ни одной из сторон.

Решение. Разобьем квадрат на 50 прямоугольников со сторонами 1 см и 2 см. тогда хотя бы в один из этих прямоугольников не попадет менее чем 3 точки. Эти три точки образуют треугольник, площадь которого не превышает половины площади прямоугольника, в котором этот треугольник находится. Задача 4. Внутрь квадрата со стороной 10 см «брошено» 101 точку (ни какие три не лежат на одной прямой). Доказать, что среди этих точек есть три, которые образуют треугольник, площадь которого не превышает 1 см2.

Задачи для самостоятельного решения. Задача 1. Доказать, что из произвольных 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100. Задача 2. Доказать, что существует натуральное число, последние четыре цифры которого 1972 и которое делится на 1971. Задача 3. Можно ли найти такой натуральный показатель степени числа 3, который заканчивается на 0001?

Задача 4. В ящике лежат носки: 10 черных, 10 синих, 10 белых. Какое наименьшее количество носков нужно вытянуть, не смотря, чтоб среди вытянутых оказалось два носка: а) одного цвета; б) разных цветов; в) черного цвета? Задача 5.В классе 25 учеников. Известно, что среди любых трех из них есть двое друзей. Доказать, что есть ученик, у которого не менее чем 12 друзей. Задача 6. Комиссия из 60 человек провела 40 заседаний, причем на каждом присутствовали ровно 10 членов комиссии. Доказать, что какие-то 2 члена комиссии встретились на заседаниях хотя бы дважды.

Задача 7. Внутри правильного шестиугольника со стороной 3 см произвольным образом размещено 55 точек, никакие три из которых не лежат на одной прямой. Доказать, что среди них найдутся три точки, образующие треугольник, площадь которого не превышает v3/4см2. Задача 8. Дано n+1 разное натуральное число, каждое из которых меньше чем 2n. Доказать, что из них можно выбрать 3 таких числа, одно из которых равняется сумме двух других. Задача 9. Доказать, что из 52 целых чисел всегда найдутся два, разность квадратов которых делится на 100.

Задача 10. 11 учеников занимаются в 5 кружках дома культуры. Доказать, что найдется два ученика A и B такие, что все кружки, которые посещает А, посещает и В. Задача 11. Доказать, что среди любых 10 целых чисел найдется несколько (возможно одно), сумма которых делится на 10. Задача 12. На плоскости дано 17 точек, никакие три из которых не лежат на одной прямой. Любые две точки соединены отрезком. Каждый отрезок покрашено либо в красный, либо в синий, либо в зеленый цвет. Доказать, что найдется треугольник с вершинами в данных точках, все стороны которого имеют одинаковый цвет.

Задача 13. Каждая точка плоскости покрашена в белый или черный цвет. Доказать, что на этой плоскости найдется треугольник с углами 300, 600, 900 и гипотенузой 2, вершины которого одноцветные Задача 14. В квадрате, сторона которого равна 1, взято 51 точку. Доказать, что некоторые три из этих точек обязательно находятся внутри круга радиуса 1/7. Задача 15. На плоскости дано 25 точек, причем среди произвольных трех найдутся две на расстоянии меньше 1. Доказать, что существует круг радиуса 1, который вмещает не менее чем 13 данных точек.

Задача 16. На отрезке длиной 1 закрашено несколько отрезков так, что расстояние между произвольными двумя закрашенными точками не равно 0,1. Доказать, что сумма длин всех закрашенных отрезков не превышает 0,5. Задача 18. Дано бесконечная бумага в клето чку и фигура, площадь которой меньше площади клето чки. Доказать, что эту фигуру можно положить на бумагу так, чтобы она не накрыла ни одной вершины клето чек. Задача 17. Дано числа 21 – 1,22 – 1,23 – 1,…,2n-1, где n3 – непарное число. Доказать, что хотя бы одно из данных чисел делится на n.

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

Дирихле Петер Август Лежён (1805-1859) -
немецкий математик, иностранный членкорреспондент Петербургской Академии наук
(1837), член многих других академий.
Дирихле родился в вестфальском городе Дюрене в семье почтмейстера.
В 12 лет Дирихле начал учиться в гимназии в Бонне, спустя два года в
иезуитской гимназии в Кёльне, где в числе прочих преподавателей его
учил Георг Ом. С 1822 по 1827 г. жил в качестве домашнего учителя в
Париже, где вращался в кругу Фурье.В 1827г. устраивается на
должность приватдоцента университета Бреслау. В 1829 г. он
перебирается в Берлин, где проработал непрерывно 26 лет, сначала
как доцент. Затем с 1831 г. как экстраординарный профессор. С 1839 г.
как ординарный профессор Берлинского университета. В 1855 г. Дирихле
становится в качестве преемника Гаусса профессором высшей
математики в Гёттингенском университете.

В комбинаторике при́нцип Дирихле́- утверждение, устанавливающее
связь между объектами («кроликами») и контейнерами («клетками»)
при выполнении определённых условий. В английском и некоторых
других языках утверждение известно как «принцип голубей и
ящиков», когда объектами являются голуби, а контейнерами -
ящики.
9 клеток содержат 7 голубей,
по принципу
Дирихле хотя бы
9-7=2 клетки свободны
9 клеток содержат 10 голубей,
по принципу Дирихле хотя бы
в одной клетке находятся
более одного голубя

Формулировки

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

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

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

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

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

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

В ковре размером 3x3 метра Коля проделал 8 дырок.
Докажите, что из него можно вырезать коврик размером
1x1 метр, не содержащий внутри себя дырок.
(Дырки можно считать точечными.)
РЕШЕНИЕ
Здесь дырки будут «зайцами».
Разрежем ковер на 9 ковриков
размерами 1x1 метр. Так как
ковриков-«клеток» - 9, а дырок«зайцев» - 8, то найдется хотя бы
одна «клетка», в которой не будет
«зайцев», то есть найдется коврик
без дырок внутри.

Таким образом, применяя данный метод, надо:
Определить, что удобно в задаче принять за «клетки», а
что за «зайцев».
Получить «клетки»; чаще всего «клеток» меньше
(больше), чем «зайцев» на одну (или более).
Выбрать для решения требуемую формулировку
принципа Дирихле.
Принцип Дирихле важен, интересен, полезен. Его
можно применять в повседневной жизни, что развивает
логическое мышление.
Многие олимпиадные задачи решаются, используя это
специальный метод. Он дает возможность обобщать.