Гуляем по графу

У одноклассников Пети может быть друзей — всего вариантов. Но если кто-то дружит со всеми, то у всех не меньше одного друга. Поэтому либо кто-то дружит со всеми, либо кто-то не дружит ни с кем. В обоих случаях остается вариантов: или

Пусть у больше всего друзей, а у — меньше всего. В первом случае дружит со всеми, а — только с Во втором случае не дружит ни с кем, а — со всеми, кроме В каждом из случаев дружит с Петей, а — нет. Переведём и в другой класс. Как мы уже видели, дружит со всеми из оставшихся, а — ни с кем из оставшихся. Поэтому после перевода у каждого стало на одного друга меньше (среди одноклассников). Значит, у оставшихся Петиных одноклассников снова будет разное число друзей среди одноклассников.

Cнова переведём самого “дружелюбного” и самого “нелюдимого” в другой класс и т. д. Повторяя эти рассуждения раз, мы переведём в другой класс пар школьников, в каждой из которых ровно один Петин друг. Итак, друзей у Пети