В компании из 100 человек некоторые знакомы друг с другом. Каждую минуту из компании уходит человек, который имеет знакомых больше, чем любой из оставшихся. Через несколько минут такого человека не нашлось. Какое наименьшее количество людей могло остаться к этому моменту в компании?
Подсказка
Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека 
.
Решение
Ответ: 3.
Решение. Оценка. Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека . Пусть 
тот, у кого больше всех знакомых. Если у один знакомый, то у кого-то из 
и 
тоже есть один знакомый (сам ), но тогда у не больше всех знакомых. Следовательно, у два знакомых и он знаком с и . Пусть 
— человек, который ушел перед . Так как у хотя бы два знакомых из 
и , то у их должно быть не менее 3 . Значит, знаком с 
и . Но тогда и у три знакомых. Противоречие.
Пример. Выстроим людей в ряд и познакомим каждого со всеми, кроме его соседей в ряду. Кроме того, не будем знакомить 1 и 3 человек в ряду. Последний человек в ряду знаком со всеми, кроме одного (если людей больше трех). А все остальные люди в ряду имеют как минимум двух незнакомых. Более того, после ухода последнего получается ряд, вновь удовлетворяющий условиям выше. Следовательно, люди будут уходить, пока не останется 3 человека.