На вечеринке у каждого человека спросили, сколько у него знакомых среди присутствующих. Были получены следующие ответы: 2,2,2,3,3,6,6,7,7. Докажите, что кто-то ошибся?

Если сложить все числа, то получится 50, что на 1 больше, чем количество людей на вечеринке. Значит, кто-то из участников вечеринки ошибся и указал неправильное число знакомых.

Чтобы доказать, что кто-то ошибся, можно воспользоваться следующим алгоритмом:

1. Сложить все числа, которые были указаны в ответах.
2. Проверить, что сумма равна количеству людей на вечеринке (в данном случае 9).
3. Если сумма не равна 9, то это означает, что кто-то указал неправильное число.

Представим посетителей в виде графа. Получим граф с  вершинами (по числу ответов), степени которых соответствуют числу знакомых каждого посетителя .
Количество ребер в графе равно сумме степеней его вершин деленое на . Таким образом получаем, что число ребер в графе равно: .
Рассмотрим для примера группу вершин графа в которую входят  посетителя, ответившие . Максимально в данной группе может быть  ребер (в случае, если каждый из группы знаком с каждым). Значит во второй группе вершин (в которую входят  посетителей, ответившие ) ребер, связанных с этими вершинами, должно быть  . Однако, сумма степеней вершин во второй группе (количество ребер, прилегающих к вершинам второй группы) равна  , противоречие. Значит такой граф построить нельзя и, следовательно, кто-то ошибся.