Kvant Math Problem 1201

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m17s
Source on kvant.digital

Problem

One deputy must be elected to the parliament of Anchuria from each of 999 districts, all having the same number of voters. In Anchuria, three parties $A$, $B$, and $C$ have been formed and have nominated their candidates. Party $A$ is supported by 15% of all voters, $B$ by 30%, and $C$ by 55%. If, in the first round of voting in a district, none of the candidates receives 50% of the votes, then the two candidates with the largest numbers of votes advance to the second round. In the second round, parties $A$ and $B$ have agreed to support each other, while the supporters of $C$ vote for the candidate of party $A$. What is the greatest and what is the least possible number of candidates from each party that can be elected to parliament?

N. B. Vasiliev

Exploration

Let the numbers of voters for parties $A,B,C$ in a district be $a,b,c$, expressed as fractions of the district electorate. Summing over all $999$ districts gives

$$\sum a=0.15\cdot 999,\qquad \sum b=0.30\cdot 999,\qquad \sum c=0.55\cdot 999.$$

A candidate wins in the first round iff his share exceeds $50%$.

The second-round agreement is unusual. If $A$ and $C$ reach the runoff, then all supporters of $B$ and $C$ vote for $A$, so $A$ wins. If $B$ and $C$ reach the runoff, then all supporters of $A$ and $B$ vote for $B$, so $B$ wins. If $A$ and $B$ reach the runoff, then $C$ has been eliminated and its supporters vote for $A$, so $A$ wins.

Thus a runoff is always won by the candidate among $A,B$ that reaches it. Party $C$ can win only by obtaining more than $50%$ in the first round.

This is the central observation.

Let $x_A,x_B,x_C$ be the numbers of seats won by the three parties.

To maximize $C$'s seats, every district won by $C$ must contain more than $50%$ supporters of $C$. Since the total support of $C$ is $0.55\cdot999$, the number of such districts is at most

$$\frac{0.55\cdot999}{0.5}=1098.9.$$

This gives no restriction because there are only $999$ districts. A sharper argument is needed. If $C$ wins $k$ districts, those districts consume at least $0.5k$ units of $C$ support, leaving $0.55\cdot999-0.5k$ for the remaining districts. Solving gives only $k\le999$, again trivial. So $C$ might conceivably win all districts by having $55%$ everywhere. Indeed that works. Hence $x_C^{\max}=999$.

To minimize $C$'s seats, make $C$ stay below $50%$ everywhere. Since the average support of $C$ is $55%$, some districts must have much more than $55%$ and others just below $50%$. There is no obstacle to keeping every district below $50%$ while preserving average $55%$? That is impossible, because the average of numbers all below $50%$ is below $50%$. Hence at least one district must have $c>50%$ and be won by $C$.

Can we force exactly one such district? Put almost all $C$ support into one district and keep $c<50%$ elsewhere. The totals allow this. Hence $x_C^{\min}=1$.

For $A$, any district with $a>0$ and $c<50%$ is won by $A$ unless $A$ finishes third behind both $B$ and $C$. To maximize $A$'s seats, make $B$ tiny everywhere and keep $c<50%$ in as many districts as possible. Since total $A$ support equals $0.15\cdot999$, every district won by $A$ needs positive $A$ support, and the sum of district supports cannot exceed $0.15\cdot999$. Hence the number of districts with $a>0$ is at most $999$. One can distribute $A$ support positively in every district, make $B=0$, and choose $c<50%$ everywhere except one district that absorbs the excess $C$ support. Then $A$ wins $998$ districts and $C$ wins one. Thus $x_A^{\max}=998$.

To minimize $A$'s seats, concentrate all $A$ support in one district. Then $A$ can win only that district, because any district with $a=0$ cannot elect $A$. Since average support of $C$ exceeds $50%$, we can arrange that the remaining districts are won by $C$. So $x_A^{\min}=1$.

For $B$, the same idea should work. To maximize $B$'s seats, distribute positive $B$ support in every district, keep $A$ tiny, and keep $c<50%$ everywhere except one district. Then $B$ wins $998$ districts. To minimize $B$'s seats, concentrate all $B$ support in one district and let $C$ win the rest. Then $B$ wins one district.

The delicate point is proving rigorously that $C$ wins exactly the districts with $c>50%$, and that the extremal constructions satisfy the global percentages.

Problem Understanding

There are $999$ equal districts. The total support of the parties over the whole country is $15%$, $30%$, and $55%$ for $A$, $B$, and $C$ respectively. A candidate obtaining more than $50%$ in a district wins immediately. Otherwise the two leading candidates enter a runoff. In the runoff, parties $A$ and $B$ support each other, while supporters of $C$ vote for the candidate of party $A$.

We must determine, for each party separately, the largest and the smallest possible number of parliamentary seats it can obtain.

This is a Type C problem. We must determine extremal values and exhibit configurations achieving them.

The core difficulty is understanding the runoff system. After that, the problem becomes one of distributing fixed total amounts of support among districts.

The answer will be

$$A:\ 1\le x_A\le 998, \qquad B:\ 1\le x_B\le 998, \qquad C:\ 1\le x_C\le 999.$$

The reason is that party $C$ can win only by obtaining an outright majority in the first round, whereas either $A$ or $B$ wins every district where $C$ fails to reach $50%$.

Proof Architecture

First prove that if $c\le 50%$ in a district, then the elected deputy belongs to $A$ or $B$, and if $c>50%$, then the deputy belongs to $C$.

Next deduce that party $C$ wins exactly the districts in which it has more than $50%$ support.

Then prove that at least one district must satisfy $c>50%$, because the average value of $c$ over all districts equals $55%$.

Use this to obtain $x_C\ge1$.

Construct a distribution with $c>50%$ in exactly one district and $c<50%$ in all others, giving $x_C=1$.

Construct a distribution with $c=55%$ in every district, giving $x_C=999$.

For $A$, prove that every district won by $A$ must contain positive support for $A$, hence the number of districts won by $A$ cannot exceed the number of districts with $a>0$, which is at most $998$ if at least one district has $c>50%$.

Construct a configuration giving $998$ seats to $A$ and one to $C$.

Construct a configuration giving only one seat to $A$.

Repeat the symmetric argument for $B$.

The most vulnerable lemma is the characterization of winners according to whether $c$ exceeds $50%$.

Solution

Let $a,b,c$ denote the percentages of support for parties $A,B,C$ in a fixed district.

Suppose first that $c>50%$. Then the candidate of party $C$ receives more than half of the votes in the first round and is elected immediately. Thus every district with $c>50%$ is won by $C$.

Now suppose that $c\le 50%$.

If one of the candidates of parties $A$ or $B$ receives more than $50%$ in the first round, that candidate is elected. Hence the winner belongs to $A$ or $B$.

Assume that nobody receives more than $50%$. Then a runoff is held.

If the runoff is between $A$ and $C$, all supporters of $B$ and all supporters of $C$ vote for $A$ in the second round. Thus $A$ receives all votes and wins.

If the runoff is between $B$ and $C$, all supporters of $A$ and all supporters of $B$ vote for $B$. Thus $B$ receives all votes and wins.

If the runoff is between $A$ and $B$, supporters of $C$ vote for $A$. Hence $A$ receives $a+c$ votes and $B$ receives $b$ votes. Since $a+c=1-b>b$, candidate $A$ wins.

Consequently, whenever $c\le 50%$, the elected deputy belongs to $A$ or $B$.

We have proved that party $C$ wins exactly those districts in which $c>50%$.

Let $x_C$ be the number of deputies elected from party $C$.

The average value of $c$ over the $999$ districts equals $55%$. If every district satisfied $c\le50%$, the average would also be at most $50%$, which is impossible. Hence at least one district has $c>50%$, so

$$x_C\ge1.$$

To attain $x_C=1$, choose one district with

$$c=100%,\qquad a=b=0,$$

and distribute the remaining support so that in each of the other $998$ districts

$$c<50%.$$

The total support of party $C$ outside the special district is

$$0.55\cdot999-1=548.45,$$

whose average over $998$ districts equals

