Задание №166184: Задание 8
Задание 8. Вариант 4. Компания из шестнадцати человек удовлетворяет условию: если два человека знакомы, то у одного из них не более двух знакомых в этой компании. Найдите наибольшее возможное количество пар знакомых в этой компании. 3
Что проверяет это задание
Задание относится к теме «Задание 8» и рассчитано на уровень 10 класса. Для решения понадобятся:
- анализ условия
- выбор формулы
- проверка вычислений
Источник: ВсОШ в Москве — официальный архив · 2025
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- ВсОШ в Москве — официальный архив
- Организатор
- Редакция «Я сам решу»
- Год материала
- 2025
- Материалы
- 2 файла
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Задание 8» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Математика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
Задание 8. Вариант 1. Компания из десяти человек удовлетворяет условию: если два человека знакомы, то у одного
из них не более двух знакомых в этой компании. Найдите наибольшее возможное количество пар знакомых в этой
компании.
Ответ: 16
Решение.
Переформулируем задачу на язык графов. Рассмотрим граф, в котором вершины — люди, пары знакомых —
рёбра. Требуется найти наибольшее число рёбер в таком графе. Назовём людей (и вершины) замкнутыми, если у них
не более двух знакомых, а остальные вершины назовём общительными.
Заметим, что общительные не знакомы между собой, поэтому хотя бы один конец любого ребра выходит из за-
мкнутой вершины. Следовательно, число рёбер в графе не больше суммы степеней замкнутых вершин.
Пусть замкнутых не более 8, тогда рёбер не более 8 · 2 = 16.
Пусть замкнутых ровно 9. Тогда степень единственной общительной вершины не более 9.
Тогда сумма степеней графа не более 9 · 2 + 9 = 27, поэтому число рёбер не больше 13.
Пусть замкнутых ровно 10. Тогда число рёбер равно половине суммы степеней, которая, в свою очередь, не пре-
вышает 10 · 2 = 20. Следовательно, число рёбер не больше 10.
Пример графа с 16 рёбрами приведён на рисунке
Используемые формулы
Пусть замкнутых не более 8, тогда рёбер не более 8 · 2 = 16.Тогда сумма степеней графа не более 9 · 2 + 9 = 27, поэтому число рёбер не больше 13.вышает 10 · 2 = 20.
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Не проверить область допустимых значений.
- Потерять знак при переносе или раскрытии скобок.
- Не выполнить обратную подстановку.