Задача
№ 14507
Формула включений-исключений, подсчёт двумя способами
Ур. 5
Всероссийская олимпиада школьников по математике, 10 класс, муниципальный этап 2023/24 уч. г. (Москва), задача 7
Девять посёлков соединены восемью дорогами $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$, как показано на рисунке. Длины дорог равны 1, 2, 3, …, 8 км в некотором порядке. Для каждого посёлка нашли длину кратчайшего пути до каждого другого по дорогам, и все такие длины сложили.
1. Известно, что полученная сумма — наибольшая из возможных. Какая из дорог может иметь длину 8 км? Укажите все возможные варианты.
2. Сколько существует способов присвоить дорогам их длины от 1 до 8 км так, чтобы полученная сумма оказалась наибольшей из возможных?
1. Известно, что полученная сумма — наибольшая из возможных. Какая из дорог может иметь длину 8 км? Укажите все возможные варианты.
2. Сколько существует способов присвоить дорогам их длины от 1 до 8 км так, чтобы полученная сумма оказалась наибольшей из возможных?
Ответ:
Решение: