Корректность доказательства (теория множеств)

[alkoln]

Помогите, пожалуйста, проверить корректность доказательства для следующей задачи:

"Среди участников похода из любых четырех как минимум один знаком с тремя другими. Докажите, что каждый участник похода, кроме максимум трех, знаком со всеми остальными."

Попытался доказать следующим образом:

От противного. Пусть $n \geqslant 4$ — количество участников, не знакомых хотя бы с одним другим, а $P$ - множество таких участников. Тогда можем составить четвёрку участников следующим способом:
1) возьмём любых двух участников $x_1, x_2 \in P$ таких, что $x_1$ не знаком с $x_2$;
2) возьмём любых двух участников $x_3$, $x_4$ \in P;
3) если $x_4$ знаком одновременно с $x_1, x_2, x_3$, то заменим участника $x_3$ на другого: $x_3=x'_3$ такого, что $x'_3$ не знаком с $x_4$.

Таким образом, четвёрка $Q=\{x_1,x_2,x_3,x_4\}$ не содержит ни одного участника, знакомого с тремя остальными, а это противоречит условию задачи.
Ч.Т.Д.

Я видел другое решение этой задачи на основе теории графов, но мне хотелось бы понять, может ли данный способ считаться полноценным и достаточно строгим доказательством. Заранее спасибо!

[12d3]

alkoln в сообщении #1125731 писал(а):

если $x_4$ знаком одновременно с $x_1, x_2, x_3$, то заменим участника $x_3$ на другого: $x_3=x'_3$ такого, что $x'_3$ не знаком с $x_4$.

Вот здесь пробел. Не доказано, что существует такой $x_3'$, который не знаком с $x_4$.

[grizzly]

12d3 в сообщении #1125735 писал(а):

Не доказано, что существует такой $x_3'$, который не знаком с $x_4$.

Это очевидно, поскольку $x_4\in P$. Но уточнить это стоило. А так всё нормально, только записано в конце не очень аккуратно.

[12d3]

grizzly в сообщении #1125739 писал(а):

Это очевидно, поскольку $x_4\in P$.

А вдруг единственный незнакомец - это $x_1$ или $x_2$. Все-таки, пару фраз в доказательство надо добавить.

[grizzly]

12d3 в сообщении #1125740 писал(а):

А вдруг единственный незнакомец - это $x_1$ или $x_2$.

Будьте внимательней :)

alkoln в сообщении #1125731 писал(а):

3) если $x_4$ знаком одновременно с $x_1, x_2, x_3$, то заменим участника $x_3$ на другого

[12d3]

grizzly в сообщении #1125741 писал(а):

Будьте внимательней :)

Согласен, был невнимателен.
Но тем не менее, случай, когда $x_3$ знаком со всеми тремя, а $x_4$ с кем-то незнаком, не рассмотрен явно. Нужно повторить рассуждение из пункта 3 и для $x_3$.

[grizzly]

12d3 в сообщении #1125742 писал(а):

Нужно повторить рассуждение из пункта 3 и для $x_3$.

Они равноправны -- достаточно просто рассматривать $x_4$ "не уменьшая общности" (хотя такие слова тоже нужно произносить).
Я согласен, что доказательство не выписано идеально чётко. Но по сути решение задачи правильное.

[mihaild]

12d3 в сообщении #1125742 писал(а):

Но тем не менее, случай, когда $x_3$ знаком со всеми тремя, а $x_4$ с кем-то незнаком, не рассмотрен явно. Нужно повторить рассуждение из пункта 3 и для $x_3$.

Этот случай невозможен, т.к. отношение знакомства симметрично.

[alkoln]

mihaild в сообщении #1125744 писал(а):

12d3 в сообщении #1125742 писал(а):

Но тем не менее, случай, когда $x_3$ знаком со всеми тремя, а $x_4$ с кем-то незнаком, не рассмотрен явно. Нужно повторить рассуждение из пункта 3 и для $x_3$.

Этот случай невозможен, т.к. отношение знакомства симметрично.

Всё-таки возможен. Например, если $x_4$ знаком одновременно с $x_3$ и $x_2$, а $x_3$ знаком одновременно с $x_4, x_2, x_1$. В таком случае условие пункта 3 формально не выполняется, хотя ситуация и является равноправной, как выше заметил grizzly.

Думаю, пункт 2 следует дополнить следующим образом:

2) возьмём любых двух участников $x_3, x_4 \in P$, принимая за $x_4$ того из них, который знаком с наибольшим количеством участников из $\{x_1,x_2\}$;

[grizzly]

alkoln
Вот здесь тоже поправьте заодно -- режет глаз после возможной замены $x_3$:

alkoln в сообщении #1125731 писал(а):

Таким образом, четвёрка $Q=\{x_1,x_2,x_3,x_4\}$

Скажите лучше словами: "приведенная четвёрка", например.

[alkoln]

grizzly в сообщении #1125769 писал(а):

alkoln
Вот здесь тоже поправьте заодно -- режет глаз после возможной замены $x_3$:

alkoln в сообщении #1125731 писал(а):

Таким образом, четвёрка $Q=\{x_1,x_2,x_3,x_4\}$

Скажите лучше словами: "приведенная четвёрка", например.

Прошу прощения. Это во мне ещё буянит программист, пока я погружаюсь в мир математики.
Спасибо вам, коллеги, за ценные замечания!