В большом вольере живёт сто попугайчиков. В некоторый момент оказалось, что каждый из них за свою жизнь клюнул ровно пять других попугайчиков из этого вольера. Докажите, что можно выпустить на волю десять таких попугайчиков, что никто из них друг друга не клевал.
В большом вольере живёт сто попугайчиков. В некоторый момент оказалось, что каждый из них за свою жизнь клюнул ровно пять других попугайчиков из этого вольера. Докажите, что можно выпустить на волю десять таких попугайчиков, что никто из них друг друга не клевал.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Представим ситуацию следующим образом: каждый попугайчик клевал (был клеван) ровно 5 других попугайчиков. Рассмотрим граф, где вершинами будут попугаи, а рёбра будут соединять тех попугаев, которые клевали друг друга.
Заметим, что сумма степеней вершин в таком графе будет равна удвоенному числу рёбер (поскольку каждое ребро соответствует двум попугаям). Таким образом, сумма степеней вершин в данном графе равна 200.
Поскольку каждый попугай клевал ровно 5 других попугаев, его степень в графе равна 5. Таким образом, сумма степеней вершин в графе равна 5 * 100 = 500. Но также мы знаем, что сумма степеней вершин равна 200. Произошло противоречие.
Это означает, что в таком графе нельзя, чтобы каждый попугай клевал ровно 5 других попугаев. Таким образом, мы можем выбрать 10 попугайчиков из этих ста, которые не клевали друг друга.