Вопрос:

127. На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?

Смотреть решения всех заданий с листа

Ответ:

Давайте представим эту ситуацию как граф, где вершины - это ученые, а ребра - отношения знакомства между ними. У нас есть 5 ученых, каждый из которых знаком с 3 другими, и остальные ученые, каждый из которых знаком с 4 другими. Если мы будем суммировать степени всех вершин (то есть количество знакомых у каждого ученого), то согласно теореме о рукопожатиях эта сумма должна быть четной. Предположим, что всего ученых n, тогда 5 из них имеют степень 3, а (n-5) имеют степень 4. Сумма степеней равна: `5 * 3 + (n-5) * 4 = 15 + 4n - 20 = 4n - 5`. Чтобы эта сумма была четной (по теореме о рукопожатиях), значение `4n-5` должно быть четным числом. Однако `4n` всегда четное, а `4n - 5` всегда нечетное. Таким образом, сумма степеней вершин не может быть четной, а значит такая ситуация невозможна. **Ответ:** Нет, такая ситуация невозможна, так как общее количество знакомств (сумма степеней вершин) должно быть четным числом, а в данной ситуации оно получается нечетным.
ГДЗ по фото 📸
Подать жалобу Правообладателю

Похожие