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