МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Занятие 10. Доказательства от противного Дирихле

Теорема 1 (принцип Дирихле). Если по n клеткам рассадить n + 1 кроликов, то найдется клетка, в которой сидит больше одного кролика.

Теорема 2 (обобщенный принцип Дирихле). Если по n клеткам рассадить более k · n кроликов, то найдется клетка, где сидит больше k кроликов.

1.

a)

В классе 35 учеников. Докажите, что среди них найдутся хотя бы двое, у которых фамилия начинается с одной буквы.

б)

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

2.

На 25 страницах книги 102 опечатки. Докажите, что на одной из них не менее 5 опечаток.

3.

В мешке лежат 4 красных и 2 синих шара. Какое наименьшее число шаров надо вытащить не глядя, чтобы среди них точно были такие шары:

a)

1 красный;

б)

1 синий;

в)

1 красный и 1 синий;

г)

два одноцветных?

4.

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

5.

В школе 65 девятиклассников, и все они сдают по три экзамена, за каждый из которых можно получить оценку 2, 3, 4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки за все экзамены?

6

34 пассажира едут в автобусе, который делает 9 остановок, и на этих остановках новые пассажиры не заходят. Докажите, что на каких-то двух остановках выйдет одинаковое число пассажиров (может быть, ни одного).

7

За 5 лет обучения студент сдал 31 экзамен, причем на каждом курсе он сдавал экзаменов больше, чем на предыдущем. На V курсе экзаменов было втрое больше, чем на I курсе. А сколько экзаменов было на IV курсе?

8

Дано 7 отрезков с длинами от 1/10 до 1. Докажите, что среди этих отрезков найдутся три, из которых можно составить треугольник.

9

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