Презентация, доклад на тему Олимпиадная подготовка Принцип Дирихле

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

клеток, то хотя бы в одной из клеток находится более одного кролика.
Общий вид:
Если m элементов входят в n множеств, то хотя бы в одном множестве находится не менее элементов, а также хотя бы в множестве находится не более кроликов.

бы одна клетка содержит не больше голубя (т.е ноль)

9 клеток содержат 10 голубей, по принципу Дирихле хотя бы в одной клетке находятся более одного голубя

то либо в каждом множестве ровно один элемент, либо есть и пустое множество, и множество, в котором не менее 2 элементов.
2) Если в n множеств входят не менее n*(k-1)+1 элементов, то в каком-то из множеств не менее k элементов.
3) Если в n множеств входят не более n*(k+1)-1 элементов, то в каком-то их множеств не более k элементов.
4) Если сумма n чисел равна S, то среди них есть число, не меньшее , и число, не большее .

разбиением множества целых чисел на классы в зависимости от остатков от деления на натуральное число n. Рассмотрим типичные примеры.
Докажем, что среди 13 разных целых чисел всегда найдутся 2 числа, разность которых делится на 12.

, , а=12q+r, b=12p+r, где .

a-b=(12q+r)-(12p+r)=12(p-r) (a-b) 12.

наугад вынуть из коробки, чтобы среди них заведомо нашлись два одного цвета?

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

из них не более 400 000 иголок. Докажите, что в лесу найдутся по крайней мере три ёлки с одинаковым числом иголок.

19n, m > n

19m - 19n = 19n(19m-n - 1) 1000.

19n не имеет общих делителей с 1000 19m-n – 1 1000. Число 19m-n - 1 заканчивается тремя нулями, значит число 19m-n (какая-то степень 19) заканчивается на 001.

число, делящееся на 1999.

Пусть в первом (большем) числе будет а единиц, а во втором – b. Вычтем из большего числа – A(a) меньшее – A(b).

11…11...11 1...11 11...10...00

Полученное число будет иметь вид A(a-b)*

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

Разобьём жителей на классы. У нас есть 2 варианта разбиения – либо к каждому классу относятся 20 элементов, либо в каких-то классах элементов будет меньше 20, а в других – больше 20.

не найдётся двух с равным числом волос на голове.
б) Ни у одного жителя N на голове не растёт ровно 518 волос.
в) Жителей в N больше, чем волос на голове любого из них.
Какова наибольшая численность населения г. N?

Согласно второму условию n-1 не может быть равно 518 . Максимально возможное n – 518.

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

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

размещено 15 точек. Докажите, что внутри этого квадрата есть квадрат размером 1×1, не содержащий внутри себя ни одной точки.

получим 16 квадратов внутри большого. Так как точек дано всего 15, то, по принципу Дирихле, в каком-то из квадратов не будет точки, что и требовалось доказать.

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

треугольник с вершинами в отмеченных точках.
Решение. Разобьём вершины 20-угольника на 4 группы так, чтобы входившие в каждую группу вершины образовывали правильный пятиугольник. По принципу Дирихле в какой-то из них окажется не менее 3 отмеченных вершин. Не менее двух из них будут смежными, а, следовательно, и вершинами равнобедренного треугольника.