Комбинаторика Скачать
презентацию
<<  Число вариантов Граф  >>
Принцип Дирихле
Принцип Дирихле
Биография
Биография
Биография
Биография
Формулировка
Формулировка
Формулировка
Формулировка
Область применения
Область применения
Задачи
Задачи
Доказательство
Доказательство
Доказательство
Доказательство
5 точек
5 точек
5 точек
5 точек
Средние линии треугольника
Средние линии треугольника
Средние линии треугольника
Средние линии треугольника
11 различных целых чисел
11 различных целых чисел
Два числа
Два числа
100 целых чисел
100 целых чисел
Рассмотрим 100 следующих сумм
Рассмотрим 100 следующих сумм
Принцип Дирихле для длин и площадей
Принцип Дирихле для длин и площадей
Попарно не пересекающиеся отрезки
Попарно не пересекающиеся отрезки
Сдвинем данный отрезок
Сдвинем данный отрезок
Сдвинем данный отрезок
Сдвинем данный отрезок
Сдвинем данный отрезок
Сдвинем данный отрезок
Назовем крестом фигуру
Назовем крестом фигуру
Назовем крестом фигуру
Назовем крестом фигуру
Рассмотрим круг радиусом 1/2
Рассмотрим круг радиусом 1/2
Рассмотрим круг радиусом 1/2
Рассмотрим круг радиусом 1/2
Внутри выпуклого 2n-угольника взята точка P
Внутри выпуклого 2n-угольника взята точка P
Два случая
Два случая
Два случая
Два случая
Спасибо за внимание
Спасибо за внимание
Картинки из презентации «Принцип Дирихле» к уроку алгебры на тему «Комбинаторика»

Автор: A.S. Koshkin. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «Принцип Дирихле.ppt» со всеми картинками в zip-архиве размером 672 КБ.

Скачать презентацию

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

