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

Принцип Дирихле, или принцип ящиков. При любом распределении n+1 или более предметов по n ящикам в каком-нибудь ящике окажется не менее двух предметов.

Если число кроликов больше числа клеток, в одной из клеток сидит наверняка более одного кролика.

В более общей форме принцип ящиков состоит в следующем: при любом распределении nk+1 или более предметов по n ящикам в каком-нибудь ящике окажется не менее чем k+1 предмет.

Задачи.

1. В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них заведомо оказались два шарика одного цвета?

2. В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.

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

4. В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

5. В стране Курляндии m футбольных команд (по 11 футболистов в каждой). Все футболисты собрались в аэропорту для поездки в другую страну на ответственный матч. Самолет сделал 10 рейсов, перевозя каждый раз по m пассажиров. Еще один футболист прилетел к месту предстоящего матча на вертолете. Докажите, что хотя бы одна команда была целиком доставлена в другую страну.

6. Дано 8 различных натуральных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.

7. Докажите, что в любой компании из 5 человек есть двое, имеющее одинаковое число знакомых в этой компании.

8. а) Какое наибольшее число полей на доске 8\times 8 можно закрасить в черный цвет так, чтобы в любом уголке из трех полей было по крайней мере одно незакрашенное поле?

б)
Какое наименьшее число полей на доске 8\times8 можно закрасить в черный цвет так, чтобы в каждом уголке было по крайней мере одно черное поле?

9. 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно одну задачу, школьники, решившие ровно 2 задачи, и школьники, решившие ровно 3 задачи. Докажите, что есть школьник, решивший не менее 5 задач.

10. Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никакие два из них не били друг друга?

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

12. В квадрат со стороной 1 м бросили 51 точку. Докажите, что какие-то 3 из них можно покрыть квадратом со стороной 20 см.

13. В бригаде 7 человек, и их суммарный возраст 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142 лет.

14. Докажите, что среди степеней двойки есть две, разность которых делится на 1987.

15. Докажите, что из 52 целых чисел всегда найдутся два, разность квадратов которых делится на 100.

16. Докажите, что среди чисел, записываемых только единицами, есть число, которое делится на 1987.

17. Докажите, что существует степень тройки, оканчивающаяся на 001.

18. В клетках таблицы 3\times3 расставлены числа -1,0,1. Докажите, что какие-то две из 8 сумм по всем строкам, всем столбцам и двум главным диагоналям будут равны.

19. 100 человек сидят за круглым столом, причем более половины из них — мужчины. Докажите, что какие-то два мужчины сидят напротив друг друга.

20. 15 мальчиков собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов.

21. Цифры 1,2,\dots,9 разбили на 3 группы. Докажите, что произведение чисел в одной из групп не меньше 72.

22. В таблице 10\times10 расставлены целые числа, причем любые 2 числа в соседних клетках отличаются не более, чем на 5. Докажите, что среди этих чисел есть 2 равных.

23. Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно не знакомых.

24. На клетчатой плоскости дано 5 произвольных узлов сетки. Докажите, что середина одного из отрезков, соединяющих какие-то 2 из этих точек, тоже является узлом сетки.

25. На складе имеется по 200 сапог 41, 42 и 43 размеров, причем из этих 600 сапог 300 левых и 300 правых. Докажите, что из них можно составить не менее 100 годных пар обуви.

26. В алфавите языка племени Ни-Бум-Бум 22 согласных и 11 гласных, причем словом в этом языке называется произвольное буквосочетание, в котором нет двух согласных подряд и ни одна буква не использована дважды. Алфавит разбили на 6 непустых групп. Докажите, что из всех букв одной из групп можно составить слово.

27. Докажите, что среди любых 10 целых чисел найдется несколько, сумма которых делится на 10.

28. Дано 11 различных натуральных чисел, не больших 20. Докажите, что из них можно выбрать 2 числа, одно из которых делится на другое.

29*. 11 пионеров занимаются в пяти кружках дома культуры. Докажите, что найдется два пионера A и B, такие, что все кружки, которые посещает A, посещает и B.

Комментариев: 6

  1. 1 Ирина:

    Очень содержательный сайт для тем, кто хочет знать и думать не нормами ЕГЭ в математике! Рекомендую всем!!!!!

    [Ответить]

  2. 3 Лучший карточный фокус | Математика, которая мне нравится:

    [...] карты обязательно будут иметь одинаковую масть (см. принцип Дирихле). Первой должна быть выложена именно одна из этих двух [...]

  3. 4 Две задачи | Математика, которая мне нравится:

    [...] по принципу Дирихле среди любых натурального числа найдется хотя бы одна [...]

  4. 5 Александр:

    Есть задача, которая уже неделю не дает мне покоя. Звучит она следующим образом:
    Дверь закрыта на несколько замков. У каждого из M человек есть несколько ключей, притом никакие N человек не могут открыть дверь, а любые N+1 человек могут. Найдите наименьшее количество замков, на которые закрыта дверь и определите количество ключей у каждого человека.
    Кажется это задача на принцип Дирихле, но не знаю как именно к ней “подступиться”.

    [Ответить]

    Екатерина Reply:

    Александр, вы меня заинтересовали своей задачей, тоже не знаю как подступиться

    [Ответить]

Оставьте свой отзыв

Добавить изображение