1. Главная
  2. Библиотека
  3. Геометрия
  4. Столица некоторой страны соединена дорогами с 4 другими...
Разбор задачи

Столица некоторой страны соединена дорогами с 4 другими городами. Каждый город, соединенный со столицей напрямую, соединен с 5 городами (включая столицу). Каждый город, из которого до столицы можно доехать лишь через один промежуточный город, соединен с 6

  • Предмет: Геометрия
  • Автор: Кэмп
  • #Дискретная математика
  • #Теория графов
Столица некоторой страны соединена дорогами с 4 другими городами. Каждый город, соединенный со столицей напрямую, соединен с 5 городами (включая столицу). Каждый город, из которого до столицы можно доехать лишь через один промежуточный город, соединен с 6

Условие:

Столица некоторой страны соединена дорогами с 4 другими городами. Каждый город, соединенный со столицей напрямую, соединен с 5 городами (включая столицу). Каждый город, из которого до столицы можно доехать лишь через один промежуточный город, соединен с 6 другими. Если через 2 промежуточных - с 7 другими, и так далее. Какое наименьшее число городов может быть в стране?

Решение:

1. Дано

  1. Есть Столица (SS).
  2. Столица соединена дорогами с 4 другими городами (назовем их Города 1-го уровня, L1L_1).
  3. Города 1-го уровня (L1L_1): каждый соединен с 5 городами (включая столицу).
  4. Города 2-го уровня (L2L_2): доехать до них можно через 1 промежуточный город (т.е. через город L1L_1). Каждый такой город соединен с 6 другими.
  5. Города 3-го уровня (L3L_3): доехать до них можно через 2 промежуточных города. Каждый такой город соединен с 7 другими.
  6. Общая закономерность: Город на расстоянии kk промежуточных переходов от столицы соединен с k+5k+5 городами....

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое ключевое условие необходимо выполнить при определении числа городов на каждом уровне, чтобы найти наименьшее общее количество городов в стране?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Выбери предмет