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

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

Занятие 4 (17 октября 2015). Принцип Дирихле

Докажите, что

a.

Если рассадить тридцать одного кролика в 7 клеток, то найдется клетка, в которой сидит, по крайней мере, 5 кроликов.

b.

Если расселить 110 ЛМШ-ат в 36 комнат, то найдется комната, в которой живет, по крайней мере, 4 ЛМШ-онка.

Принцип Дирихле (общий случай): а) «Если в N клетках сидят не менее M кроликов, то найдется хотя бы одна клетка, в которой содержится не менее ^M/_N кроликов»
б) «Если в N клетках сидят не более M кроликов, то найдется хотя бы одна клетка, в которой содержится не более ^M/_N кроликов»

Доказательство: а) пусть в каждой клетке число кроликов меньше, чем ^M/_N. Тогда зайцев меньше, чем N×(^M/_N) = M. Противоречие!

1.

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

2.

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

3.

Олимпиаду писало 70 мехматян. Кирилл набрал 33 балла, остальные меньше. Докажите, что по крайней мере три мехматянина набрали одинаковое количество баллов.

4.

В ковре размером 44 метра моль проела 15 дырок. Докажите, что из этого ковра можно вырезать коврик размера 11 метр, в котором нет ни одной дырки.

5.

В клетках таблицы 33 расставлены числа – 1, 0, 1. Рассмотрим следующие суммы: сумма трех чисел в каждой строчке, каждом столбце и по двум диагоналям. Могут ли быть все эти суммы различными?

6.

Может ли Софья расставить на шахматной доске 17 королей так, чтобы они не били друг друга?

7.

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

8.

Числа 1, 2, 3,..., 9 разбиты на три группы. Докажите, что произведение чисел в одной из групп меньше 72.

Для самостоятельного решения

9.

65 школьников написали 3 контрольные работы. За каждую контрольную работу ставилась одна из оценок: «2», «3», «4» или «5». Докажите, что найдутся школьники, написавшие все контрольные работы одинаково.

10.

10 подружек договорились в «День подружек» обменяться поздравлениями. Каждая отправила по одной SMS-ке пяти подругам. Докажите, что какие-то две из них обменялись SMS-ками друг с другом.