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

[Vladimir Pliassov]

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

[mihaild]

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

Если удастся это доказать, то и все утверждение будет доказано, правильно?

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

[Vladimir Pliassov]

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

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

Спасибо за картинку, благодаря ей и Вашему замечанию я увидел свою ошибку, я написал, что если к $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$ -- то образуется либо две, либо три тройки попарно знакомых. На самом деле образуется не либо две, либо три тройки, а точно три.

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

тройки попарно незнакомых может не быть уже при меньшем количестве пар знакомых.

Правда.

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

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

Но нет сомнения в том, она соберется, ведь так? К доказательству этого можно вернуться позже, а пока что я буду исходить из того, что при соотношении числа пар знакомых к числу пар незнакомых $9/6, 10/5, 11/4$ и т. д. условия задачи выполняются.

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

Рассмотрим соотношение $8/7$.

Сначала возьмем соотношение $9/6$, которое уже подробно рассматривали:

непересекающиеся тройки -- пусть это будут $\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$ пар будут парами знакомых между собой.

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

4. А вот если пар знакомых меньше 9, то совсем непонятно.
Пункт 1 надо обосновать, и что-то сказать в п. 4.

Теперь, чтобы получить соотношение $8/7$, переведем произвольную пару из множества пар знакомых -- пусть это будет $\lbrace a, 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$, которые являются подмножествами изначально выбранных непересекающихся троек $\lbrace a, d, e\rbrace$ и $\lbrace b, c, f\rbrace$, продолжают оставаться в множестве пар незнакомых.

Отметим, что, как бы мы ни разбили множество всех $15$ пар на $9$ и $6$, мы можем подобрать такие две непересекающиеся тройки, что перевод одной пары из множества пар знакомых в множество пар незнакомых никак не повлияет на то, что среди незнакомых есть две полные тройки.

Таким образом, при соотношении $8/7$ условие задачи выполняется, то есть оно выполняется при любом соотношении.

[mihaild]

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

[Vladimir Pliassov]

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

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

В предыдущем посте я написал:

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

как бы мы ни разбили множество всех $15$ пар на $9$ и $6$, мы можем подобрать такие две непересекающиеся тройки, что перевод одной пары из множества пар знакомых в множество пар незнакомых никак не повлияет на то, что среди незнакомых есть две полные тройки.

Но это неверно: подобрать две непересекающиеся тройки из шести пар можно, только если эти шесть пар являются подмножествами этих троек.

Тем не менее, будем исходить из описанной системы, основывающейся на двух непересекающихся тройках:

непересекающиеся тройки -- пусть это будут $\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$, которые являются подмножествами выбранных троек;

оставшиеся $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$ пар будут парами знакомых между собой.

Теперь будем совершать обмены между шестью парами незнакомых и девятью парами знакомых так, чтобы соотношение между числом пар незнакомых и числом пар знакомых оставалось $6/9$.

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

Если перевести две пары:

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

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

Если перевести четыре пары:

1) так, что одно из множеств $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$, $\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ окажется среди знакомых, то будет полная тройка знакомых;

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

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

Тут я уже понял, что доказать это таким путем, конечно, можно, потому что множество всех комбинаций конечно, но надо перебрать все возможные варианты, а это лучше делать с помощью вычислительной машины. (Надо ведь перебрать также и все варианты не только для соотношения $9/6$, но и для всех остальных соотношений.)

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

это вопрос о так называемых числах Рамсея: число Рамсея $R(x, y)$ - это минимальный размер группы, в которой заведомо найдется либо $x$ попарно знакомых, либо $y$ попарно незнакомых людей. И исходная задача в этих терминах формулируется как "доказать, что $R(x, y) \leq 6$".
При этом известно, что $R(5, 3) = 14$, так что среди $8$ людей может не найтись ни $5$ попарно знакомых, ни $3$ попарно незнакомых. Но это довольно сложная наука. И например значение $R(5, 5)$ или $R(4, 6)$ неизвестны (хотя известно, что $R(x, y)$ конечно для любых $x$ и $y$).

Мне кажется, что можно было бы попробовать доказать таким путем, что $R(5, 5)=10$, то есть взять множество из десяти элементов, две непересекающиеся пятерки из него, все пары, которые являются подмножествами этих пятерок и т.д.. Но без вычислительной машины (или без феноменального живого вычислителя), по-моему, не обойтись.

[mihaild]

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

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

И если перебирать все варианты, то проще уж сразу перебирать варианты знакомств. Их всего-то $32768$, даже если не отождествлять получающиеся разными перестановками.

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

Мне кажется, что можно было бы попробовать доказать таким путем, что $R(5, 5)=10$, то есть взять множество из десяти элементов, две непересекающиеся пятерки из него, все пары, которые являются подмножествами этих пятерок и т.д.. Но без вычислительной машины (или без феноменального живого вычислителя), по-моему, не обойтись.

[quote="Эрдёш"]Если инопланетяне вторглись на Землю и угрожают уничтожить ее через год, если человечество не сможет найти число Рамсея для пяти красных и пяти синих. Мы могли бы мобилизовать лучшие умы и самые быстродействующие компьютеры, и тогда в течение года мы, возможно, сумели бы найти искомое значение. Однако если бы инопланетяне потребовали от нас найти число Рамсея для шести красных и шести синих, то у нас не осталось бы иного выбора, как нанести упреждающий удар.

[Geen]

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

доказать таким путем, что $R(5, 5)=10$,

Возможно, таким путём Вы это и сможете "доказать", но вот только известно, что $R(5,5)\ge43$

[Vladimir Pliassov]

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

И если перебирать все варианты, то проще уж сразу перебирать варианты знакомств. Их всего-то $32768$, даже если не отождествлять получающиеся разными перестановками.

