Попробую еще раз. "Доказать, что среди любых
![$6$ $6$](https://dxdy-04.korotkov.co.uk/f/3/2/7/327c36301dc71617dc7032f8ce30b23682.png)
людей есть либо
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно знакомых, либо
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно незнакомых".
То есть: либо среди любых
![$6$ $6$](https://dxdy-04.korotkov.co.uk/f/3/2/7/327c36301dc71617dc7032f8ce30b23682.png)
человек есть
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно знакомых, либо -- если среди них не найдется
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно знакомых, -- среди них найдется
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно незнакомых.
Пусть среди них найдется
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно знакомых (то есть найдется либо
![$6$ $6$](https://dxdy-04.korotkov.co.uk/f/3/2/7/327c36301dc71617dc7032f8ce30b23682.png)
, либо
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
, либо
![$4$ $4$](https://dxdy-03.korotkov.co.uk/f/e/c/f/ecf4fe2774fd9244b4fd56f7e76dc88282.png)
, либо
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно знакомых), тогда условие выполнено.
Теперь рассмотрим возможность, когда среди них не найдется
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно знакомых. Надо показать, что при этом найдется, по крайней мере,
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно незнакомых.
Если нет ни одной тройки попарно знакомых, значит, в каждой тройке найдется, по крайней мере, одна пара незнакомых между собой.
Обозначим множество наших шестерых человек как
![$X=\lbrace 1, 2, 3, 4, 5, 6 \rbrace$ $X=\lbrace 1, 2, 3, 4, 5, 6 \rbrace$](https://dxdy-01.korotkov.co.uk/f/8/c/f/8cfd74b4d8d9ebb4562999de975f555082.png)
. Возьмем из него произвольную тройку, пусть это будет, например, тройка
![$\lbrace 2, 4, 5 \rbrace$ $\lbrace 2, 4, 5 \rbrace$](https://dxdy-04.korotkov.co.uk/f/f/c/7/fc765efb38ef8bbd59854b18fcfb56d682.png)
, и пусть в ней парой незнакомых будет
![$\lbrace 2, 5 \rbrace$ $\lbrace 2, 5 \rbrace$](https://dxdy-04.korotkov.co.uk/f/b/1/3/b139aca57c18aabcdf460bdb17e386b582.png)
.
Возьмем все тройки, содержащие пару
![$\lbrace 2, 5 \rbrace$ $\lbrace 2, 5 \rbrace$](https://dxdy-04.korotkov.co.uk/f/b/1/3/b139aca57c18aabcdf460bdb17e386b582.png)
, и отметим, что она в них есть (это будет всего четыре тройки:
![$\lbrace1, 2, 5 \rbrace$ $\lbrace1, 2, 5 \rbrace$](https://dxdy-04.korotkov.co.uk/f/b/3/d/b3df4cb50d07f24081a9c7cab053866782.png)
,
![$\lbrace 3, 2, 5 \rbrace$ $\lbrace 3, 2, 5 \rbrace$](https://dxdy-01.korotkov.co.uk/f/c/c/a/cca34b9d7def12b4f66d12037b87bdd082.png)
,
![$\lbrace 4, 2, 5 \rbrace$ $\lbrace 4, 2, 5 \rbrace$](https://dxdy-01.korotkov.co.uk/f/4/5/2/452351252b4c101d325af4a978d08c4282.png)
и
![$\lbrace 6, 2, 5 \rbrace$ $\lbrace 6, 2, 5 \rbrace$](https://dxdy-02.korotkov.co.uk/f/d/f/f/dffae77797da6b9a4b9096dba1cd588e82.png)
).
Теперь возьмем другую произвольную пару незнакомых и отметим все четыре тройки, в которых она есть, и так далее. Рано или поздно -- в лучшем случае на третьем ходу, в худшем случае на пятнадцатом ходу -- обнаружится тройка, в которой будет три пары незнакомых.
За три хода получится, если сразу взять пары
![$\lbrace a, b\rbrace$ $\lbrace a, b\rbrace$](https://dxdy-04.korotkov.co.uk/f/3/3/7/337e516044e98d9ea80b70bbf79b878c82.png)
,
![$\lbrace a, c\rbrace$ $\lbrace a, c\rbrace$](https://dxdy-02.korotkov.co.uk/f/9/c/6/9c6038fe3991c59e1e87229e7e130a2d82.png)
и
![$\lbrace b, c\rbrace$ $\lbrace b, c\rbrace$](https://dxdy-02.korotkov.co.uk/f/d/1/6/d163366da0a222f007da051459c7f38f82.png)
-- эти двухэлементные множества являются всеми подмножествами трехэлементного множества
![$\lbrace a, b, c\rbrace$ $\lbrace a, b, c\rbrace$](https://dxdy-04.korotkov.co.uk/f/f/8/6/f8624c99c0eaa4498d1b9b15f88b409782.png)
.
А за пятнадцать ходов точно получится, потому что, какое бы ни взять трехэлементное подмножество множества
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
, все его двухэлементные подмножества есть среди всех (пятнадцати) двухэлементных подмножеств множества
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
.
(В множестве из шести элементов всего имеется
![$15$ $15$](https://dxdy-04.korotkov.co.uk/f/3/2/1/321d40fbe58f2e8c27e9964b658fbf6282.png)
пар:
![$$\binom {6}{2}=\frac {6!}{2!(6-2)!}=15.$$ $$\binom {6}{2}=\frac {6!}{2!(6-2)!}=15.$$](https://dxdy-04.korotkov.co.uk/f/7/0/c/70cb1d6ba4d5f1ae7667b5d6de1ddbf082.png)
)