В Тридесятом царстве 4 города и ещё один город столица. Один город впал немилость царя. Какое наибольшее количество дорог может оставить царь между городами так, чтобы в опальный город нельзя было проехать ни из одного другого города?

Для решения этой задачи можно использовать концепцию графов. У нас есть 4 города и 1 город-столица, итogo в сумме 5 городов. Царь хочет, чтобы опальный город не мог быть достигнут из других городов. Это означает, что мы должны изолировать опальный город от остальных. Если мы обозначим города как A, B, C, D (где D — опальный город) и E — столицу, то чтобы удовлетворить условия задачи, мы можем соединить остальные города (A, B, C, E) между собой, но не соединять их с D. Таким образом, максимальное количество дорог, которые могут оставаться между городами A, B, C и E, будет зависеть от того, сколько соединений можно сделать между этими 4 городами. Каждый из этих городов можно соединить с каждым другим, что формирует полный граф из 4 узлов. Формула для подсчета количества дорог в полном графе из n узлов — это \( \frac{n(n-1)}{2} \). Поэтому для 4 городов: \[ \frac{4(4-1)}{2} = \frac{4 \cdot 3}{2} = 6. \] Таким образом, царь может оставить 6 дорог между другими городами, не допускающих проезда в опальный город.