ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 82: Изоморфные графы. Плоские и планарные графы
Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание — Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.
Сергей Мишин, методист по вероятности Шпаргача обновлено 11 сентября 2026
Условие
Докажите, что среди 102 учеников школы, каждый из которых знаком не менее чем с 68 другими, найдутся четверо с одинаковым числом знакомых.
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
Для решения задачи воспользуемся методом доказательства от противного и свойствами теории графов. Представим ситуацию в виде графа знакомств.
Шаг 1. Построение модели графа
Пусть вершины графа соответствуют ученикам школы. Тогда количество вершин n=102. Ребро между двумя вершинами означает, что соответствующие ученики знакомы друг с другом.
По условию каждый ученик знаком не менее чем с 68 другими. Это значит, что степень каждой вершины d(v) удовлетворяет неравенству:
d(v)≥68Максимально возможная степень вершины в простом графе с 102 вершинами равна 101 (ученик может быть знаком со всеми остальными). Таким образом, возможные значения степеней лежат в диапазоне от 68 до 101 включительно.
Шаг 2. Доказательство от противного
Предположим обратное утверждению задачи: пусть среди этих 102 учеников не найдутся четверо с одинаковым числом знакомых. То есть, для любого числа знакомых k существует не более трёх учеников, имеющих ровно k знакомых.
Рассмотрим множество возможных значений степеней: {68,69,…,101}. Количество таких значений равно 101-68+1=34.
Если предположение верно, то максимальное количество вершин, которые мы можем разместить, используя эти степени, при условии «не более 3 на каждую степень», составляет:
34×3=102Это совпадает с общим количеством учеников (102). Следовательно, чтобы уместить всех учеников без нарушения условия «не более трёх с одной степенью», должно выполняться строгое равенство: для каждого из 34 возможных значений степени должно существовать ровно три вершины такой степени.
Шаг 3. Анализ чётности степеней
Вспомним лемму о рукопожатиях: сумма степеней всех вершин графа равна удвоенному числу рёбер, то есть является чётным числом. Из этого следует важное следствие: количество вершин нечётной степени в любом графе всегда чётно .
Проверим это следствие для нашего случая. Выделим из диапазона степеней [68;101] все нечётные числа:
- Нечётные степени: 69,71,73,…,101.
- Чётные степени: 68,70,72,…,100.
Найдём количество нечётных значений в этом ряду. Это арифметическая прогрессия с первым членом 69, последним 101 и шагом 2. Количество членов m вычисляется по формуле:
m=101-69/2+1=32/2+1=16+1=17Таким образом, существует 17 различных нечётных значений степеней.
Согласно нашему предположению из Шага 2, каждое значение степени встречается ровно 3 раза. Значит, общее количество вершин с нечётной степенью равно:
Nodd=17×3=51Шаг 4. Противоречие и вывод
Мы получили, что количество вершин с нечётной степенью равно 51. Число 51 является нечётным.
Однако, согласно лемме о рукопожатиях (Шаг 3), количество вершин нечётной степени в любом графе должно быть чётным. Возникает противоречие: 51 — нечётное число, но оно должно быть чётным.
Значит, наше предположение о том, что ни одна степень не повторяется более трёх раз, было неверным.
Вывод: Среди 102 учеников обязательно найдутся хотя бы четверо с одинаковым числом знакомых.
Доказано от противного: если бы не было четырёх с одинаковой степенью, то каждая из 34 возможных степеней встречалась бы ровно 3 раза. Тогда число вершин нечётной степени было бы 17·3=51 (нечётное), что противоречит лемме о рукопожатиях.
Задача решается через принцип Дирихле в сочетании с паритетом степеней вершин. Ключевой момент — подсчет количества нечётных степеней в заданном интервале и умножение на максимально допустимую кратность (3), что дает нечётный результат, невозможный для реального графа.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 82 из моего учебника?
Номер совпадает с учебником «Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 82?
Краткий ответ: Доказано от противного: если бы не было четырёх с одинаковой степенью, то каждая из 34 возможных степеней встречалась бы ровно 3 раза. Тогда число вершин нечётной степени было бы 17 · 3 = 51 (нечётное), что противоречит лемме о рукопожатиях.
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 10. Изоморфные графы. Плоские и планарные графы.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.