Условие
На международный конгресс приехало 578 делегатов из разных
стран. Любые три делегата могут поговорить между собой без помощи остальных
(при этом, возможно, одному из них придется переводить разговор двух других). Докажите, что всех делегатов можно поселить
в двухместных номерах гостиницы таким образом, чтобы любые двое, живущие
в одном номере, могли поговорить без посторонней помощи.
Решение
Возьмем произвольных трех делегатов; какие-то два из них точно могут поговорить между собой без переводчика. Поселим их в один номер.
Будем повторять эту операцию до тех пор, пока не останется 4 делегата. Как нетрудно проверить перебором, их всегда можно разделить в 2 номера так, чтобы живущие в каждом из номеров могли поговорить друг с другом без посторонней помощи.
Источники и прецеденты использования
