Question

В классе 30 ребят, некоторые из них дружат. Оказалось, что среди любых 10 ребят из этого класса какие‑то двое дружат. Какое наибольшее количество школьников, имеющих ровно двух друзей‑одноклассников может быть в этом классе?

Answer 1

Ответ:24

( пример: 8 графов треугольниками и 6 ребят, которые друг с другом знакомы).

Объяснение:

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

Answer 2

Давайте рассмотрим данную задачу. Если в классе 30 ребят и среди любых 10 ребят какие-то двое дружат, то это означает, что каждый ученик дружит с 9 другими детьми. Если бы каждый имел ровно двух друзей, это бы означало, что среди любых 10 ребят было бы по 5 друзей у каждого.

Допустим, есть N учеников, у каждого из которых ровно 2 друга. Тогда можно выразить общее количество дружеских связей в классе следующим образом: 2 * N / 2 (поскольку каждая дружба учитывается дважды). Это должно быть равно общему количеству дружеских связей в классе, которое равно C(30, 2) (количество сочетаний 2 из 30).

Итак, у нас есть уравнение:

2 * N / 2 = C(30, 2)

Решая это уравнение:

N = C(30, 2) N = 30! / (2!(30-2)!) N = (30 * 29) / (2 * 1) N = 435

Таким образом, в этом классе наибольшее количество учеников, имеющих ровно двух друзей-одноклассников, равно 435.