Question

На саммит съехались 2018 политиков. Каждые двое собирались провести  переговоры без свидетелей. В какой-то момент оказалось, что среди любых четверых найдётся такой, который уже поговорил с тремя остальными. Какое наибольшее количество переговоров осталось провести?

Answer 1

Пусть А и Б не поговорили. Рассмотрим любую другую пару, В и Г. Если и они не поговорили, то в четвёрке А, Б, В, Г не найдётся поговорившего с тремя остальными, что противоречит условию. Следовательно, в любую пару не поговоривших обязательно входит А или Б.
Пусть А не поговорил кроме Б еще с кем-то, которого назовем В. Рассмотрим четверки вида А, Б, В, Г, где в роли Г – каждый из остальных политиков. Так как А не поговорил с Б и не поговорил с В, то в каждой такой четвёрке Г обязательно поговорил со всеми остальными. Таким образом, с А и Б наверняка поговорили все, кроме В. Значит, не проведёнными могли остаться только переговоры между Б и В, что условию не противоречит. Итого, осталось провести, как максимум, три встречи: А – Б, А – В и Б – В.