2019-04-29
На некотором собрании присутствовало $2n$ человек, каждый из которых был знаком не менее чем с $n$ присутствующими. Доказать, что за круглый стол на 4 лица можно посадить четырех из присутствующих так, чтобы каждый сидел между своими знакомыми.
Решение:
Если все присутствующие знакомы друг с другом, то возможность рассадить таким образом 4-х человек сомнения не вызывает. Пусть теперь $A$ к $B$ незнакомы между собой. Каждый из них имеет среди остальных $2n - 2$ присутствующих не менее $n$ знакомых; так как $n + n = 2n = (2n - 2) + 2$, то у $A$ и $B$ имеется, минимум, два общих знакомых $C_1$ и $C_2$ - и мы можем посадить $A$ и $B$ напротив друг друга, а между ними посадить $C_1$ и $C_2$.