Колесо

У цій задачі ми розглядаємо унікальну систему доріг у країні, в якій є n+1 місто: столиця та $n$ звичайних міст. Звичайні міста розміщені на колі, центр якого знаходиться у столиці. Відстань між будь-якими двома сусідніми звичайними містами однакова. Кожне місто з'єднане дорогами зі своїми двома сусідами та зі столицею. Якщо подивитися згори, то це утворює правильний $n$-кутник з вершинами, з'єднаними з центром.

У країні існують дві однаково сильні опозиційні партії, які прагнуть захопити владу, і жодна з них не збирається робити це мирно. У кожному місті, включаючи столицю, розташований танковий взвод. На початку наступного дня кожне місто буде захоплене однією з опозиційних партій з однаковою ймовірністю, і танковий взвод у цьому місті перейде під контроль завойовника. Далі кожна партія планує зосередити максимальну кількість своїх взводів в одному місті. Танковий взвод може подорожувати дорогою лише якщо обидва міста, які вона з'єднує, контролюються однією партією.

Ви — організатор підпільного руху, який теж хоче здобути владу. Вам потрібно визначити математичне сподівання максимальної кількості танкових взводів, які можна зосередити в одному місті. Ваша організація покладається на вас!

Наприклад, нехай є три звичайних міста. Тоді всі чотири міста (три звичайних і столиця) попарно з'єднані дорогами. З ймовірністю $1/8$ усі міста буде захоплено однією партією — тоді максимальний розмір армії буде $4$. З ймовірністю $3/8$ дві пари міст будуть під контролем різних партій — максимум $2$. Нарешті, з ймовірністю $1/2$ одне місто буде під контролем однієї партії, три інших — іншої, максимум — $3$. Математичне сподівання: 4\times 1/8 + 2\times 3/8 + 3\times 1/2 = 2.75.