Олимпиадная задача: языки и коммуникация в стране лингвистов
В стране лингвистов существует 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.
Обсуждение
0Комментариев пока нет.