Отношение эквивалентности

[Vladimir Pliassov]

Попробую еще раз. "Доказать, что среди любых $6$ людей есть либо $3$ попарно знакомых, либо $3$ попарно незнакомых".

То есть: либо среди любых $6$ человек есть $3$ попарно знакомых, либо -- если среди них не найдется $3$ попарно знакомых, -- среди них найдется $3$ попарно незнакомых.

Пусть среди них найдется $3$ попарно знакомых (то есть найдется либо $6$, либо $5$, либо $4$, либо $3$ попарно знакомых), тогда условие выполнено.

Теперь рассмотрим возможность, когда среди них не найдется $3$ попарно знакомых. Надо показать, что при этом найдется, по крайней мере, $3$ попарно незнакомых.

Если нет ни одной тройки попарно знакомых, значит, в каждой тройке найдется, по крайней мере, одна пара незнакомых между собой.

Обозначим множество наших шестерых человек как $X=\lbrace 1, 2, 3, 4, 5, 6 \rbrace$. Возьмем из него произвольную тройку, пусть это будет, например, тройка $\lbrace 2, 4, 5 \rbrace$, и пусть в ней парой незнакомых будет $\lbrace 2, 5 \rbrace$.

Возьмем все тройки, содержащие пару $\lbrace 2, 5 \rbrace$, и отметим, что она в них есть (это будет всего четыре тройки: $\lbrace1, 2, 5 \rbrace$, $\lbrace 3, 2, 5 \rbrace$, $\lbrace 4, 2, 5 \rbrace$ и $\lbrace 6, 2, 5 \rbrace$).

Теперь возьмем другую произвольную пару незнакомых и отметим все четыре тройки, в которых она есть, и так далее. Рано или поздно -- в лучшем случае на третьем ходу, в худшем случае на пятнадцатом ходу -- обнаружится тройка, в которой будет три пары незнакомых.

За три хода получится, если сразу взять пары $\lbrace a, b\rbrace$, $\lbrace a, c\rbrace$ и $\lbrace b, c\rbrace$ -- эти двухэлементные множества являются всеми подмножествами трехэлементного множества $\lbrace a, b, c\rbrace$.

А за пятнадцать ходов точно получится, потому что, какое бы ни взять трехэлементное подмножество множества $X$, все его двухэлементные подмножества есть среди всех (пятнадцати) двухэлементных подмножеств множества $X$.

(В множестве из шести элементов всего имеется $15$ пар:

$$\binom {6}{2}=\frac {6!}{2!(6-2)!}=15.$$

)

[Vladimir Pliassov]

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

К сожалению просто подсчетом числа ходов результат получить не удастся, т.к. за 8 ходов может не получиться, а гарантировать наличие 9 ходов нельзя (может быть что у нас 8 пар знакомых и 7 пар незнакомых).

По-моему, не может быть, чтобы не хватило пар незнакомых, потому что, если их не хватит, то, значит, хватит пар знакомых, чтобы нашлась тройка попарно знакомых (по тому же алгоритму), а мы рассматриваем возможность, когда не найдется тройки попарно знакомых.

[mihaild]

Vladimir Pliassov в сообщении #1578437 писал(а):

По-моему, не может быть, чтобы не хватило пар незнакомых, потому что, если их не хватит, то, значит, хватит пар знакомых, чтобы нашлась тройка попарно знакомых (по тому же алгоритму)

Это надо доказывать. И просто из количества пар не хватит, надо учитывать и другие связи между знакомыми и незнакомыми.
Потому что существуют:
1. Набор, в котором есть 8 пар знакомых и 7 пар незнакомых.
2. Набор, в котором есть 8 пар знакомых, но нет тройки попарно знакомых.
3. Набор, в котором есть 7 пар незнакомых, но нет тройки попарно незнакомых.

[Vladimir Pliassov]

krum в сообщении #1578416 писал(а):

:D

А я-то думал! Но вот решение: https://www.problems.ru/view_problem_de ... p?id=21995

[Vladimir Pliassov]

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

Это надо доказывать. И просто из количества пар не хватит, надо учитывать и другие связи между знакомыми и незнакомыми.
Потому что существуют:
1. Набор, в котором есть 8 пар знакомых и 7 пар незнакомых.
2. Набор, в котором есть 8 пар знакомых, но нет тройки попарно знакомых.
3. Набор, в котором есть 7 пар незнакомых, но нет тройки попарно незнакомых.

Вот перед нами шесть человек. Мы произвольно назначаем: "Вы незнакомы, вы знакомы, вы знакомы, вы незнакомы ..." -- как угодно, могут быть все незнакомы, или все знакомы, или три пары знакомых и двенадцать пар незнакомых и т. д..

У нас получается $p$ пар знакомых и $q$ пар незнакомых. Применяем алгоритм отдельно к парам $p$ и отдельно к парам $q$.

1) Либо хватает и пар $p$, и пар $q$, и тогда имеется не менее трех попарно знакомых и не менее трех попарно незнакомых;

2) либо пар $p$ хватает, а пар $q$ не хватает, и тогда имеется не менее трех попарно знакомых, а о незнакомых можно не думать;

3) либо пар $q$ хватает, а пар $p$ не хватает, и тогда имеется не менее трех попарно незнакомых, а о знакомых можно не думать;

4) ни тех, ни других не хватает -- об этом надо подумать, но ясно, что такого быть не может, потому что есть другие решения этой задачи.

[Vladimir Pliassov]

Будем сначала применять алгоритм к парам знакомых (хотя, разумеется, можно было бы сначала применять его к парам незнакомых).

При применении алгоритма максимальное число ходов, при котором может не обнаружиться тройка, в которой есть три выбранные пары, это девять, потому что

каждая из девяти пар входит в четыре тройки, всего троек $20$, для того, чтобы тройка не обнаружилась, в нее может войти максимум две пары. Поэтому -- при максимально продленном необнаружении -- по две пары входит в каждую из $18$ троек, при этом две тройки остаются полностью свободными.

[Эти две тройки не пересекаются (они вместе состоят из всех шести элементов множества $X$).]

Теперь можно выбрать: продолжить алгоритм для пар знакомых (если они еще остались) или начать алгоритм для пар незнакомых (если они есть в наличии).

Если сделать еще один (десятый) ход в алгоритме для пар знакомых (если, конечно, имеется еще одна пара знакомых -- все равно какая), то обнаружится тройка попарно знакомых (это будет первая тройка попарно знакомых, пока еще не было ни одной).

Если же вместо этого применить алгоритм к парам незнакомых, то (при наличии шести пар) обнаружится две тройки незнакомых, потому что после применения алгоритма для пар знакомых две тройки остались свободными, а оставшиеся шесть пар являются их подмножествами (это видно, если выписать все пары и тройки на листе бумаги).

Таким образом, условие задачи выполняется.

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

(Как сказано, можно делать наоборот: начинать не с пар знакомых, а с пар незнакомых, а затем переходить к парам знакомых.)

Я думаю, трудно без обозначений и иллюстраций понять то, что я написал, может быть, позже попытаюсь изложить все понятнее.

[mihaild]

Vladimir Pliassov в сообщении #1578505 писал(а):

Поэтому -- при максимально продленном необнаружении -- по две пары входит в каждую из $18$ троек, при этом две тройки остаются полностью свободными.

Вот это надо доказывать. Как то, что из 10 пар попарно знакомых точно найдется хотя бы одна тройка, так и то, что если попарно знакомых 9 пар и среди них нет ни одной тройки, то есть тройки попарно незнакомых.

[Vladimir Pliassov]

Пусть нам дано множество $X=\lbrace a, b, c, d, e, f\rbrace$ из шести человек. Тогда имеем множество $G$ всех его троек (трехэлементных подмножеств) $X^3_i\subset X$ (их всего $20$) и множество $H$ всех его пар (двухэлементных подмножеств) $X^2_j\subset X$ (их всего $15$).

(Каждая пара $X^2_j\subset X$ является подмножеством некоторых четырех из всех $20$ троек $X^3_i\subset X$.)

Выберем из $H$ девять пар

$\lbrace a, b\rbrace$, $\lbrace a, c\rbrace$, $\lbrace a, f\rbrace$, $\lbrace b, d\rbrace$, $\lbrace b, e\rbrace$, $\lbrace c, d\rbrace$, $\lbrace c, e\rbrace$, $\lbrace d, f\rbrace$, $\lbrace e, f\rbrace$, которые назначим парами знакомых между собой, таким образом, чтобы $18$ троек из $20$ представить в виде объединения этих двоек:

