Олимпиадная классика (4)

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

Решение. Предположим, что в каждый день недели родилось не более трех учеников. Тогда в классе учится не более 3 × 7 = 21 ученика — противоречие.

При любом распределении nk + 1 или более предметов по n ящикам в каком-нибудь ящике окажется не менее чем k + 1 предмет.

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

В квадрате со стороной 10 отметили 201 точку. Докажите, что какие-то три из выбранных точек можно накрыть квадратом со стороной 1.

Решение. Разобьем квадрат на 100 квадратов со стороной 1. По принципу Дирихле в какой-то из них попадут по крайней мере три точки из выбранных.

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

Решение. Так как команд 10, каждая команда могла сыграть от 0 до 9 матчей (всего 10 вариантов). Предположим, что в какой-то момент все команды сыграли разное количество матчей. Это возможно, только если одна команда сыграла 0 матчей, одна — 1 матч, …, одна — 9 матчей. Но команда, которая сыграла 9 матчей, сыграла со всеми, в том числе и с командой, которая сыграла 0 матчей, — противоречие.