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

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

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

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

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

5 Задачи и примеры решений Задача 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 все стороны синие.

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

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

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

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

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

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

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

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

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

15