$$\begin {matrix} \lbrace a, b\rbrace \cup \lbrace a, c\rbrace\\ \lbrace a, b\rbrace \cup \lbrace b, d\rbrace\\ \lbrace a, b\rbrace \cup \lbrace b, e\rbrace\\ \lbrace a, b\rbrace \cup \lbrace a, f\rbrace\\ \lbrace a, c\rbrace \cup \lbrace c, d\rbrace\\ \lbrace a, c\rbrace \cup \lbrace c, e\rbrace \end {matrix} \;\;\;\;\; \begin {matrix} \lbrace a, c\rbrace \cup \lbrace a, f\rbrace\\ \lbrace a, f\rbrace \cup \lbrace d, f\rbrace\\ \lbrace a, f\rbrace \cup \lbrace e, f\rbrace\\ \lbrace b, d\rbrace \cup \lbrace c, d\rbrace\\ \lbrace b, e\rbrace \cup \lbrace c, e\rbrace\\ \lbrace b, e\rbrace \cup \lbrace b, d\rbrace \end {matrix}\;\;\;\;\; \begin {matrix} \lbrace b, d\rbrace \cup \lbrace d, f\rbrace\\ \lbrace b, e\rbrace \cup \lbrace e, f\rbrace\\ \lbrace c, d\rbrace \cup \lbrace c, e\rbrace\\ \lbrace c, d\rbrace \cup \lbrace d, f\rbrace\\ \lbrace c, e\rbrace \cup \lbrace e, f\rbrace\\ \lbrace d, f\rbrace \cup \lbrace e, f\rbrace \end {matrix}.$$

При этом две оставшиеся тройки $\lbrace a, d, e\rbrace$ и $\lbrace b, c, f\rbrace$ не имеют своими подмножествами ни одной из выбранных пар.

Если к выбранным девяти парам знакомых добавить еще одну пару -- все равно какую из оставшихся шести $\lbrace a, d\rbrace$, $\lbrace a, e\rbrace$, $\lbrace b, c\rbrace$, $\lbrace b, f\rbrace$, $\lbrace d, e\rbrace$, $\lbrace c, f\rbrace$ -- образуется либо две, либо три тройки попарно знакомых (можно проверить это непосредственно), таким образом,

если среди шестерых человек найдется 10 пар знакомых друг с другом, то точно найдется и тройка попарно знакомых.

Если же среди них не найдется 10 пар знакомых друг с другом, то найдется, во всяком случае, две тройки (например, $\lbrace a, d, e\rbrace$, $\lbrace b, c, f\rbrace$), которые не имеют своими подмножествами ни одной из пар знакомых, а среди пар незнакомых найдется три пары, объединение которых представляет собой одну из этих троек, то есть найдется, во всяком случае, одна тройка попарно незнакомых.

[mihaild]

Vladimir Pliassov в сообщении #1578593 писал(а):

таким образом,
если среди шестерых человек найдется 10 пар знакомых друг с другом, то точно найдется и тройка попарно знакомых

Нужно доказывать, что нельзя никаким другим способом выбрать 9 пар знакомых - вдруг можно выбрать 9 пар так, что и 10ю добавить получится?

Vladimir Pliassov в сообщении #1578593 писал(а):

Если же среди них не найдется 10 пар знакомых друг с другом, то найдется, во всяком случае, две тройки (например, $\lbrace a, d, e\rbrace$, $\lbrace b, c, f\rbrace$), которые не имеют своими подмножествами ни одной из пар знакомых

Аналогично - вдруг можно найти другой набор попарно знакомых людей, так, что тройки составить не получится?

Вообще, смотреть на примерах, что происходит, конечно, полезно. Но доказательство должно учитывать все возможные варианты.

[Vladimir Pliassov]

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

Нужно доказывать, что нельзя никаким другим способом выбрать 9 пар знакомых - вдруг можно выбрать 9 пар так, что и 10ю добавить получится?

По-моему, для этого доказательства необходимым и достаточным условием выбора 9 пар является условие, что найдутся $18$ троек (из всех $20$), таких, что каждая из них представляется в виде объединения двух из этих пар. (При этом, в частности, необходимо получается, что две тройки не имеют своими подмножествами ни одной из выбранных пар.)

[mihaild]

Vladimir Pliassov в сообщении #1578610 писал(а):

По-моему, для этого доказательства необходимым и достаточным условием выбора 9 пар является условие, что найдутся $18$ троек (из всех $20$), таких, что каждая из них представляется в виде объединения двух из этих пар.

