Təkər

Bu məsələdə biz qeyri-adi yol sistemi olan bir ölkəni araşdırırıq. Həmin ölkədə **n+1 şəhər** vardır: bir paytaxt və **$n$** adi şəhər. Adi şəhərlər paytaxtı mərkəzdə olmaqla bir dairə üzrə yerləşir. İstənilən iki qonşu adi şəhər arasında məsafə eynidir. Hər bir şəhər iki qonşu şəhər və paytaxt ilə yollarla birləşir. Yuxarıdan baxıldıqda, bu konfiqurasiya mərkəzə birləşdirilmiş zirvələri olan düzgün $n$-bucaqlını xatırladır.

Bu ölkədə hakimiyyəti ələ keçirmək istəyən iki bərabər güclü müxalifət partiyası var və heç biri bunu sülh yolu ilə etmək niyyətində deyil. Hər bir şəhərdə, o cümlədən paytaxtda, bir tank bölməsi yerləşir. Növbəti günün əvvəlində, hər bir şəhər eyni ehtimalla müxalifət partiyalarından biri tərəfindən ələ keçiriləcək və həmin şəhərdəki tank bölməsi həmin partiyanın sərəncamına keçəcək. Hər bir partiya, öz nəzarətindəki tank bölmələrini bir şəhərdə cəmləməyə çalışacaq. Tank bölməsi yalnız yolun birləşdirdiyi hər iki şəhər eyni partiyanın nəzarətindədirsə, o yolda hərəkət edə bilər.

Siz isə hakimiyyəti ələ keçirmək istəyən gizli bir hərəkatın təşkilatçısınız. Bir şəhərdə cəmləşdirilə biləcək maksimum tank bölmələrinin gözlənilən dəyərini müəyyən etməlisiniz. Təşkilatınız sizə ümid edir!

Məsələn, üç adi şəhər olduğunu fərz edək. Onda bütün dörd şəhər (üç adi və paytaxt) yollarla birləşdirilib. **$1/8$** ehtimalla bütün şəhərlər eyni partiya tərəfindən ələ keçirilir və maksimum ordu sayı 4 olacaq. **$3/8$** ehtimalla şəhərlərin yarısı bir, yarısı digər partiya tərəfindən ələ keçiriləcək və maksimum ordu sayı 2 olacaq. Nəhayət, **$1/2$** ehtimalla bir şəhər bir partiyanın, digər üçü isə digər partiyanın olacaq və maksimum ordu sayı 3 olacaq. Gözlənilən dəyər: 4\times 1/8 + 2\times 3/8 + 3\times 1/2 = 2.75.