В стране 120 посёлков, которым присвоены номера 1, 2, 3, ..., 120. Два посёлка соединены прямой дорогой, если сумма их номеров делится на 8. Какое минимальное число дорог ещё надо построить, чтобы из каждого посёлка можно было попасть в любой другой, возможно, через другие посёлки?

Для решения этой задачи нужно понять, какие посёлки уже соединены дорогами и сколько ещё нужно добавить, чтобы все посёлки были связаны между собой.

Сначала определим, какие посёлки могут быть соединены. Сумма номеров двух посёлков должна делиться на 8. Это значит, что посёлки с номерами (a) и (b) соединены, если (a + b) кратно 8.

Рассмотрим остатки от деления номеров посёлков на 8. Возможные остатки: 0, 1, 2, 3, 4, 5, 6, 7.

Для того чтобы сумма двух номеров делилась на 8, остатки этих номеров при делении на 8 должны в сумме давать либо 8, либо 0.

• Остаток 0 может сочетаться только с остатком 0 (8k + 0 + 8m + 0 = 8(k+m)).


• Остаток 1 может сочетаться с остатком 7.


• Остаток 2 может сочетаться с остатком 6.


• Остаток 3 может сочетаться с остатком 5.


• Остаток 4 может сочетаться с остатком 4.

Таким образом, посёлки делятся на несколько групп, внутри которых они могут быть соединены. Нам нужно посчитать, сколько таких групп и сколько дорог нужно построить, чтобы объединить все группы в одну.

Подсчитаем количество посёлков с каждым остатком от деления на 8:

• Остаток 0: 120 / 8 = 15


• Остаток 1: 15


• Остаток 2: 15


• Остаток 3: 15


• Остаток 4: 15


• Остаток 5: 15


• Остаток 6: 15


• Остаток 7: 15

Теперь определим группы, которые формируются:

1. Посёлки с остатком 0.


2. Посёлки с остатком 1 и 7.


3. Посёлки с остатком 2 и 6.


4. Посёлки с остатком 3 и 5.


5. Посёлки с остатком 4.

Получается 5 групп. Чтобы связать все группы в одну, нужно построить минимум 4 дороги (количество групп минус 1). Каждая дорога связывает два посёлка из разных групп.

Ответ: 4