Олимпиадная задача по теории графов для 8-11 классов от Гулько С.
В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону.
Разобрать решение
Докажем утверждение индукцией по числу n жителей города. База (n ≤ 2) очевидна.
Шаг индукции. Пусть n ≥ 3, а m – общее количество звонков в этот день. По условию m ≤ n, поэтому найдётся житель A, разговаривавший не более чем с двумя жителями (в противном случае m ≥ 3n/2 > n). По предположению индукции, всех жителей города, кроме A, можно разбить на три группы так, чтобы выполнялось условие задачи. Житель A не разговаривал с жителями, входящими в одну из групп, поэтому его можно добавить к этой группе, сохранив в силе требуемое утверждение.
Обсуждение
0Комментариев пока нет.