На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 | П9 | |
| П1 | 38 | 30 | 34 | 26 | |||||
| П2 | 38 | 31 | 22 | 24 | |||||
| П3 | 30 | 31 | 32 | ||||||
| П4 | 40 | 28 | |||||||
| П5 | 22 | 25 | 36 | ||||||
| П6 | 24 | 40 | 25 | 37 | |||||
| П7 | 32 | 36 | |||||||
| П8 | 34 | 35 | |||||||
| П9 | 26 | 28 | 37 | 35 |
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога КИ короче дороги АГ. Определите длину дороги ДЖ.
На схеме только один населенный пункт степени 2 имеющий общие дороги с пунктами степени 3. Это пункт И, ему соответствует пункт П7. Пункт Д единственный пункт степени 4 у которого есть общие дороги с двумя пунктами степени 3. Тогда пункт Д это населенный пункт П2. Пункт Ж может быть или пунктом П3 или пунктом П5.
Предположим, что Ж это пункт П3. Тогда Г это пункт П1, К это пункт П5, а населенный пункт А это пункт П8. Тогда Дорога КИ длиною 36, а дорога АГ длиною 34, что противоречит условию, , что дорога КИ короче дороги АГ.
Предположим, что Ж это пункт П5. Тогда Г это пункт П6, К это пункт П3, а населенный пункт А это пункт П4. Тогда Дорога КИ длиною 36, а дорога АГ длиною 40, что подходит по условию. Тогда длина дороги ДЖ(П2-П5) равна 22.
Ответ: 22.
Приведём решение Юрия Красильникова на языке 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(табтранс))
В первом варианте дорога КИ - это дорога 57 длиной 36, а дорога АГ - это дорога 81 длиной 34, это противоречит условию.
Во втором варианте дорога КИ - это дорога 37 длиной 32, а дорога АГ - это дорога 46 длиной 40, это соответствует условию. Тогда дорога ДЖ - это дорога 25 длиной 22.

