}

In Anchuria, presidential elections are being prepared, in which President Miraflores wants to win. Exactly half of the numerous voters support Miraflores, and the other half support Dick Maloney. Miraflores is also a voter. By law, he has the right to divide all voters into two electoral districts at his discretion. In each district, the voting is conducted as follows: each voter marks the name of their candidate on the ballot; all ballots are placed in an urn. Then, one random ballot is drawn from the urn, and the candidate whose name is marked on it wins in that district. A candidate wins the election only if they win in both districts. If no winner is determined, a second round of voting is held under the same rules. How should Miraflores divide the voters to maximize the probability of his victory in the first round?

#
Suppose there are $2 n$ voters in Anchuria in total. They can be divided into districts so that exactly half of the voters in each district are supporters of Miraflores. Under this condition, the probability that Miraflores wins in the first round is $1 / 2 \cdot 1 / 2 = 1 / 4$.

Now suppose that in one of the districts, fewer than half of the voters vote for Miraflores. Such a district is called an opposition district. Then in another district, more than half of the voters are for Miraflores.

If there are $m$ voters in the opposition district ($m < 2 n$), then the number of voters voting for Miraflores in this district does not exceed $m / 2 - 0.5$. Therefore, the probability of Miraflores winning in the opposition district is no more than $\left(\frac{m}{2} - 0.5\right) : m = \frac{1}{2}\left(1 - \frac{1}{m}\right) \leq \frac{1}{2}\left(1 - \frac{1}{2 n - 1}\right) = \frac{n - 1}{2 n - 1}$,

The probability of Miraflores winning in the non-opposition district does not exceed 1. Therefore, the probability of Miraflores winning in the first round is no more than $1 \cdot \frac{n - 1}{2 n - 1} = \frac{n - 1}{2 n - 1}$. This probability can be achieved if Miraflores assigns his only supporter to the non-opposition district. Then in the opposition district, there will be $2 n - 1$ voters, of which $n - 1$ vote for Miraflores.

## Answer

One district should consist of only one Miraflores, and the other should consist of all the other voters.

$$
\text { Send a comment }
$$

## [ Algorithms (miscellaneous) ]

Problem