Wheel

In this problem, we explore a unique road system in a country with n+1 cities: the capital and $n$ regular cities. These regular cities are arranged in a circle with the capital at the center. The distance between each pair of neighboring regular cities is identical. Each city is connected by roads to its two neighboring cities and to the capital. From an aerial view, this forms a regular $n$-gon with vertices linked to the center.

In this scenario, two equally powerful opposition parties aim to take control of the country, but neither intends to do so peacefully. Each city, including the capital, has a stationed tank platoon. At the start of the next day, each city will be seized by one of the opposition parties with equal probability, and the tank platoon in that city will fall under the control of the seizing party. Each party then plans to consolidate the largest possible army in one location. A tank platoon can only travel along a road if both cities connected by the road are controlled by the same party.

As the leader of an underground movement also seeking power, you need to determine the expected value of the largest number of tank platoons that can be gathered in one city. Your organization is counting on you!

For instance, consider a scenario with three regular cities. All four cities (three regular and the capital) are interconnected by roads. There is a $1/8$ probability that all cities will be seized by the same party, resulting in a maximum army size of 4. With a $3/8$ probability, two cities will be controlled by one party and two by the other, leading to a maximum army size of 2. Lastly, with a $1/2$ probability, one city will be seized by one party and the other three by the other, resulting in a maximum army size of 3. The expected value in this case is calculated as 4\times 1/8 + 2\times 3/8 + 3\times 1/2 = 2.75.