Но ведь это все равно было бы доказательство, даже если бы пришлось перебрать $32768$ вариантов? А если за основу доказательства взять то, что изображено на картинке
то есть то, что я предлагаю, то вариантов было бы меньше: не надо было бы переводить из пар знакомых в пары незнакомых ни все шесть пар, ни пять, ни одну пару, ни две пары по одной из каждого множества $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$, $\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$, возможно, нашлись бы еще облегчения работы. (То есть, как я понимаю, перебирать все варианты знакомств это не проще.)

За сколько времени вычислительная машина могла бы перебрать $32768$ вариантов?

Хотя, разумеется, это было бы не такое изящное доказательство как вот это.

А есть ли еще доказательства? Или известно только одно (не считая перебора вариантов)?

Geen в сообщении #1579053 писал(а):

Возможно, таким путём Вы это и сможете "доказать", но вот только известно, что $R(5,5)\ge43$

вот здесь сказано, что $R(5,5)=43$, правда, это Хабр.

Можно ли это проверить на вычислительной машине? Ведь $43$ это, как будто, не очень большое число? Или все равно будет слишком много операций для современных машин?

[mihaild]

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

Но ведь это все равно было бы доказательство, даже если бы пришлось перебрать $32768$ вариантов?

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

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

То есть, как я понимаю, перебирать все варианты знакомств это не проще.

Зато думать не надо. А какой именно вариант перебора предлагаете Вы - я пока не очень понимаю.
Ну и если отождествить комбинации, отличающиеся перестановкой вершин, то разных конфигураций всего-то 156.

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

За сколько времени вычислительная машина могла бы перебрать $32768$ вариантов?

Думаю за миллисекунду хорошо оптимизированный код справится.

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

вот здесь сказано, что $R(5,5)=43$, правда, это Хабр.

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

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

Можно ли это проверить на вычислительной машине?

Проверить конкретный граф несложно (пока число знакомых/незнакомых небольшое, так-то в графе из 100000 вершин найти группу из 1000 знакомых, даже если она там есть, сложно), и известен граф с 42 вершинами, в котором нет ни пятерки знакомых, ни пятерки незнакомых. Проблема в том, что для наивного доказательства нам нужно проверить не один граф на предмет наличия в нём пятерки знакомых/незнакомых, а все графы из 43 вершин. А их примерно $10^{219}$.
Собственно оценка $R(5, 5) \leq 48$ тоже была получена перебором, но там сначала сложным рассуждением доказали, что в любой конфигурации из 49 человек, кроме двух триллионов конфигураци определенного вида, наверняка есть либо пятерка знакомых, либо пятерка незнакомых. А потом перебором проверили эти два триллиона.

[Vladimir Pliassov]

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

А какой именно вариант перебора предлагаете Вы - я пока не очень понимаю.

Я там неправильно написал:

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

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

надо было: "не надо было бы переводить из пар незнакомых в пары знакомых ни все шесть пар ..."

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

[Vladimir Pliassov]

Еще одна попытка.

Пусть все шестеро из $X=\lbrace a, b, c, d, e, f\rbrace$ попарно знакомы, то есть имеется $15$ пар и $20$ троек попарно знакомых и при этом $0$ пар и $0$ троек попарно незнакомых

(последние четыре слова могут показаться странными, ведь если все шестеро попарно знакомы, то все остальные незнакомы, то есть имеется $15$ пар и $20$ троек попарно незнакомых, но я имею в виду полный граф двуцветной окраски, в котором все ребра одного цвета, а ребер другого цвета нет совсем).

Будем переводить по одной паре из знакомых в незнакомые так, чтобы при переводе каждой пары разрушить как можно больше полных троек знакомых.

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

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

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

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

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

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

Обратим внимание, что переведенные пары являются подмножествами (непересекающихся) троек $\lbrace a, d, e\rbrace$ и $\lbrace b, c, f\rbrace$.

Таким образом, разрушились все $20$ полных троек знакомых, но при этом возникло две полные тройки незнакомых, то есть тройки $\lbrace a, d, e\rbrace$ и $\lbrace b, c, f\rbrace$.

[Vladimir Pliassov]

Прошу следующие слова из предыдущего поста:

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

(последние четыре слова могут показаться странными, ведь если все шестеро попарно знакомы, то все остальные незнакомы, то есть имеется $15$ пар и $20$ троек попарно незнакомых, но я имею в виду полный граф двуцветной окраски, в котором все ребра одного цвета, а ребер другого цвета нет совсем).

не принимать во внимание, здесь на меня нашло затмение.

[mihaild]

А кто вам сказал, что жадное удаление (т.е. удаление на каждом шаге ребра, разрушающего максимальное число троек) дает минимальное число ребер, разрушающее все тройки? Ну и вдруг есть другой способ выбрать 6 ребер, разрушающий все тройки знакомых, но не дающий ни одной тройки попарно незнакомых?

[Vladimir Pliassov]

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

А кто вам сказал, что жадное удаление (т.е. удаление на каждом шаге ребра, разрушающего максимальное число троек) дает минимальное число ребер, разрушающее все тройки?

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

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

Ну и вдруг есть другой способ выбрать 6 ребер, разрушающий все тройки знакомых, но не дающий ни одной тройки попарно незнакомых?

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

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

[mihaild]

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

При этом может быть только две пары, разрушающие по четыре тройки

Это же неправда. После изъятия $ad$ и $cf$ пара $be$ разрушает 4 тройки.

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

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

Это нужно четко сформулировать и доказать. Удаляемая пара будет принадлежать нескольким тройкам, в том числе, возможно, некоторым разрушенным. Но никто не сказал, что не получится разрушить все тройки, не разрушив ни одну из них до конца.