Question

У двох галактиках по п'ять населених планет. Між планетами можна літати лише рейсами компанії «Долетимо!». Усередині кожної з галактик від будь-якої планети до будь-якої можна долетіти не більше ніж з однією пересадкою, а між планетами з різних галактик немає жодного рейсу. Компанія хоче додати рейси між галактиками так, щоб від будь-якої з десяти планет до будь-якої іншої можна було долетіти не більше ніж з двома пересадками. Виявилось, що двох нових рейсів для цього буде замало. Скільки всього може бути всього різних рейсів компанії «Долетимо!» в обох галактиках? (Рейсом називається переліт без пересадки.) Вкажіть усі варіанти. Відповідь обґрунтуйте.

Answer 1

У кожній галактиці є 5 планет, тому всього може бути 5 * 4 = 20 рейсів між планетами в кожній галактиці. Оскільки ми можемо долетіти з будь-якої планети до будь-якої іншої з однією пересадкою, то всього може бути 20/2 = 10 рейсів в кожній галактиці.

Якщо компанія додасть два нових рейси між галактиками, то вони з’єднають дві планети з різних галактик. Однак цього буде недостатньо, щоб долетіти з будь-якої планети до будь-якої іншої з двома пересадками. Наприклад, якщо нові рейси з’єднають планету А з галактики 1 з планетою B з галактики 2 і планету C з галактики 1 з планетою D з галактики 2, то ми не зможемо долетіти з планети E (галактика 1) до планети F (галактика 2) з двома пересадками.

Тому компанії потрібно додати щонайменше три нових рейси між галактиками. Це означає, що всього може бути 10 + 10 + 3 = 23 рейси компанії «Долетимо!» в обох галактиках.

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