В классе 30 ребят, некоторые из них дружат. Оказалось, что среди любых 10 ребят из этого класса какие‑то двое дружат. Какое наибольшее количество школьников, имеющих ровно двух друзей‑одноклассников может быть в этом классе?
Ответы
Ответ:24
( пример: 8 графов треугольниками и 6 ребят, которые друг с другом знакомы).
Объяснение:
Доказательство, что больше нельзя: Допустим можно больше 24. Возьмём 2 имеющих 2 знакомых и незнакомых между а и б (они обязательно найдутся, иначе все со всеми дружат), и их знакомых, их знакомых максимум 4. Вычтем а и б и их знакомых из общего количества. Возьмем следующих двоих ( они тоже имеют 2 знакомых)из 24 оставшихся и снова вычтем их. Заметим, что сделав эту операцию 5 раз мы сможем найти 10 незнакомых ( а и б не знакомы с следующими двумя, так как мы вычли их знакомых вместе с ними и ТД для всех последующих 4 пар). Значит мы можем вычесть не более чем 4 пары, то есть количество учеников, имеющих 2 знакомых не более чем 6*4=24) А в пятой шестерки все со всеми знакомы,иначе мы бы смогли выбрать среди пятой шестерки двоих незнакомых