Задача
В стране лингвистов существует n языков. Там живет m людей, каждый из которых знает ровно три языка, причём для разных людей эти наборы различны. Известно, что максимальное число людей, любые два из которых могут поговорить без посредников, равно k. Оказалось, что 11n ≤ k ≤ m/2.
Докажите, что тогда в стране найдутся хотя бы mn пар людей, которые не смогут поговорить без посредников.
Решение
Обозначим через B множество из k человек, которые могут поговорить без посредников. Рассмотрим произвольного человека (мистера X), не вошедшего в множество B. Для него существует такой человек из B (мистер X'), что пересечение их языков пусто. Оценим количество тех людей из B, которые могут поговорить с мистером X. Такие люди имеют хотя бы один общий язык и с мистером X, и с мистером X', а значит, их не больше чем 3·3n. Таким образом, для каждого человека, не вошедшего в множество B, мы нашли как минимум k – 9n представителей множества B, которые не могут с ним поговорить без посредника. Значит, всего таких пар (m – k)(k – 9n) ≥ (m – m/2)(11n – 9n) ≥ m/2·2n = mn.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь