Вопрос школьника
Ответь развернуто и подробно на вопрос — Доведіть, що в будь-якій компанії із 6 осіб знайдеться трос попарно знайомих або троє попарно незнайомих.
Ответ от учителя
Для розв’язання цієї задачі використаємо теорію графів. Представимо кожну особу у компанії як вершину графа, а знайомство між двома особами як ребро, що з’єднує ці вершини. Тоді наша задача полягає в тому, щоб знайти трос, який з’єднує дві або три вершини графа.
Розглянемо два випадки:
1. Якщо у графі є хоча б одна вершина зі ступенем не менше 3, то ця вершина з’єднана з трьома і більше інших вершинами. Одна з цих вершин може бути з’єднана зі ступенем не менше 2, а інші дві вершини можуть бути з’єднані між собою. Таким чином, ми знайшли трос, який з’єднує троє попарно незнайомих осіб.
2. Якщо у графі кожна вершина має ступінь не більше 2, то кількість ребер не більше 15 (6 вершин і кожна з них може бути з’єднана з двома іншими вершинами). З іншого боку, кожен трос з’єднує дві вершини, тому кількість тросів не більше 15. Отже, за принципом Дирихле, у графі знайдеться трос, який з’єднує дві попарно знайомі особи.
Таким чином, ми довели, що в будь-якій компанії із 6 осіб знайдеться трос попарно знайомих або троє попарно незнайомих.
