Физтех 2026, отборочный этап, 11 класс, второй тур, задача 9
Каждый из участников школьного кружка, кроме Андрея, дружит с разным числом других участников. Андрей дружит с из них. Каково наибольшее возможное число школьников в кружке?
Ответ
Ответ. .
Решение. Если среди всех остальных (без Андрея) есть кружковец , который дружит со всеми, то каждый дружит по крайней мере с одним школьником, следовательно, в группе остальных дружбы распределены так: , где — количество кружковцев. Удалив из группы остальных участников двоих: и того школьника, который дружит только с (т. е. имеющего ровно дружбу), получим аналогичную ситуацию, только вместо будет . Так, попарно удаляя кружковцев, мы придём к ситуации, когда из группы остальных либо будут удалены все, либо останется один, который дружит с Андреем. При каждом удалении число друзей Андрея уменьшается на . Значит, были удалены либо человек, и тогда общее количество школьников равно , либо человек, при этом один остался. В этом случае получаем кружковцев.
Если среди остальных (кроме Андрея) нет школьника, который дружит со всеми, то между ними дружбы распределены так: . В этом случае, если удалить того, кто ни с кем не дружит, то получится предыдущая ситуация — человек, имеющий друзей, дружит со всеми оставшимися. Поэтому в этом случае число кружковцев равно или .