На бал пришли 30 юношей и 30 девушек. После вечера танцев оказалось, что все юноши танцевали с одним и тем же количеством девушек, а девушка Оля танцевала ровно с 15 юношами. Докажите, что какие-то две девушки танцевали с одним и тем же количеством юношей.
Подсказка
Отметим мальчиков синими точками, девочек — красными, а тех, кто танцевал друг с другом, соединим линиями. По условию из всех синих точек выходит поровну линий, и потому общее число линий делится на 30 .
Решение
Отметим мальчиков синими точками, девочек — красными, а тех, кто танцевал друг с другом, соединим линиями. По условию из всех синих точек выходит поровну линий, и потому общее число линий делится на 30 . Из красных точек может выходить 
линий. Заметим, что 
. Чтобы не нашлось двух девочек, танцевавших с одним и тем же количеством юношей, надо вычесть из этой суммы число от 0 до 30 так, чтобы разность разделилась на 30 . Но единственное подходящее для этого число 15 по условию вычесть нельзя.