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

Кружок 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 ученых переписывается с остальными. В их переписке речь идет лишь о трех темах. Каждая пара ученых переписывается друг с другом только по одной теме. Докажите, что не менее трех ученых переписываются друг с другом по одной и той же теме.