ГЛАВНАЯ » РЕШЕБНИК

2014-06-08   
В компании, состоящей из пяти человек, среди любых трех человек найдутся двое, которые знают друг друга, и двое, незнакомых друг с другом. Доказать, что компанию можно рассадить за круглым столом так, чтобы по обе стороны от каждого человека сидели его знакомые.


Решение:


Заметим, что каждый гость знает ровно двоих из остальных четырех гостей. В самом деле, допустим, что гость А имеет трех знакомых: В, С и D. Тогда если В и С знают друг друга, то среди А, В и С нет незнакомых. Поэтому В и С (аналогично В и D, С и D) незнакомы, и среди В, С, D нет знакомых. Аналогично рассматривается случай, когда А имеет трех незнакомых. Пусть теперь знакомые А - гости В и С. Тогда В и С не знакомы, и у В есть знакомый D ($D \neq A, D \neq C$). Если D знаком с С, то каждый из гостей A, В, С, D знаком с двумя гостями внутри этой четверки, поэтому пятый гость Е не может быть ни с кем знаком. Таким образом, D не знаком с С, и так как он не знаком с А, а С и с знаком с В, то С и D знакомы с Е. Следовательно, гостей можно рассадить, например, в таком порядке: E, D, В, A, С.