Задача 011 — Задачи на Графы

В некоторой стране 100 городов. Любые два города этой страны соединены дорогой. От этой страны отделилась независимая республика, причем количество дорог, соединяющих города этой республики, равно количеству дорог, ведущих из республики в остальные города этой страны. Сколько городов в отделившейся республике? (Приведите все варианты и докажите, что других нет).

Подсказка

Обозначьте число городов в республике за х.

Решение

Ответ: 67.

Решение: Пусть в отделившейся республике $x$ городов. Тогда количество дорог, соединяющих ее города, равно $x(x-1) / 2$ (из каждого из $x$ городов выходит по $x-1$ дороге, и каждая дорога при этом считается дважды), а количество дорог, ведущих из республики в остальные города страны, равно $x(100-x)$ . По условию $x(x-1) / 2=x(100-x)$ . Сократив на $x$ и решив получившееся уравнение, находим ответ.