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