Это тоже надо доказывать.
Т.е. Ваше доказательство имеет, получается, такую структуру:
1. Если пар знакомых ровно 9, и среди них нет тройки, то найдутся 18 троек с указанным свойством.
2. Если пар знакомых больше 9, и среди них нет полной тройки, то выберем 9 пар знакомых. По пункту 1 эти 9 пар имеют указанный вид, а к нему ничего добавить нельзя - значит, если пар знакомых больше 9, то есть полная тройка знакомых.
3. Если пар знакомых ровно 9, и среди них нет полной тройки, то они имеют ровно описанный вид, и есть полная тройка незнакомых.
4. А вот если пар знакомых меньше 9, то совсем непонятно.
Пункт 1 надо обосновать, и что-то сказать в п. 4.

[Vladimir Pliassov]

Можно зайти с другой стороны.

Возьмем две произвольные непересекающиеся тройки, например, $\lbrace a, d, e\rbrace$ и $\lbrace b, c, f\rbrace$, и все шесть пар, которые являются их подмножествами: $\lbrace a, d\rbrace$, $\lbrace a, e\rbrace$, $\lbrace b, c\rbrace$, $\lbrace b, f\rbrace$, $\lbrace d, e\rbrace$, $\lbrace c, f\rbrace$. Тогда каждая из оставшихся $18$ троек (из $20$) будет представлена в виде объединения некоторых двух из оставшихся $9$ пар $\lbrace a, b\rbrace$, $\lbrace a, c\rbrace$, $\lbrace a, f\rbrace$, $\lbrace b, d\rbrace$, $\lbrace b, e\rbrace$, $\lbrace c, d\rbrace$, $\lbrace c, e\rbrace$, $\lbrace d, f\rbrace$, $\lbrace e, f\rbrace$:

$$\begin {matrix} \lbrace a, b\rbrace \cup \lbrace a, c\rbrace\\ \lbrace a, b\rbrace \cup \lbrace b, d\rbrace\\ \lbrace a, b\rbrace \cup \lbrace b, e\rbrace\\ \lbrace a, b\rbrace \cup \lbrace a, f\rbrace\\ \lbrace a, c\rbrace \cup \lbrace c, d\rbrace\\ \lbrace a, c\rbrace \cup \lbrace c, e\rbrace \end {matrix} \;\;\;\;\; \begin {matrix} \lbrace a, c\rbrace \cup \lbrace a, f\rbrace\\ \lbrace a, f\rbrace \cup \lbrace d, f\rbrace\\ \lbrace a, f\rbrace \cup \lbrace e, f\rbrace\\ \lbrace b, d\rbrace \cup \lbrace c, d\rbrace\\ \lbrace b, e\rbrace \cup \lbrace c, e\rbrace\\ \lbrace b, e\rbrace \cup \lbrace b, d\rbrace \end {matrix}\;\;\;\;\; \begin {matrix} \lbrace b, d\rbrace \cup \lbrace d, f\rbrace\\ \lbrace b, e\rbrace \cup \lbrace e, f\rbrace\\ \lbrace c, d\rbrace \cup \lbrace c, e\rbrace\\ \lbrace c, d\rbrace \cup \lbrace d, f\rbrace\\ \lbrace c, e\rbrace \cup \lbrace e, f\rbrace\\ \lbrace d, f\rbrace \cup \lbrace e, f\rbrace \end {matrix}.$$

По-моему, это лучше, чем было:

"Выберем из $H$ девять пар таким образом, чтобы $18$ троек из $20$ представить в виде объединения этих пар.

При этом две оставшиеся тройки $\lbrace a, d, e\rbrace$ и $\lbrace b, c, f\rbrace$ не имеют своими подмножествами ни одной из выбранных пар."

Надо ли доказывать в новом варианте, что каждая из оставшихся $18$ троек (из $20$) будет представлена в виде объединения некоторых двух из оставшихся $9$ пар? Ведь это можно проверить непосредственно (составив список).

[mihaild]

Смотрите, Вы опять рассуждаете про конкретную конфигурацию. Т.е. Вы показали, что существует набор из 9 пар знакомых, такой что две тройки попарно незнакомы, а в остальных тройках один человек знаком с двумя другими. Если нарисовать картинку, то получится граф из задачи о домиках и колодцах.
Это рассуждение как раз из пунктов 2 и 3, и с ними у Вас всё хорошо. Проблема в том, что бывают и совершенно другие конфигурации, про которые Вы ничего не говорите, а это большая часть работы.
Примерно как в шахматной задаче: "белые начинают, черные ставят мат в три хода" - при её решении нельзя ограничиться рассмотрением какого-то конкретного первого хода белых, нужно рассмотреть все варианты.
С доказательством то же самое: Вам нужно показать, что, какую бы конфигурацию знакомств я Вам не принес, Вы сможете найти в ней нужную тройку. При этом обязательства приносить Вам только конфигурацию указанного Вами вида я на себя не брал.

