1-я Европейская математическая олимпиада, Вильнос, Литва

$n\geqslant2$ бүтін саны берілген. Еуроландияда $n$ қала бар және кез келген екі қала өзара тікелей әуе рейстерімен қосылған. Әрбір қалалар жұбы үшін император осы екі қала арасындағы барлық әуе рейстеріне бірдей болатын оң баға белгілейді. Әртүрлі $A$ және $B$ қалалары үшін $D(A,B)$ арқылы осы қалалар арасындағы ең арзан саяхаттағы әуе рейстерінің санын белгілейік; егер мұндай саяхаттар бірнешеу болса, $D(A,B)$ ең ұзақ саяхат үшін алынады. Әрбір $n$ мәні үшін император қол жеткізе алатын барлық әртүрлі қалалар жұбы $(A,B)$ үшін $D(A,B)$ шамаларының орташа мәнінің ең үлкен мүмкін мәнін табыңыз.