2019-04-29
На конгресс приехало 1000 делегатов из разных стран. Известно, что каждые трое из них могут говорить друг с другом без помощи остальных (однако при этом возможно, что одному из трех лиц придется служить переводчиком для двух других). Доказать, что всех делегатов конгресса можно так разместить в гостинице с двуместными номерами, что в каждом номере будут помещены делегаты, которые могут говорить друг с другом.
Решение:
Выберем каких-то трех делегатов конгресса; среди них найдутся двое, знающие один язык - их-то мы и поместим в одном номере гостиницы. Из оставшихся 998 делегатов снова отберем троих, среди которых снова найдутся двое, которых можно будет разместить в одном номере - и т. д„ пока у нас не останутся всего 4 делегата $А, В, С$ и $D$. Если каждые два из них могут говорить между собой, то с размещением этих делегатов не будет никаких трудностей; если же $А$ и $В$ между собой не говорят, то и $С$, и $D$ могут служить для них переводчиками (что и делает возможным общение в тройках $А, В, С$ и $А, В, D$ делегатов); это позволяет поместить, скажем $С$ в один номер с $A$, a $D$ - в один номер с $В$.