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