В фэнтезийных мирах постоянно идут бои, так почему бы не приплести сюда математическую задачу?
Условие:
В некоторой эльфийской стране n городов и из каждого города выходит не менее k дорог (одна дорога соединяет два города, между двумя городами не более одной дороги). С этой страной ведут войну орки и в ходе боевых действий они разбили страну на m частей (не уничтожив и не перекрыв ни одной дороги), так что в каждой части никакие два города не соединены дорогой. Докажите, что m ≥n/(n-k) .
Решение:
Рассмотрим такое разбиение на m частей. Тогда найдется такая часть, в которой не менее чем n/m городов. Но по условию каждый город может быть соединен с городами только из других частей, поэтому из него выходит не более n-n/m дорог. То есть
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!
