Олимпиада им. Эйлера

Докажем, что из любой популярной группы, состоящей более, чем из ребят, можно кого-то удалить так, что группа останется популярной. Пусть все приехавшие имеют ровно по знакомых. Рассмотрим какую-то популярную группу в которую входит не менее школьников. Будем считать, что все остальные школьники входят в группу Предположим, что при удалении из любого школьника она перестаёт быть популярной. Тогда школьники из этой группы делятся на тех, для каждого из которых найдётся кто-то из знакомый только с ним — назовём эту группу — и остальных, которые знакомы только со школьниками из (и потому, попав после удаления из группы в группу оказываются незнакомы ни с кем из — назовём эту группу Каждому школьнику из группы сопоставим одного школьника из который знаком только с этим школьником из Они образуют группу Пусть остальные школьники из образуют группу Пусть означает число элементов во множестве Все школьники из суммарно имеют не менее знакомств в С другой стороны, школьники из суммарно имеют не более знакомств в Значит, Но поскольку а

получаем, что — противоречие.