А если есть другие конфигруации с 9 знакомыми? А если есть конфигурация с 8 знакомыми, но такая, что при добавлении любой пары знакомых появляется тройка знакомых?
В предыдущем посте я написал:
как бы мы ни разбили множество всех
![$15$ $15$](https://dxdy-04.korotkov.co.uk/f/3/2/1/321d40fbe58f2e8c27e9964b658fbf6282.png)
пар на
![$9$ $9$](https://dxdy-01.korotkov.co.uk/f/4/3/8/4383b081cba8f285e7854426f9ea1e6d82.png)
и
![$6$ $6$](https://dxdy-04.korotkov.co.uk/f/3/2/7/327c36301dc71617dc7032f8ce30b23682.png)
, мы можем подобрать такие две непересекающиеся тройки, что перевод одной пары из множества пар знакомых в множество пар незнакомых никак не повлияет на то, что среди незнакомых есть две полные тройки.
Но это неверно: подобрать две непересекающиеся тройки из шести пар можно, только если эти шесть пар являются подмножествами этих троек.
Тем не менее, будем исходить из описанной системы, основывающейся на двух непересекающихся тройках:
непересекающиеся тройки -- пусть это будут
![$\lbrace a, d, e\rbrace$ $\lbrace a, d, e\rbrace$](https://dxdy-02.korotkov.co.uk/f/9/7/9/9794f7b91d8774ce7a90771af08ff3e282.png)
и
![$\lbrace b, c, f\rbrace$ $\lbrace b, c, f\rbrace$](https://dxdy-02.korotkov.co.uk/f/5/4/b/54be75424e0eac748a22b4f874d640c582.png)
(выбираются произвольно);
шесть пар
![$\lbrace a, d\rbrace$ $\lbrace a, d\rbrace$](https://dxdy-02.korotkov.co.uk/f/9/0/a/90a559228f52831b0585c15d42abb1c982.png)
,
![$\lbrace a, e\rbrace$ $\lbrace a, e\rbrace$](https://dxdy-02.korotkov.co.uk/f/d/1/6/d1624dc735de11399d25bcfe8e6502ed82.png)
,
![$\lbrace b, c\rbrace$ $\lbrace b, c\rbrace$](https://dxdy-02.korotkov.co.uk/f/d/1/6/d163366da0a222f007da051459c7f38f82.png)
,
![$\lbrace b, f\rbrace$ $\lbrace b, f\rbrace$](https://dxdy-04.korotkov.co.uk/f/3/0/4/3045e81dfee9032dcae48c7409ad935b82.png)
,
![$\lbrace d, e\rbrace$ $\lbrace d, e\rbrace$](https://dxdy-01.korotkov.co.uk/f/0/a/0/0a08065a282f2cd5c986e04e549a3afc82.png)
,
![$\lbrace c, f\rbrace$ $\lbrace c, f\rbrace$](https://dxdy-03.korotkov.co.uk/f/2/3/e/23ee181782d026d1987c2db39d3cd67482.png)
, которые являются подмножествами выбранных троек;
оставшиеся
![$9$ $9$](https://dxdy-01.korotkov.co.uk/f/4/3/8/4383b081cba8f285e7854426f9ea1e6d82.png)
пар (из
![$15$ $15$](https://dxdy-04.korotkov.co.uk/f/3/2/1/321d40fbe58f2e8c27e9964b658fbf6282.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 a, f\rbrace$ $\lbrace a, f\rbrace$](https://dxdy-03.korotkov.co.uk/f/2/5/d/25d3a6217fab2909576de0cdc9432bd882.png)
,
![$\lbrace b, d\rbrace$ $\lbrace b, d\rbrace$](https://dxdy-02.korotkov.co.uk/f/d/7/4/d747979f1bdfa5c8d99c26397d7da3a682.png)
,
![$\lbrace b, e\rbrace$ $\lbrace b, e\rbrace$](https://dxdy-02.korotkov.co.uk/f/1/f/8/1f8a9358d1a72aeb36a9b6112995837282.png)
,
![$\lbrace c, d\rbrace$ $\lbrace c, d\rbrace$](https://dxdy-02.korotkov.co.uk/f/d/a/7/da798620f1103a571ecb0c532afa093382.png)
,
![$\lbrace c, e\rbrace$ $\lbrace c, e\rbrace$](https://dxdy-04.korotkov.co.uk/f/f/b/4/fb47ed12aeb0e78cccdf0e0a4ca72a3a82.png)
,
![$\lbrace d, f\rbrace$ $\lbrace d, f\rbrace$](https://dxdy-04.korotkov.co.uk/f/7/1/b/71b3980492d22efa1ba4694003e8192982.png)
,
![$\lbrace e, f\rbrace$ $\lbrace e, f\rbrace$](https://dxdy-04.korotkov.co.uk/f/f/6/b/f6b8bd248c447e250788613ea0f3ef9f82.png)
;
каждая из оставшихся
![$18$ $18$](https://dxdy-02.korotkov.co.uk/f/1/5/d/15d851cfce799553cec908376fe8edd982.png)
троек представляется в виде объединения некоторых двух из оставшихся
![$9$ $9$](https://dxdy-01.korotkov.co.uk/f/4/3/8/4383b081cba8f285e7854426f9ea1e6d82.png)
пар:
![$$\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)$$ $$\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)$$](https://dxdy-02.korotkov.co.uk/f/9/4/7/947be16e4b94dd7aaaa69cab5dbbe9a682.png)
Пусть оставшиеся
![$9$ $9$](https://dxdy-01.korotkov.co.uk/f/4/3/8/4383b081cba8f285e7854426f9ea1e6d82.png)
пар будут парами знакомых между собой.
Теперь будем совершать обмены между шестью парами незнакомых и девятью парами знакомых так, чтобы соотношение между числом пар незнакомых и числом пар знакомых оставалось
![$6/9$ $6/9$](https://dxdy-04.korotkov.co.uk/f/7/7/4/774c34aed2497b36c6b736ab4bb879d882.png)
.
Если перевести из этих шести пар в эти девять пар все шесть пар, или одно из множеств
![$\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$ $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$](https://dxdy-04.korotkov.co.uk/f/3/5/6/35624fdb5448f50b2569518aecb358b582.png)
,
![$\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ $\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bda2b11669fb945e331098969a0157982.png)
, а также если перевести пять пар или только одну пару, то, независимо от того, какие пары будут по обмену переведены из множества пар незнакомых в множество пар знакомых, условие будет выполнено: или среди знакомых, или среди незнакомых будет по крайней мере одна полная тройка.
Если перевести две пары:
1) из одного из множеств
![$\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$ $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$](https://dxdy-04.korotkov.co.uk/f/3/5/6/35624fdb5448f50b2569518aecb358b582.png)
,
![$\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ $\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bda2b11669fb945e331098969a0157982.png)
, то останется нетронутым второе из этих множеств, и значит, полная тройка среди незнакомых сохранится;
2) по одной паре из каждого множества
![$\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$ $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$](https://dxdy-04.korotkov.co.uk/f/3/5/6/35624fdb5448f50b2569518aecb358b582.png)
,
![$\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ $\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bda2b11669fb945e331098969a0157982.png)
, то обе тройки незнакомых будут разрушены, но появится шесть троек знакомых, из которых придется, в худшем случае, вычесть четыре тройки при переводе двух пар из знакомых в незнакомые (в лучшем случае придется вычесть всего одну тройку), так что в результате обмена среди знакомых появится минимум две полные тройки.
Если перевести четыре пары:
1) так, что одно из множеств
![$\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$ $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$](https://dxdy-04.korotkov.co.uk/f/3/5/6/35624fdb5448f50b2569518aecb358b582.png)
,
![$\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ $\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bda2b11669fb945e331098969a0157982.png)
окажется среди знакомых, то будет полная тройка знакомых;
2) так, что по две пары будут взяты из каждого из множеств
![$\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$ $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace \big \rbrace$](https://dxdy-04.korotkov.co.uk/f/3/5/6/35624fdb5448f50b2569518aecb358b582.png)
,
![$\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ $\big \lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bda2b11669fb945e331098969a0157982.png)
, то обе полные тройки незнакомых будут разрушены, выигрыш для знакомых при обмене составит двенадцать пар, проигрыш будет в любом случае меньше, если быть точным, то ...
(Кстати, я и для трех обменянных пар тоже нашел, сколько в лучшем случае, сколько в худшем, но уже не стал писать.)
Тут я уже понял, что доказать это таким путем, конечно, можно, потому что множество всех комбинаций конечно, но надо перебрать все возможные варианты, а это лучше делать с помощью вычислительной машины. (Надо ведь перебрать также и все варианты не только для соотношения
![$9/6$ $9/6$](https://dxdy-03.korotkov.co.uk/f/a/c/a/aca1da8f3e801ccf976e4d69397126fd82.png)
, но и для всех остальных соотношений.)
это вопрос о так называемых числах Рамсея: число Рамсея
![$R(x, y)$ $R(x, y)$](https://dxdy-03.korotkov.co.uk/f/e/3/f/e3f81600837b04eef105d83dc06dcfc282.png)
- это минимальный размер группы, в которой заведомо найдется либо
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
попарно знакомых, либо
![$y$ $y$](https://dxdy-02.korotkov.co.uk/f/d/e/c/deceeaf6940a8c7a5a02373728002b0f82.png)
попарно незнакомых людей. И исходная задача в этих терминах формулируется как "доказать, что
![$R(x, y) \leq 6$ $R(x, y) \leq 6$](https://dxdy-01.korotkov.co.uk/f/4/8/7/487fd032cb661c966c9f88bf0f1c76f682.png)
".
При этом известно, что
![$R(5, 3) = 14$ $R(5, 3) = 14$](https://dxdy-04.korotkov.co.uk/f/f/9/2/f92339592a0799467cff5c15e3eefeb882.png)
, так что среди
![$8$ $8$](https://dxdy-01.korotkov.co.uk/f/0/0/5/005c128d6e551735fa5d938e44e7a61382.png)
людей может не найтись ни
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
попарно знакомых, ни
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
попарно незнакомых. Но это довольно сложная наука. И например значение
![$R(5, 5)$ $R(5, 5)$](https://dxdy-04.korotkov.co.uk/f/f/6/d/f6ddc1d65af122b6db367bf012c4eb6a82.png)
или
![$R(4, 6)$ $R(4, 6)$](https://dxdy-02.korotkov.co.uk/f/1/7/4/17428b771f0daa304253271ebef68eed82.png)
неизвестны (хотя известно, что
![$R(x, y)$ $R(x, y)$](https://dxdy-03.korotkov.co.uk/f/e/3/f/e3f81600837b04eef105d83dc06dcfc282.png)
конечно для любых
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
и
![$y$ $y$](https://dxdy-02.korotkov.co.uk/f/d/e/c/deceeaf6940a8c7a5a02373728002b0f82.png)
).
Мне кажется, что можно было бы попробовать доказать таким путем, что
![$R(5, 5)=10$ $R(5, 5)=10$](https://dxdy-01.korotkov.co.uk/f/4/0/c/40c9ccc14349fc17d0b68fc87a55172a82.png)
, то есть взять множество из десяти элементов, две непересекающиеся пятерки из него, все пары, которые являются подмножествами этих пятерок и т.д.. Но без вычислительной машины (или без феноменального живого вычислителя), по-моему, не обойтись.