1. Главная
  2. Библиотека
  3. Геометрия
  4. В стране 120 посёлков, которым присвоены номера . Два п...
Разбор задачи

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

  • Предмет: Геометрия
  • Автор: Кэмп
  • #Дискретная математика
  • #Теория графов
В стране 120 посёлков, которым присвоены номера . Два посёлка соединены прямой дорогой, если сумма их номеров делится на 8 . Какое минимальное число дорог ещё надо построить, чтобы из каждого посёлка можно было попасть в любой другой, возможно, через

Условие:

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

Решение:

Шаг 1. Понимаем условие задачи. Имеется 120 посёлков с номерами от 1 до 120. Между посёлками проводится дорога, если сумма их номеров делится на 8. Нужно выяснить, сколько дополнительных дорог надо построить, чтобы можно было добраться из любого посёлка в любой другой (дополнительные дороги можно строить без условия делимости).

Шаг 2. Рассмотрим посёлки по остатку от деления их номеров на 8. Пусть r – остаток от деления номера посёлка на 8 (r = 0,1,…,7). Два посёлка с остатками r1 и r2 будут соединены дорогой, если r1 + r2 ≡ 0 (mod 8), то есть, если r2 ≡ –r1 (mod 8). Получаем с...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое свойство номеров посёлков определяет наличие дороги между ними в исходной задаче?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Выбери предмет