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

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

Принцип Дирихле. 27 октября 2012 года

«Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика». В каждой задаче важно понять что мы считаем «клетками», а что «кроликами». И только после этого мы применяем принцип Дирихле в привычной нам формулировке.

1.

a)

Докажите, что в любой футбольной команде есть два игрока, которые родились в один и тот же день недели.

б)

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

2.

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

3.

Докажите, что в любом наборе из n+1 чисел найдутся два числа, разность которых делится на n.

4.

Каждая клетка таблицы 2013х2013 покрашена в один из 2012 цветов. За ход можно взять строку или столбец и, если там есть две клетки одного цвета, перекрасить эту строку или столбец в этот цвет. Можно ли за несколько ходов покрасить всю таблицу в один цвет?

5.

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

6.

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

7.

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

Дополнительные задачи

8.

а)

Докажите, что найдется число вида 111…11000..00, делящееся на 2013.

б)

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

9.

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

10.

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