Областная олимпиада по математике, 2009 год, 10 класс

В школе учатся 2009 мальчиков и 2009 девочек. Каждый школьник посещает не более 100 кружков. Известно, что любой мальчик посещает с каждой девочкой по крайней мере один общий кружок. Докажите, что существует кружок, который посещают по крайней мере 11 мальчиков и по крайней мере 11 девочек.

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

Возьмем любого мальчика из 2009 мальчиков. Если бы количество кружков было не ограничено, то мальчик ходил бы в 2009 кружков. Но есть ограничение в 100 кружков. По принципу Дирихле по крайней мере в 9 кружках из 100 будет 11 девочек. Но у этих девочек есть по крайней мере один соответствующий ей мальчик, ходящий в этот кружок