microbik.ru
1

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


Задача 1. В 100 клетках живёт 101 кролик. Докажите, что найдётся клет-ка, в которой живут по крайней мере два кролика.

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

Задача 2. Докажите принцип Дирихле. (Указание. Рассуждайте от про-тивного.)

Задача 3. Антропологи установили, что у человека не может быть более 500.000 волос на голове. Докажите, что в Риге (свыше 800.000 жителей) живут по крайней мере два человека с одинаковым количеством волос на голове. (Указание. Решите задачу двумя способами: сначала – рассуждая от противного; затем – используя принцип Дирихле.)

Задача 4. Ясно, что для Санкт-Петербурга с его более чем пятимиллион-ным населением вывод предыдущей задачи тем более верен. А не кажется ли вам, что там обязательно найдётся и больше чем два жителя с одинаковым количеством волос на голове? В таком случае минимум сколько?

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

Задача 5. Докажите обобщённый принцип Дирихле.

Задача 6. В доме живёт 330 человек. Самому старшему из них 82 года. Докажите, что среди жильцов этого дома найдётся четверо одного и того же возраста. А пятеро?

* * *

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

Задача 8. В клетках таблицы 88 расставлены числа , 0, 1. Докажите, что если найти суммы чисел в каждом столбце, в каждой строке и в обеих главных диагоналях, то какие-то две суммы совпадут.

Задача 9. У Незнайки в Цветочном городе 101 друг. Известно, что у жи-телей этого города бывают глаза десяти различных цветов и волосы десяти различных цветов. Обязательно ли среди друзей Незнайки найдутся двое, у которых совпадают как цвет глаз, так и цвет волос?

Задача 10. За круглым столом сидит 20 человек: 11 мужчин и 9 женщин. Докажите, что найдутся двое мужчин, сидящих напротив друг друга.

Задача 11. В ученическом совете 4 активиста. Они создают всевозмож-ные комиссии с разными направлениями работы, состоящие из 1, 2, 3 или 4 членов. Составы никаких двух комиссий не совпадают; всего комиссий 9. Дока-жите, что найдутся две комиссии, в которых нет общего члена.

Задача 12. У каждого ученика первого класса есть набор из ста карточек с написанными на них числами от 1 до 100. Учительница попросила выбрать четыре карточки и расположить их так, чтобы получилось верное численное равенство: . Вова свои карточки забыл дома и – чтобы выполнить задание – отобрал 21 карточку у Серёжи. Наверняка ли их хватит для составления нужного равенства?

Задача 13. Янис в течение 50 дней решил 79 задач; причём не было дня, когда бы он не решил ни одной задачи. Докажите, что найдутся несколько подряд идущих дней (возможно, один-единственный), за которые Янис решил ровно 20 задач.

Задача 14. Каждая клетка прямоугольной таблицы 47 покрашена в бе-лый или чёрный цвет. Докажите, что можно выбрать 2 столбца и 2 строки, все 4 клетки пересечения которых покрашены в один цвет.

Задача 15. В конференции по лингвистике принимают участие 70 деле-гатов, говорящих на 11 различных языках. Известно, что ни одним языком не владеют более 15 делегатов. Оргкомитет решил, что официальным языком кон-ференции будет считаться язык, на котором говорят по крайней мере 5 делега-тов. Докажите, что официальных языков на конференции не меньше 3.

Задача 16. В фестивале принимают участие 6 музыкантов. Каждый день некоторые из них выступают, а остальные находятся в зале и слушают (в течение дня музыканты свой «статус» не меняют). Можно ли так организовать выступления музыкантов, чтобы каждый из них имел возможность послушать всех остальных из зала?

Задача 17. В мастерской художника изготовлены 36 скульптур массой 490 кг, 495 кг, 500 кг, …, 665 кг. Можно ли все скульптуры вывезти на авто-мобиле грузоподъемностью 3 тонны за 7 рейсов?

Задача 18. Каждая из вершин правильного двухсотугольника отмечена одним из чисел 1, 2, 3, …, 99. Докажите, что найдутся такие вершины двухсотугольника A, B, C, D, что отрезки АВ и CD будут равны и параллельны, а суммы записанных на их концах чисел равны.

* * *

Задача 19. Серёжа быстрее всех в классе выполнил первое задание учительницы (см. задачу 12), и она предложила ему задачу повышенной трудности: снова выбрать четыре карточки и расположить их так, чтобы получилось верное равенство: . Но 21 карточку у Серёжи отнял Вова, а еще 10 потерял он сам… Наверняка ли хватит оставшихся 69 карточек для выполнения задания?