Районная олимпиада, 2011-2012 учебный год, 9 класс

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

Комментарий/решение

По принципу Дирихле.

200-сумма открыток. У каждого человека 19 вариантов могут дать всем кроме себя. Значит 200 кроликов и 190 клеток. В наихудшем случае в 190 клеток пойдут в 190 кроликов. Оставшийся 10 кроликов куда бы не пошли там будет по 2 кролика. Это значит что кто то с кем-то обменяются открытками.