[Vladimir Pliassov]

В предыдущем посте я ничего не доказывал, я только похвастался, что нашел новый взгляд на изучаемую структуру. Мне кажется, что этот новый взгляд гораздо естественнее старого и может помочь в доказательстве. Исходя из него,

непересекающиеся тройки -- пусть это будут $\lbrace a, d, e\rbrace$ и $\lbrace b, c, f\rbrace$ -- выбираются произвольно. Все остальное является следствием этого выбора:

шесть пар $\lbrace a, d\rbrace$, $\lbrace a, e\rbrace$, $\lbrace b, c\rbrace$, $\lbrace b, f\rbrace$, $\lbrace d, e\rbrace$, $\lbrace c, f\rbrace$, которые являются подмножествами выбранных троек;

оставшиеся $18$ троек (из $20$);

оставшиеся $9$ пар (из $15$) $\lbrace a, b\rbrace$, $\lbrace a, c\rbrace$, $\lbrace a, f\rbrace$, $\lbrace b, d\rbrace$, $\lbrace b, e\rbrace$, $\lbrace c, d\rbrace$, $\lbrace c, e\rbrace$, $\lbrace d, f\rbrace$, $\lbrace e, f\rbrace$;

то, что каждая из оставшихся $18$ троек представляется в виде объединения некоторых двух из оставшихся $9$ пар :

$$\begin {matrix} \lbrace a, b\rbrace \cup \lbrace a, c\rbrace,\\ \lbrace a, b\rbrace \cup \lbrace b, d\rbrace,\\ \lbrace a, b\rbrace \cup \lbrace b, e\rbrace,\\ \lbrace a, b\rbrace \cup \lbrace a, f\rbrace,\\ \lbrace a, c\rbrace \cup \lbrace c, d\rbrace,\\ \lbrace a, c\rbrace \cup \lbrace c, e\rbrace, \end {matrix} \;\;\;\;\; \begin {matrix} \lbrace a, c\rbrace \cup \lbrace a, f\rbrace,\\ \lbrace a, f\rbrace \cup \lbrace d, f\rbrace,\\ \lbrace a, f\rbrace \cup \lbrace e, f\rbrace,\\ \lbrace b, d\rbrace \cup \lbrace c, d\rbrace,\\ \lbrace b, e\rbrace \cup \lbrace c, e\rbrace,\\ \lbrace b, e\rbrace \cup \lbrace b, d\rbrace, \end {matrix}\;\;\;\;\; \begin {matrix} \lbrace b, d\rbrace \cup \lbrace d, f\rbrace,\\ \lbrace b, e\rbrace \cup \lbrace e, f\rbrace,\\ \lbrace c, d\rbrace \cup \lbrace c, e\rbrace,\\ \lbrace c, d\rbrace \cup \lbrace d, f\rbrace,\\ \lbrace c, e\rbrace \cup \lbrace e, f\rbrace,\\ \lbrace d, f\rbrace \cup \lbrace e, f\rbrace. \end {matrix} \eqno (1)$$

По-моему, все эти следствия очевидны и не требуют доказательств.

Пусть оставшиеся $9$ пар будут парами знакомых между собой.

Если к ним добавить еще одну пару -- все равно какую -- из шести пар $\lbrace a, d\rbrace$, $\lbrace a, e\rbrace$, $\lbrace b, c\rbrace$, $\lbrace b, f\rbrace$, $\lbrace d, e\rbrace$, $\lbrace c, f\rbrace$ -- то образуется либо две, либо три тройки попарно знакомых (можно проверить это непосредственно для каждой тройки и каждой пары).

Таким образом, если среди шестерых человек найдется 10 пар знакомых друг с другом, то точно найдется и тройка попарно знакомых.

Согласны ли Вы с этим?

[mihaild]

Да, это всё действительно очевидно (по модулю опечаток, на которые я не проверял).
Это очень хорошо видно на картинке:

Ребра тут - знакомства. Три вершины сверху и три вершины снизу - это тройки попарно незнакомых, в любой другой тройке (дву сверху одна снизу или одна сверху две снизу) та вершина что одна на своей стороне соединена с двумя другими. Добавление любого ребра даст нам три полных тройки (две соединенные им вершины и любая вершина с другой стороны).