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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle R(3,3:2)=6.}$

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

• Party Acquaintances at cut-the-knot (requires Java)