Задача 78529
|
|
 |
Условие
Собрались 2n человек, каждый из которых знаком не менее чем с n
присутствующими. Доказать, что можно выбрать из них четырёх человек и рассадить
их за круглым столом так, что при этом каждый будет сидеть рядом со
своими знакомыми (n2).
Решение
Если все присутствующие знакомы друг с другом, то возможность рассадить таким образом 4-х человек сомнения не вызывает. Пусть теперь A и B незнакомы между собой. Каждый из них имеет среди остальных 2n - 2 присутствующих не менее n знакомых; так как n + n = 2n = (2n - 2) + 2, то у A и B имеется, минимум, два общих знакомых C1 и C2 — и мы можем посадить A и B напротив друг друга, а между ними посадить C1 и C2.
