На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога АБ длиннее дороги ЖИ. Определите длину дороги ВД.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 | |
| П1 | 8 | 11 | 20 | |||||
| П2 | 19 | 28 | 29 | 15 | ||||
| П3 | 8 | 19 | 12 | 9 | ||||
| П4 | 11 | 28 | 12 | 26 | ||||
| П5 | 18 | 16 | 14 | |||||
| П6 | 20 | 26 | 18 | 32 | ||||
| П7 | 29 | 16 | 32 | 17 | ||||
| П8 | 15 | 9 | 14 | 17 |
Заметим, что в таблице имеется только один пункт степени 4, имеющий дороги с населенными пунктами степени 3, это населенный пункт А, ему соответствует пункт П6. Также в таблице имеется только один пункт степени 4, имеющий дороги с населенными пунктами только степени 4, это населенный пункт И, ему соответствует пункт П2.
В таблице имеется два пункта степени 3, это пункты В и Г, им могут соответствовать пункты П1 и П5. Населенным пунктам Б и Ж могут соответствовать пункты П4 и П7.
Рассмотрим пункт Б. Он может быть пунктом П4, тогда длина дороги АБ равна 26. Также может быть пунктом П7, тогда длина дороги АБ 32.
Рассмотрим пункт Ж. Он может быть пунктом П4, тогда длина дороги ЖИ равна 28. Также может быть пунктом П7, тогда длина дороги ЖИ 29.
По условию задачи дорога АБ длиннее дороги ЖИ, тогда пункт Б может соответствовать только пункту П7, так как длина дороги П6–П7 больше длин дорог П2–П4 и П2–П7. Тогда населенный пункт Б соответствует пункту П7, населенный пункт Ж соответствуют пункту П4.
Населенный пункт В имеет общие дороги с пунктами А и Б (пункты П6 и П7), ему соответствует пункт П5.
Населенный пункт Д имеет общие дороги с В, Б и И (пункты П5, П7 и П2), ему соответствует пункт П8.
Длина дороги ВД (пункты П5 и П8) равна 14.
Ответ: 14.
Приведём решение Ивана Новикова на языке Python.
from itertools import *
a = '346 3478 1248 1236 678 1457 2568 2357'.split()
b = 'жа аб би иж жг га ав вб бд ди ие еж ге ед дв'.split()
print(*range(1 , 9))
for i in permutations('абвгдежи'):
if all(str(i.index(b1) + 1) in a[i.index(b2)] for b1 , b2 in b):
print(*i)
Приведём решение Юрия Красильникова на языке Python.
def алфавит(s): return ''.join(sorted(set(s.replace(' ',''))))
# алфавит - строка из символов строки s в алфавитном порядке (кроме пробела)
def дуги(s): return set(map(алфавит,s.split()))
# дуги - множество дуг графа (пар символов), каждая пара упорядочена по алфавиту
таблица = '13 14 16 23 24 27 28 34 38 46 56 57 58 67 78' # дуги по таблице
граф = 'АБ АВ АГ АЖ БВ БД БИ ВД ГЕ ГЖ ДЕ ДИ ЕЖ ЕИ ЖИ' # дуги по схеме
# Не надо бояться включить одну дугу дважды (напр., БД и ДБ). Главное - ничего не пропустить.
print(алфавит(таблица)) # заголовок
from itertools import permutations
for p in permutations(алфавит(граф)): # все возможные перестановки буквенных обозначений
табтранс = str.maketrans(''.join(p),алфавит(таблица)) # таблица трансляции
if дуги(таблица) == дуги(граф.translate(табтранс)): # если множества дуг совпадают
print(''.join(p),
'АБ -','АБ'.translate(табтранс),
'ЖИ -','ЖИ'.translate(табтранс),
'ВД -','ВД'.translate(табтранс))