Теорема про друзів і незнайомців

Теорема про друзів і незнайомців є математичною теоремою у області математики з назвою теорія Ремзі.

Всі 78 можливих графів друзів-незнайомців з 6 вершинами. Для кожного графу червоні/сині вершини показують зразок трійки спільних друзів/незнайомців.

Твердження

Припустимо, що на вечірці є група з шести осіб. Розглянемо будь-яких двох з них. Вони можуть зустрінутися вперше — у цьому випадку ми будемо називати їх незнайомими; або вони могли зустрічатися раніше — у цьому випадку ми будемо називати їх знайомими. Теорема говорить: 

У будь-якій групі з шести осіб або принаймні три з них (попарно) незнайомі або принаймні три з них (попарно) знайомими.

Перетворення до графічно-теоретичного оформлення

Доказ теореми не вимагає нічого, крім триступеневої логіки. Зручно викласти цю проблему на графічно-теоретичну мову.

Припустимо, що граф, який має 6 вершин, і кожна пара (окремі) вершини об'єднана ребром. Такий граф називається повним графіком (тому, що не може бути більше країв). Повний графік на $n$ вершинах позначається символом $K_{n}$.

Тепер візьміть  $K_{6}$. У ньому всього 15 країв. Нехай 6 вершин позначають 6 людей на нашій вечірці. Нехай краї будуть пофарбовані червоним або синім кольором залежно від того, чи обидві людини, представлені вершинами, з'єднані краєм, є взаємними незнайомими або взаємними знайомими, відповідно.

Незалежно від того, як ви забарвити 15 ребер $K_{6}$ з червоним і синім кольором, ви не можете уникнути наявності червоного трикутника, тобто трикутника, з усіх трьох сторін червоних, що представляють три пари взаємних незнайомців, або синій трикутник, що представляє три пари взаємних знайомих. Іншими словами, будь-які кольори, які ви використовуєте, завжди буде щонайменше один монохроматичний трикутник (тобто трикутник, у якого всі ребра мають однаковий колір).

Доказ

Виберіть будь-яку вершину; назвіть її P. Існує п'ять ребер, що йдуть від вершини P. Кожен з них пофарбований синім або червоним кольором. Принцип Діріхле  говорить, що принаймні три з них повинні бути одного кольору;  бо якщо в ньому менше трьох ребер одного кольору, наприклад червоного, то є щонайменше три сині.

Нехай А, В, С — інші кінці цих трьох ребер, мають однаковий колір, скажімо, блакитний. Якщо будь-який з AB, BC, CA є синім, то це ребро разом з обома ребрами від P утворює синій трикутник. Якщо жодна з AB, BC, CA не є синьою, тоді всі три краю червоні, а ми маємо червоний трикутник, а саме ABC.

Насправді, можна знайти два монохроматичні трикутники.

Теорія Ремзі

Виняткова простота цього аргументу, й робить теорему привабливою. У 1930 році у статті «Про проблему в формальній логіці» Френк П. Ремзі показав дуже загальну теорему (тепер відомої як теорема Ремзі), з якої ця теорема є простим випадком. Ця теорія Ремзі утворює основу галузі, відомої як теорія Ремзі в комбінаториці.

Обмеження теореми

 2-забарвлення K₅ без монохроматичного K₃

Висновок до теореми не виконується, якщо замінити групу шести людей групою менше ніж шість. Це стає очевидним, якщо розглянути розфарбування графу K₅ у червоний та синій кольори, так, що буде відсутній трикутник, ребра якого будуть одним кольором. Для цього зобразимо K₅ як п'ятикутник навколо зірки (пентаграми). Ребра п'ятикутника будуть червоними, а ребра зірки — синіми. Отже, 6 є найменшим числом, при якому виконується висновок теореми. У теорії Ремзі цей факт позначають так:

$R(3,3:2)=6.$

Список літератури

• V. Krishnamurthy. Culture, Excitement and Relevance of Mathematics, Wiley Eastern, 1990. ISBN 81-224-0272-0.

Посилання

• Party Acquaintances [Архівовано 22 грудня 2017 у Wayback Machine.] at cut-the-knot (requires Java)