Условие
На конгресс приехали 1000 делегатов из разных стран. Каждый делегат знает
несколько языков. Известно, что любые трое могут разговаривать между собой без
помощи остальных. (При этом, возможно, одному из них придётся переводить
разговор двух других.) Доказать, что всех делегатов можно расселить в 500
комнатах так, чтобы в каждой комнате располагались 2 делегата и при этом они
могли бы поговорить между собой.
Решение
Выберем каких-то трёх делегатов конгресса; среди них найдутся двое, знающие
один язык — их-то мы и поместим в одном номере гостиницы. Из оставшихся 998 делегатов снова отберем троих, среди которых снова найдутся двое, которых можно будет разместить в одном номере — и т. д., пока у нас не останутся всего 4 делегата
A,
B,
C и
D. Если каждые два из них могут говорить между собой, то с размещением этих делегатов не будет никаких трудностей; если же
A и
B между собой не говорят, то и
C, и
D могут служить для них переводчиками (что и делает возможным общение в тройках
A,
B,
C и
A,
B,
D делегатов); это позволяет поместить, скажем
C в одни номер с
A, а
D — в один номер с
B.
Источники и прецеденты использования