содержание презентации «Принцип Дирихле.ppt»
Сл Текст Сл Текст
1Принцип Дирихле. 12равные остатки (т. к. «кроликов» у нас 100, а «клеток»может быть
2Биография. Дирихле родился в городе Дюрен в семье лишь 99). Пусть это SZ и SF (Z < F). Тогда разность SF-SZ=
почтмейстера. В 12 лет Дирихле начал учиться в гимназии в Бонне, (x1 +. . .+ xF) - (x1 +. . .+ xZ) = xZ + 1+. . .+ xF делится на
спустя два года в иезуитской гимназии в Кёльне, где в числе 100, и поэтому сумма x Z+ 1+. . .+ xF является искомой.
прочих преподавателей его учил Георг Ом. В 1855 г. Дирихле 13Принцип Дирихле для длин и площадей. "Если внутри
становится профессором высшей математики в Гёттингенском множества меры V расположено несколько множеств, сумма мер
университете. которых больше V, то найдётся общий элемент, принадлежащий по
3Формулировка. Традиционная формулировка звучит так: «Если в крайней мере двум из этих множеств". Для длин и площадей
n клетках сидит n+1 или больше зайцев, то найдётся клетка, в это положение формулируется так: "Если на отрезке длины L
которой сидят по крайней мере два зайца» Но существуют еще две расположено несколько отрезков с суммой длин больше L, то хотя
формулировки: "При любом отображении множества P, бы два из них имеют общую точку"; "Если внутри фигуры
содержащего n+1 элементов, в множество Q, содержащее n площади S находится несколько фигур, имеющих сумму площадей
элементов, найдутся два элемента множества P, имеющие один и тот больше S, то хотя бы две из них имеют общую точку".
же образ» "Если nk+1 зайцев размещены в n клетках, то 14Задачи решаемые с помощью принципа Дирихле. На отрезке
найдутся k+1 зайцев, которые посажены в одну клетку (n, k - длиной 1 расположены попарно не пересекающиеся отрезки, сумма
натуральные числа)". длин которых равна p. Обозначим эту систему отрезков A. Пусть B
4Область применения. Один математик сказал, что Дирихле по — дополнительная система отрезков (отрезки систем A и B не имеют
частоте упоминаний ученикам навсегда обеспечено одно из самых общих внутренних точек и полностью покрывают данный отрезок).
высших мест. И добавил: "Пожалуй, есть способ лишить его Докажите, что существует параллельный перенос T, для которого
лидерства — назвать чьим-нибудь именем принцип «никакое чётное пересечение B и T(A) состоит из отрезков, сумма длин которых не
число не равно никакому нечётному». Несмотря на очевидность меньше p(1 - p)/2. .
этого принципа и, казалось бы простоту, с его помощью в решении 15Доказательство. Пусть с от -1 до 1. Сдвинем данный отрезок
,многие сложные задачи сводятся к простому и эффективному на c вдоль себя, а затем сдвинем его на c в ортогональном
решению. Принцип Дирихле даёт только неконструктивное направлении. Заштрихованная на рис. область соответствует
доказательство - мы не можем сказать, в какой именно клетке пересечению отрезков Ai и Bj. Ее площадь равна произведению длин
сидят два зайца, а знаем только, что такая клетка есть. Зачастую этих отрезков. Если рассмотреть все пары отрезков систем A и B,
вся сложность применения принципа Дирихле состоит в том чтобы то заштрихованная область будет иметь площадь p(1 - p). Поэтому
определить , что считать «зайцем», что – «клеткой». некоторое горизонтальное сечение заштрихованных областей имеет
5Задачи решаемые с помощью принципа Дирихле. На шахматной длину не меньше p(1 - p)/2. Замечание. Если вместо отрезка
доске стоят 44 ферзя. Докажите, что каждый из них бьёт рассматривать окружность (и вместо параллельного переноса
какого-нибудь другого ферзя. поворот), то p(1 - p)/2 можно заменить на p(1 - p). .
6Доказательство. При любом положении на доске ферзь бьёт не 16Задачи решаемые с помощью принципа Дирихле. Назовем крестом
менее 21 поля. Пусть какой-то из этих 44 ферзей не бьёт никакого фигуру, образованную диагоналями квадрата со стороной 1 (рис.).
другого ферзя. Тогда все клетки, которые находятся под боем Докажите, что в круге радиуса 100 можно разместить лишь конечное
этого ферзя, пусты. А так как при любом положении на шахматной число непересекающихся крестов.
доске ферзь бьёт не менее 21 поля, то занято ферзями не более 64 17Доказательство. Для каждого креста рассмотрим круг радиусом
– 21 = 43 полей. 1/2 с центром в центре креста. Докажем, что если пересекаются
7Задачи решаемые с помощью принципа Дирихле. Внутри два таких круга, то пересекаются и сами кресты. Расстояние между
равностороннего треугольника со стороной 1 расположено 5 точек. центрами пересекающихся равных кругов не превосходит их
Доказать, что расстояние между некоторыми двумя из них меньше удвоенного радиуса, поэтому расстояние между центрами
0,5. соответствующих им крестов не превосходит 1/. Рассмотрим
8Доказательство. Проведем средние линии треугольника. Они прямоугольник. заданный перекладинами первого креста и центром
разобьют его на четыре правильных треугольника со стороной 0,5. второго (рис.). Одна из перекладин второго креста проходит через
По принципу Дирихле из пяти точек хотя бы две окажутся в одном этот прямоугольник, поэтому она пересекает первый крест, так как
из четырёх треугольников. Используем лемму о том, что длина длина перекладины равна 1/, а длина диагонали прямоугольника не
отрезка, расположенного внутри треугольника, меньше длины его превосходит 1/. В круге конечного радиуса можно разместить лишь
наибольшей стороны. Расстояние между этими точками меньше 0.5 конечное число непересекающихся кругов радиуса 1/2.
так как точки не лежат в вершинах треугольников. 18Задачи решаемые с помощью принципа Дирихле. Внутри выпуклого
9Задачи решаемые с помощью принципа Дирихле. Дано 11 2n-угольника взята точка P. Через каждую вершину и точку P
различных целых чисел. Доказать, что из них можно выбрать два проведена прямая. Докажите, что найдется сторона 2n-угольника, с
числа, разность которых делится на 10. которой ни одна из проведенных прямых не имеет общих внутренних
10Решение. При помощи принципа Дирихле определим что по точек. .
крайней мере два числа из доступных 11 имеют одинаковый остаток 19Доказательство. Возможны два случая: 1. Точка P лежит на
при делении их на 10. Пусть это будут числа Z = 10z + r и F = некоторой диагонали AB. Тогда прямые PA и PB совпадают и не
10f + r. (Буквой r означим остаток при делении этих чисел). пересекают сторон. Остаются 2n - 2 прямые; они пересекают не
Тогда их разность делится на 10: Z - F = 10(z - f). более 2n - 2 сторон. 2. Точка P не лежит на диагонали
11Задачи решаемые с помощью принципа Дирихле. Доказать, что многоугольника A1A2...A2n. Проведем диагональ A1An + 1. По обе
если имеется 100 целых чисел x1, x2, . . . , x100, то из них стороны от нее лежит по n сторон. Пусть для определенности точка
можно выбрать несколько чисел, сумма которых делится на 100. P лежит внутри многоугольника A1...An + 1 (рис.). Тогда прямые
12Доказательство. Рассмотрим 100 следующих сумм: 1)S1= x1 2)S2 PAn + 1, PAn + 2,..., PA2n, PA1 (число этих прямых равно n + 1)
= x1 + x2 И т.д. вплоть до: 100)S100=x1+x2+ x3+. . .+ x100. Если не могут пересекать стороны An + 1An + 2, An + 2An + 3,...,
хотя бы одна из этих сумм делится на 100 то задача решена. A2nA1. Поэтому оставшиеся прямые могут пересекать не более чем n
Допустим, что ни одно из чисел S1, S2, . . . , S100 не делится - 1 из этих n сторон. .
на 100. По принципу Дирихле, два из них при делении на 100 дают 20Спасибо за внимание!
«Принцип Дирихле» | Принцип Дирихле.ppt
http://900igr.net/kartinki/algebra/Printsip-Dirikhle/Printsip-Dirikhle.html
cсылка на страницу

