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

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

Принципом Дирихле традиционно называют следующее утверждение:

если в 4 клетках сидит хотя бы 5 кроликов, то по крайней мере в одной клетке находится хотя бы 2 кролика.

В общем виде принцип Дирихле выглядит так:

Пусть есть хотя бы n·k+1 объект, которые распределены в n множествах. Тогда хотя бы в одном множестве находится хотя бы k+1 объект.

Доказательство. 

Докажем это утверждение методом от противного. Пусть в каждой клетке сидит не более k кроликов. Поскольку клеток n, то всего кроликов должно быть не более n·k, что противоречит условию.

Пример.

25 кроликов расположились в 12 клетках. Докажите, что хотя бы в 1 клетке хотя бы 3 кролика.

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

Следствие 1.

Если сумма n чисел равна S, то среди них есть число, не большее S/n и не меньшее S/n.

Следствие 2. (геометрический вариант принципа Дирихле)

Если на отрезке AB лежат несколько отрезков, сумма длин которых равна α·AB (α> 1), тогда какая-то точка принадлежит, по крайней мере, [α] + 1 отрезкам.

Задачи для самостоятельного решения:

  1. Шесть школьников съели 7 конфет. Докажите, что хотя бы один школьник съел хотя бы 2 конфеты.
  2. 13 школьников съели 30 конфет. Докажите, что хотя бы 1 школьник съел хотя бы 3 конфеты.
  3. В классе 15 учеников. Докажите, что найдутся хотя бы 2 ученика, родившихся в одном месяце.
  4. В классе 25 учеников. Докажите, что найдутся хотя бы 3 ученика, родившихся в одном месяце.
  5. Какое наименьшее число учеников должно быть в школе, имеющей 30 классов, для того, чтобы в ней обязательно был класс, в котором не меньше 28 учеников?
  6. В квадрате 8×8 закрашено 33 клетки. Докажите, что три какие-то закрашенные клетки образуют уголок из трех клеток.
  7. В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Докажите, что какие-то три ученика сделали одинаковое количество ошибок.
  8. Докажите, что среди любых шести целых чисел найдутся два, разность которых кратна 5.
  9. 100 человек сидят за круглым столом, причем более половины из них — мужчины. Докажите, что какие-то двое мужчин сидят друг напротив друга.
  10. Докажите, что на шахматной доске нельзя расставить более 8 ладей так, чтобы никакие две из них не били друг друга.
  11. Докажите, что в любой компании есть два человека, имеющих одинаковое число знакомых в этой компании.
  12. Имеется 101 пуговица одного из 11 цветов. Докажите, что либо среди этих пуговиц найдутся 11 пуговиц одного цвета, либо 11 пуговиц разных цветов. 
  13. Дано восемь различных натуральных чисел, не превосходящих 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.
  14. Докажите, что из любых пяти натуральных чисел можно выбрать три числа, сумма которых делится на 3.
  15. Докажите, что из любых семи натуральных чисел можно выбрать три числа, сумма которых делится на 3. 
  16. 15 белок собрали 100 орехов. Докажите, что какие-то две из них собрали одинаковое количество орехов.
  17. В бригаде 7 человек; их суммарный возраст — 332 года. Докажите, что из них можно выбрать троих человек, сумма возрастов которых не менее 142 лет.
  18. Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.
  19. Докажите, что никакая прямая не может пересекать все три стороны треугольника.
  20. Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?
  21. Внутри равностороннего треугольника со стороной 1 расположено 5 точек. Доказать, что расстояние между некоторыми двумя из них меньше 0,5.
  22. В прямоугольнике 5×6 закрашено 19 клеток. Докажите,что в нем можно выбрать квадрат 2×2 , в котором закрашено не менее трех клеток.
  23. Докажите, что из любых двенадцати натуральных чисел можно выбрать два, разность которых делится на 11.
  24. Можно ли в клетках квадратной таблицы 5×5 расставить числа 0, +1, –1 так, чтобы все суммы в каждом столбце, в каждой строке и на каждой из двух диагоналей были различны?
  25. В ряд выписано пять натуральных чисел: a1, a2, a3, a4, a5. Докажите, что либо одно из них делится на 5, либо сумма нескольких рядом стоящих чисел делится на 5.
  26. Несколько дуг окружности покрашены в красный цвет. Сумма длин окрашенных дуг меньше половины длины окружности. Докажите, что существует диаметр, оба конца которого не окрашены.
  27. В квадрате со стороной 1 отметили 51 точку. Докажите, что три из них можно покрыть кругом диаметра 1/7.
  28. В квадрате со стороной 1 расположено несколько окружностей с суммой их длин, равной 10. Докажите, что существует прямая, параллельная сторонам квадрата, которая пересекает не менее четырех окружностей.
  29. Докажите, что любой выпуклый многоугольник с четным числом сторон имеет диагональ, которая не параллельна ни одной из сторон многоугольника.
  30. Доказать, что для всякого простого числа p, не равного 2 или 5, существует натуральное число k такое, что p·k записывается в десятичной системе одними единицами.
  31. В правильном двадцатиугольнике отметили 9 вершин. Докажите, что найдется равнобедренный треугольник с вершинами в отмеченных точках.
  32. Узлы бесконечной клетчатой бумаги раскрашены в два цвета. Докажите, что существуют две вертикальные и две горизонтальные прямые, на пересечении которых лежат
    точки одного цвета.
