Question

ПОМОГИТЕЕЕЕЕЕ СРОЧНОООООО ОЧЕНЬ ПРОШУ!!!!! ДАЮ МНОГО БАЛЛОВ!!!!!!
В прекрасной стране роботов всё очень оптимально: между любыми двумя городами либо есть только одна дорога, либо нет дороги, причём из каждого города выходит одинаковое количество дорог, и число это не меньше 5. Какое максимальное число городов может быть в стране роботов, если в ней 286 дорог?

Answer 1

Ответ:

Пошаговое объяснение:

По лемме о рукопожатиях:

Для любого графа сумма степеней всех его вершин равна удвоенному количеству всех его ребер. Ребра в нашей задаче- это дороги, а вершины- это города. То есть получаем уравнение:

n = 2 * 286 / degV, где n - это искомое количество городов, а degV- это количество дорог, которые выходят из каждого города(по условию количество дорог, выходящих из каждого города равно).

Далее, так как n- это количество городов, то n- целое число, поэтому 2 * 286 = 572 должно делиться нацело на degV. И при этом n должно быть максимальным. Для получения ответа просто выбираем в качестве degV минимальное число, которое >= 5 и которое делит нацело 572. Это число 11.

Поделив 572 на 11 получим 52.

Ответ: 52.