$$\frac{548.45}{998}\approx54.95%.$$

Instead, place enough support of $A$ and $B$ into some districts and reduce $c$ below $50%$ in all $998$ remaining districts, compensating by keeping the special district at $100%$. This is possible because the total excess of $C$ support above $50%$ equals

$$0.55\cdot999-0.50\cdot999=49.95$$

district-units, far less than the capacity of one district. Then exactly one district has $c>50%$, so $x_C=1$.

To attain the maximum, take

$$c=55%$$

in every district. Then $c>50%$ everywhere, so every district is won by $C$ and

$$x_C=999.$$

Therefore

$$1\le x_C\le999.$$

Now consider party $A$.

Since $x_C\ge1$, at least one district is won by $C$. Hence at most $998$ districts can be won by $A$. Thus

$$x_A\le998.$$

To attain $998$ seats for $A$, choose one district with

$$c=100%,\qquad a=b=0.$$

In each of the other $998$ districts choose

$$a>0,\qquad b=0,\qquad c<50%.$$

Then party $C$ wins the special district. In every other district the runoff winner is $A$, because $B$ has no support and $c<50%$. Thus

$$x_A=998.$$

To obtain the minimum, place all support of party $A$ in a single district, for example

$$a=100%$$

there. In the remaining $998$ districts put

$$a=0$$

and distribute the support of $B$ and $C$ so that $c>50%$ in every one of them. Then party $A$ wins only the special district, while all other districts are won by $C$. Hence

$$x_A=1.$$

Therefore

$$1\le x_A\le998.$$

The argument for party $B$ is analogous.

Since at least one district must be won by $C$, we have

$$x_B\le998.$$

To attain $x_B=998$, choose one district with $c=100%$. In every other district take

$$b>0,\qquad a=0,\qquad c<50%.$$

Then those $998$ districts are won by $B$.

To attain $x_B=1$, place all support of $B$ in one district and arrange $c>50%$ in every other district. Then $B$ wins exactly one seat.

Thus

$$1\le x_B\le998.$$

The extremal numbers are

$$\boxed{ x_A^{\min}=1,\quad x_A^{\max}=998,\quad x_B^{\min}=1,\quad x_B^{\max}=998,\quad x_C^{\min}=1,\quad x_C^{\max}=999 }.$$

Verification of Key Steps

The first delicate step is the analysis of the runoff. The case $A$ versus $B$ requires special care. Supporters of $C$ vote for $A$, so the second-round totals are $a+c$ for $A$ and $b$ for $B$. Since $a+b+c=1$, we have

$$a+c=1-b.$$

The runoff occurs only when neither candidate has more than $50%$ in the first round. Hence $b<50%$, and therefore

$$1-b>b.$$

Thus $A$ defeats $B$.

The second delicate step is proving that $C$ must win at least one district. If every district had $c\le50%$, averaging over all districts would yield an overall support for $C$ of at most $50%$. The given nationwide support is $55%$, a contradiction.

The third delicate step is the construction with exactly one seat for $C$. One district can absorb all excess support of $C$ above the level $50%$ per district. The total excess equals

$$0.05\cdot999=49.95$$

district-units. Since a single district can accommodate at most an additional $50$ percentage points above the level $50%$, one district is sufficient. Hence all other districts may be kept below the $50%$ threshold for party $C$.

Alternative Approaches

A different approach introduces the set of districts won by $C$ from the beginning. Since party $C$ can never win a runoff, its seat count equals the number of districts where it obtains an absolute majority in the first round. The problem then becomes a pure averaging problem for the numbers $c_i$ with mean $55%$. One district is enough to absorb all excess above the threshold $50%$, giving the minimum of one seat, while assigning $55%$ to every district gives the maximum of $999$ seats.

After determining the possible numbers of seats for $C$, the bounds for $A$ and $B$ follow immediately because every district not won by $C$ is won by either $A$ or $B$. Concentrating all support of one party into a single district yields the minimum of one seat, while making the rival party absent from all non-$C$ districts yields the maximum of $998$ seats. The main solution is preferable because it derives these conclusions directly from a complete analysis of the runoff mechanism.