Страница 56 номер 71, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
На лавке сидят семеро ребят. Каждый имеет среди остальных не менее трёх братьев. Докажите, что все семеро — братья.
Ребята — вершины, ребро соединяет тех двоих, которые приходятся друг другу братьями; степень каждой вершины не меньше 3.
Если первый — брат второму, то и второй — первому, а если первый и второй — братья и второй и третий — братья, то первый и третий тоже братья. Поэтому ребята разбиваются на группы: внутри группы каждые двое — братья, а ребята из разных групп братьями не приходятся, и каждый попадает ровно в одну группу.
У любого из семерых не меньше трёх братьев, и все они в его группе, значит, в группе не меньше \(3 + 1 = 4\) человек.
На две такие группы понадобилось бы не меньше \(4 + 4 = 8\) ребят, а их 7, и \(8 > 7\). Значит, группа только одна и в неё входят все семеро.
Ответ: все семеро — братья: каждая группа братьев содержит не меньше четырёх человек, а на две такие группы понадобилось бы не меньше восьми ребят, тогда как их семеро.
На лавке сидят семеро ребят. Каждый имеет среди остальных не менее трёх братьев. Докажите, что все семеро — братья.
Сопоставим каждому из ребят вершину графа и соединим ребром тех двоих, которые приходятся друг другу братьями. По условию из каждой вершины выходит не менее трёх рёбер, то есть степень каждой вершины не меньше 3.
Родство устроено так: если первый — брат второму, то и второй — брат первому; а если первый и второй — братья и второй и третий — братья, то первый и третий тоже братья. Поэтому все ребята разбиваются на группы: внутри одной группы каждые двое — братья, а ребята из разных групп братьями не приходятся. Каждый попадает ровно в одну группу — группу своих братьев.
Возьмём любого из семерых. У него не меньше трёх братьев, и все они лежат в его группе, значит, в этой группе не меньше \(3 + 1 = 4\) человек. То же верно для каждого из семерых: каждая группа содержит не меньше 4 человек.
Если бы групп было хотя бы две, ребят в них вместе оказалось бы не меньше \(4 + 4 = 8\). Но ребят всего 7, и \(8 > 7\). Значит, группа только одна, и в неё входят все семеро.
Ответ: все семеро — братья: каждая группа братьев содержит не меньше четырёх человек, а на две такие группы понадобилось бы не меньше восьми ребят, тогда как их семеро.