Читать далее

Формула включений и исключений.

Пусть |Ω| - общее количество объектов, а |Ai| — количество объектов, которые обладают свойством i, |A1∩A2| — количество объектов, обладающих свойствами 1 и 2,...,|A1∩...∩An| — количество объектов, обладающих свойствами 1,...,n. Тогда количество объектов, не обладающих ни одним из свойств равно:

Формула включений и исключений. 3

Примеры решения задач

В летнем лагере 70 ребят. Из них 27 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются спортом. В драмкружке 10 ребят из хора, в хоре 6 спортсменов, в драмкружке 8 спортсменов; 3 спортсмена посещают и драмкружок, и хор. Сколько ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке.

Решение:

70-27-32-22+10+6+8-3=10.

Ответ: 10 ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке.


Сколько существует натуральных чисел, не превосходящих 1000, которые не делятся ни на 3, ни на 5?

Решение:

Натуральное число, которое делится на 3 можно представить в виде: 3·n, где n - натуральное число. Следовательно, 333 числа делятся на 3.

Натуральное число, которое делится на 5 можно представить в виде: 5·n, где n - натуральное число. Следовательно, 200 чисел делятся на 5.

Натуральное число, которое делится и на 3 и на 5 можно представить в виде: 15·n, где n - натуральное число. Следовательно, 66 чисел делятся на и на 3 и на 5.

1000-333-200+66=533.

Ответ: 533 числа не делятся ни на 3, ни на 5.


Сколько существует натуральных чисел, не превосходящих 1000, которые не делятся ни на 5, ни на 7?

Решение:

Натуральных чисел, которые делятся на 5: 200.

Натуральных чисел, которые делятся на 7: 142.

Числа, которые делятся и на 5 и на 7: 28.

1000-200-142+28=686.

Ответ: 686 чисел, не превосходящих 1000, не делятся ни на 5, ни на 7.


Каждая сторона в треугольнике ABC разделена на 8 равных отрезков. Сколько существует различных треугольников с вершинами в точках деления (точки A, B, C не могут быть вершинами треугольников), у которых ни одна сторона не параллельна ни одной из сторон треугольника ABC?

Решение:

На каждой стороне треугольника 7 точек. Всего можно построить 73 треугольников. У 3·72 треугольников одна из сторон параллельна одной из сторон треугольника ABC, у 3·7 треугольников –  две стороны, у 1 треугольника –  все стороны.

73-3·72+3·7-1=343-147+21-1=216.

Ответ: 216 треугольников.


В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на своё место?

Решение:

Общее количество пересаживаний равно: 30!.

Количество пересаживаний, когда 1 ученик остается на своем месте равно: 29!·(30!/(30-1)!/1!)=29!·30.

Количество пересаживаний, когда 2 ученика остаются на своем месте равно: 28!·30!/(30-2)!/2!=28!·30·29/2!

...

Количество пересаживаний, когда 29 учеников остаются на своем месте равно: 1!·30!/(30-29)!/29!=30.

Количество пересаживаний, когда 30 учеников остаются на своем месте равно: 0!·30!/(30-30)!/30!=1.

30!-29!30+28!·30·29/2!-...-30+1=30!(1-1/1!+1/2!-...-1/29!+1/30!)=30!(1/2!-...-1/29!+1/30!).

Ответ: 30!(1/2!-...-1/29!+1/30!).

Читать далее

Размещения и сочетания.

Сколько вариантов подбора четырехзначного кода, состоящего только из цифр? А из букв латинского алфавита? Прочитав данную статью до конца, вы сможете решить данные задачи без проблем. Итак, начнем.

