Порозууміння 6 делегатів

На всесвітньому фестивалі молоді зустрілись 6 делегатів. Виявилось, що серед будь-яких трьох з них двоє можуть порозумітися між собою якоюсь мовою. Доведіть, що тоді найдеться 3 делегатів, кожен з яких може порозумітись з кожним.

Відповідь:

[hidepost]Хай делегат А може поговорити з трьома іншими делегатами, назвемо їх В, С, D. Серед останніх можливо двоє також можуть порозумітися між собою, скажімо, В і С. Тоді А, В, С – шукана трійка. Якщо А може поговорити не більше, ніж з двома іншими делегатами, то знайдуться три делегати Е, F, G, ні з одним з яких А не може говорити. Тоді Е, F, G утворюють шукану трійку.[/hidepost]