В компании сплетников и сплетниц 63 человек. Каждый человек знаком не более, чем с 8 другими, причём каждый сплетник знаком только со сплетницами, а каждая сплетница - только со сплетниками. Если кто-то из них узнаёт сплетню, то он сразу рассказывает её всем своим знакомым. Известно, что кто бы ни узнал сплетню, через некоторое время эту сплетню узнают все. Какое наибольшее количество сплетниц может быть в этой компании?

Оценка:

Так как каждый знаком не более, чем с восемью другими, каждая сплетница должна быть знакома хотя бы с одним сплетником, значит, сплетников не меньше 7. Пусть у нас 7 сплетников, тогда каждая из сплетниц знакома с одним сплетником (иначе кто-то новость не узнает), но так как каждый сплетник знаком не более, чем с восемью сплетницами, граф знакомств бьётся на 7 компонентов, значит, новость узнают не все. Значит, сплетников было не меньше восьми.

Пример:

Первый сплетник знает с 1-ой по 8-ую сплетниц, второй - с 8-ой по 15-ую, третий - с 15-ой по 22-ую, ..., восьмой - с 50-ой по 55-ую. Тогда для каждого сплетника найдётся сплетница, знающая хотя бы одного другого сплетника.

Ответ: 55 сплетниц.