Кружок 9-11 классов

Принцип Дирихле 1 (22.09.2012)

1.

а)

Фермер рассадил 5 кроликов по 4 клеткам. Докажите, что хотя бы в одну клетку попало не менее двух кроликов.

б)

Докажите, что если он рассадил 11 кроликов по 5 клеткам, то найдется клетка, в которой не менее трех кроликов.

в)

А можно ли сказать, что при рассаживании m кроликов по n клеткам найдется клетка, в которой не меньше ^m/_n кроликов? Докажите.

2.

Известно, что в Нью-Йорке жителей больше, чем волос на голове у любого из них, и что среди жителей Нью-Йорка нет полностью лысых, у которых на голове не осталось бы ни одного волоса. Следует ли отсюда, что в Нью-Йорке непременно найдутся по крайней мере два жителя с одинаковым числом волос на голове?

3.

а)

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

б)

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

в)

Как изменится решение задачи, если в ящике лежат 12 пар чёрных и 12 пар синих ботинок и требуется составить пару одного цвета (как в пункте а) и пару черного цвета (как в пункте б)? Ботинки, в отличие от носков, бывают левыми и правыми.

4.

В школе 30 классов и 1000 учащихся. Докажите, что есть класс, в котором не менее 34 учеников.

5.

Можно ли разложить 44 шарика на 9 кучек так, чтобы количество шариков в разных кучках было различным?

6.

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

7.

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

8.

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

Дополнительный листок

9.

Числа 1, 2, 3, ..., 101 выписаны в ряд в каком-то порядке. Докажите, что из них можно вычеркнуть 90 так, что оставшиеся 11 будут расположены по их величине (либо возрастая, либо убывая).

10.

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

11.

В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.

12.

Имеется n целых чисел. Доказать, что среди них найдутся несколько (или, быть может, одно) сумма которых делится на n.

13.

В Мехико для ограничения транспортного потока для каждой частной автомашины устанавливаются два дня недели, в которые она не может выезжать на улицы города. Семье требуется каждый день иметь в распоряжении не менее 10 машин. Каким наименьшим количеством машин может обойтись семья, если её члены могут сами выбирать запрещённые дни для своих автомобилей?