Размещениями называют множества, составленные из n элементов по m элементов, которые отличаются либо составом элементов, либо их порядком.

Число всех возможных размещений, если все n элементы различны, определяется формулой:

 A=n·(n-1)·(n-2)·...·(n-m+1).

Число размещений по m с повторениями из n элементов равно nm. Таким образом: A(c повторениями)=nm.

Примеры:

  1. Сколько способов выбрать старосту и заместителя старосты из 25 кандидатов?
    Решение:
    25·24=600
    Ответ: 600.
  2. Сколькими способами девочка Кристи может разложить 6 кукол по трём ящикам, если каждый ящик может вместить все куклы?
    Решение:
    A=312 =531441
    Ответ: 531441.

Сочетаниями из n элементов по m называются множества, содержащие m элементов из числа n заданных, и которые отличаются хотя бы одним элементом.

Число сочетаний из n элементов по m обозначают: С(m,n).

Число всех возможных сочетаний, если все n элементы различны, определяется формулой:

С(m,n)=n!/(m!(n-m)!).

Число сочетаний с  повторениями равно: С(m,n) с повт. = С(m,n+m-1).

Полагают, что С(0,n)=1.

Для количества сочетаний справедливы равенства:

  1. С(m,n)=C(n-m,n),
  2. C(m+1,n+1)=C(m,n)+C(m+1,n),
  3. C(0,n)+C(1,n)+C(2,n)+...+C(n-1,n)+C(n,n)=2(число всех подмножеств множества, состоящего из n элементов равно 2n).

Примеры:

  1. Сколько способов выбрать три лица на три одинаковые должности из 25 кандидатов?
    Решение:
    С(3,25)=25!/(3!(22)!)=(23·24·25)/6=2300
    Ответ: 2300.
  2. В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток?
    Решение:
    С(12,10)=С(12,12+10-1)=С(12,21)=21!/(12!(21-12)!)=293930
    Ответ: 293930.
Читать далее

Элементы комбинаторики. Перестановки.

Элементы комбинаторики. Перестановки. 4

Множества элементов, состоящие из одних и тех же различных элементов и отличающиеся друг от друга только их порядком, называются перестановками этих элементов.

В перестановках элементы только переставляют. Поменяв местами любые два элемента множества, мы получим новую перестановку. Количество возможных перестановок множества из n элементов обозначают: Pn.

Алгоритм нахождения перестановок:

  1. Выберем элемент, который будет находиться на первом месте. Количество способов его выбрать равняется количеству элементов. Всего n элементов, значит количество способов тоже n.
  2. Так как первый элемент уже на месте, то количество элементов которые ещё не на месте уменьшается на единицу. На второе место мы можем поставить n-1 элемента.
  3. На третье место n-2 элемента.
  4. На четвертое n-3 элемента.
  5.  ...

n. На n-ое место оставшийся элемент.

Зная как находятся перестановки и используя правило произведения из комбинаторики, найдем количество перестановок множества из n элементов.

Pn=n·(n-1)·(n-2)·(n-3)·...·1=n!

n! - произведение n первых натуральных чисел (читается как "эн факториал")

Замечание: 

Пустое множество можно упорядочить только одним способом. Полагают, что 0!=1.

Примеры:

  1. Сколько различных способов выстроиться в ряд компании из 6 человек?

    Решение:

    P6=6·(6-1)·(6-2)·(6-3)·...·1=6!=720.

    Ответ: 720.

  2. Сколько различных чисел можно составить из цифр 1, 2 и 3?

    Решение:

    P3=3·(3-1)·(3-2)=3!=6.

    Ответ: 6.

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

Pn(n1,n2,n3,...,nk)=n!/(n1!·n2!·n3!·...·nk!)

Примеры:

  1. Сколько различных перестановок букв можно сделать в слове: М,А,Т,Е,М,А,Т,И,К,А?

     Решение:

     Количество букв равно 10.

     Буква М повторяется 2 раза, буква А - 3 раза, буква Т - 2 раза, буквы И и К по одному разу.

     P10(2,3,2,1,1)=10!/(2!·3!·2!·1!·1!)=3628800/(2·6·2·1·1)=151200

    Ответ: 151200.

  2. Сколько различных шестизначных чисел можно составить из цифр 1, 1, 2, 2, 2, 3?

     Решение:

     P6(1,2,3)=6!/(1!·2!·3!)=720/12=60.

    Ответ: 60.

Читать далее