Комбинаторика

другие презентации о комбинаторике

«Остовное дерево» - Минимальное остовное ориентированное дерево. Связный граф. Последовательность. Доказательство. Как улучшить шаг. Основная идея. Оптимальное решение. Алгоритм Прима находит решение. Алгоритм Эдмондса находит оптимальное решение. Корневое ориентированное дерево. Ориентированный лес и циклы. Эквивалентные задачи.

«Решение комбинаторных зада» - Сколькими способами можно посадить шестерых школьников. Крестики и нолики. Разные значки. Перестановка с повторениями. Вершины правильного 10-угольника. Общее количество вариантов. Правило суммы. Коля сидит на краю. Четырехзначные числа. Подсчет вариантов с помощью графов. Вова умеет решать все 5 задач.

«Формулы для перестановок, сочетаний, размещений» - Формулы для подсчёта количества перестановок. Количество сочетаний. Сочетания. Количество размещений. Размещения. Подарок. Количество перестановок. Лесник. Очередь. Слово «факториал». Перестановки.

«Применение теории графов» - Панама. Проверочный практикум. Возможность. Приём развития картографической памяти. Выполнение заданий. Теория «графов». Психический процесс. Человеческая память. Задания к «графам». Несколько слов о памяти. Политическая карта. Столицы. Математическая модель. Страны.

«Принцип Дирихле» - Область применения. Принцип Дирихле для длин и площадей. Биография. Средние линии треугольника. Попарно не пересекающиеся отрезки. Задачи. 11 различных целых чисел. Формулировка. Принцип Дирихле. Доказательство.

«Понятие комбинаторики» - Граф. Размещение без повторения. Правило размещения. Дерево возможных вариантов. Комбинаторная задача. Сигналы. Цифры. Варианты решения задачи. Правило произведения. Область математики. Решение элементарных задач. Решение. Комбинаторика. Сочетание с повторением. Тонкости. Капля в море. Правило перестановки.

Урок

Алгебра

34 темы
Картинки
Презентация: Принцип Дирихле | Тема: Комбинаторика | Урок: Алгебра | Вид: Картинки