Страница 54 номер 82, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Докажите, что среди них найдутся четверо, имеющих одинаковое число знакомых.
Сопоставим каждому ученику вершину; ребро соединяет двух учеников, которые знакомы друг с другом (знакомство взаимно). В графе 102 вершины, и степень вершины равна числу знакомых соответствующего ученика.
Степень каждой вершины не меньше 68, а больше 101 она быть не может, потому что всего учеников 102. Значит, степени принимают одно из \(101 - 68 + 1 = 34\) значений.
Предположим противное: никакие четверо учеников не имеют одинакового числа знакомых. Тогда каждое из 34 значений встречается не более чем у трёх вершин, и всего вершин не больше \(34 \cdot 3 = 102\). Но вершин ровно 102, поэтому каждое из 34 значений встречается ровно у трёх вершин.
Нечётные числа от 68 до 101 — это \(69,\ 71,\ \ldots,\ 101\), и их \((101 - 69) : 2 + 1 = 17\). Значит, вершин нечётной степени ровно \(17 \cdot 3 = 51\).
Но число вершин нечётной степени чётно: сумма степеней всех вершин равна удвоенному числу рёбер и потому чётна, а при нечётном числе таких вершин она была бы нечётной. Число 51 нечётно — получилось противоречие.
Следовательно, предположение неверно и какие-то четверо учеников имеют одинаковое число знакомых.
Ответ: среди 102 учеников найдутся четверо с одинаковым числом знакомых.
Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Докажите, что среди них найдутся четверо, имеющих одинаковое число знакомых.
Сопоставим каждому ученику вершину; ребро соединяет двух учеников, которые знакомы друг с другом (знакомство считаем взаимным). В этом графе 102 вершины, и степень каждой вершины равна числу знакомых соответствующего ученика.
Каждый ученик знаком не менее чем с 68 другими, поэтому степень каждой вершины не меньше 68. Всего учеников 102, поэтому знакомых у одного ученика не больше 101, то есть степень каждой вершины не больше 101.
Значит, степени вершин принимают только значения от 68 до 101, а таких значений \(101 - 68 + 1 = 34\).
Предположим противное: пусть никакие четверо учеников не имеют одинакового числа знакомых. Тогда каждое из 34 значений встречается не более чем у трёх вершин, и всего вершин не больше \(34 \cdot 3 = 102\). Но вершин ровно 102, поэтому каждое из 34 значений встречается ровно у трёх вершин.
Среди чисел от 68 до 101 нечётные — это \(69,\ 71,\ \ldots,\ 101\), и их \((101 - 69) : 2 + 1 = 17\). Значит, вершин нечётной степени ровно \(17 \cdot 3 = 51\).
Но число вершин нечётной степени чётно: сумма степеней всех вершин равна удвоенному числу рёбер и потому чётна, а при нечётном числе вершин нечётной степени она была бы нечётной. Число 51 нечётно — получилось противоречие.
Следовательно, предположение неверно и какие-то четверо учеников имеют одинаковое число знакомых.
Ответ: среди 102 учеников найдутся четверо с одинаковым числом знакомых.
