Задание №149671: Задание 10.6
10.6. В стране ровно 1000 городов, некоторые пары городов соединены двусторонними авиалиниями. Известно, что для любого на- ⩽ турального k 500 выполнено следующее утверждение: «Если выбрать любое множество A из k городов, то найдётся хотя бы k городов, не принадлежащих A, каждый из которых соединён авиалинией хотя бы с одним городом из A». Какое наименьшее количество авиалиний может быть в этой стране?
Что проверяет это задание
Задание относится к теме «Задание 10.6». Для решения понадобятся:
- анализ условия
- выбор формулы
- проверка вычислений
Источник: ВсОШ — официальный архив
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- ВсОШ — официальный архив
- Организатор
- Редакция «Я сам решу»
- Материалы
- 1 файл
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Задание 10.6» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Математика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
10.6. В стране ровно 1000 городов, некоторые пары городов соединены двусторонними авиали-
ниями. Известно, что для любого натурального k ⩽ 500 выполнено следующее утвержде-
ние: «Если выбрать любое множество A из k городов, то найдётся хотя бы k городов, не
принадлежащих A, каждый из которых соединён авиалинией хотя бы с одним городом из
A». Какое наименьшее количество авиалиний может быть в этой стране?
Ответ: 250000.
Решение. Положим n = 500, так что в нашем графе 2n вершин.
Оценка. Докажем, что в нашем графе степени всех вершин хотя бы n. Отсюда будет
Используемые формулы
Положим n = 500, так что в нашем графе 2n вершин.
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Не проверить область допустимых значений.
- Потерять знак при переносе или раскрытии скобок.
- Не выполнить обратную подстановку.