Kvant Math Problem 1

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m46s
Source on kvant.digital

Problem

In the country of Anchuria, ruled by President Miraflores, the time for a new presidential election is approaching. The country has exactly 20 million voters, of whom only one percent (the regular army of Anchuria) support Miraflores. Naturally, Miraflores wants to be elected, but at the same time, he wants the election to appear democratic. By "democratic voting," Miraflores means the following: all voters are divided into several equal groups, then each of these groups is further divided into a number of equal groups, then these smaller groups are again divided into equal groups, and so on; in the smallest groups, a group representative — an elector — is chosen, then the electors select representatives to vote in a larger group, and so on; finally, the representatives of the largest groups elect the president. Miraflores divides the voters into groups as he wishes and instructs his supporters how to vote. Can he organize such a "democratic election" so that he is elected president? (In the event of a tie, the opposition wins.)

Moscow Mathematical Olympiad (XXXII)

Exploration

The structure of the election is a rooted tree. Every nonterminal group is divided into equal subgroups, and at each level a representative is chosen by majority vote among representatives from the level below. Miraflores controls only $1%$ of the voters, namely

$20,000,000\cdot 0.01=200,000.$

The question is whether these $200,000$ voters can be arranged so that a majority is produced at every stage.

A first toy example is a two-level election. If each elector represents $3$ voters, then one supporter in each group of $3$ is insufficient, because the vote in that group is $1$ against $2$. To win a group of $3$, at least $2$ supporters are needed. Thus a winning representative costs more than half of the voters in the group.

This suggests a general principle. If a group contains $m$ equal subgroups and the representative is chosen by majority, then to make that group elect a pro-Miraflores representative, more than half of its subgroups must themselves elect pro-Miraflores representatives. Inductively, more than half of all voters in such a winning group may have to be supporters.

Let us test this. Suppose a smallest group contains $n$ voters. To elect a supporter from it, at least $\lfloor n/2\rfloor+1$ supporters are needed. This exceeds $n/2$.

Now move one level upward. Suppose each group consists of $m$ subgroups. If a group elects a supporter, then at least $\lfloor m/2\rfloor+1$ of its subgroups elect supporters. Each of those subgroups contains more than half supporters. Hence the whole group contains more than

$\left(\frac m2\right)\left(\frac12\right)=\frac14$

of its voters as supporters. But this estimate is too weak. The exact count is

$\left(\lfloor m/2\rfloor+1\right)\left(\text{more than half of subgroup size}\right),$

which is actually more than half of the entire group. The same phenomenon seems to persist through all levels.

The crucial point is to prove rigorously that every group whose representative supports Miraflores must itself contain more than half supporters. Once that is established, the topmost electorate, which is the whole country, would need more than $10$ million supporters. Since only $200,000$ exist, the scheme is impossible.

The step most likely to hide an error is the induction showing that a winning representative forces a strict majority of supporters inside the corresponding group at every level.

Problem Understanding

The country has $20$ million voters, of whom only $200,000$ support Miraflores. The election is organized hierarchically. Each group is partitioned into equal subgroups, repeatedly, until the smallest groups are reached. Representatives are elected in the smallest groups, then representatives elect higher representatives, and so on, until the president is chosen.

Miraflores may choose the entire subdivision scheme and may distribute his supporters among the groups however he wishes. Ties are won by the opposition.

The task is to determine whether there exists such a hierarchical system that elects Miraflores despite his support from only $1%$ of the voters.

This is a Type D problem. We must determine whether a suitable construction exists.

The core difficulty is understanding how support propagates through several levels of majority voting. The natural intuition is that winning a representative at a higher level requires winning a majority of the lower-level units, and each such unit already requires a majority of supporters. This suggests that any pro-Miraflores representative corresponds to a group containing more than half supporters.

The answer should be negative. If the representative of the whole country supports Miraflores, then the entire country would have to contain more than half supporters, which is impossible because only $1%$ support him.

Proof Architecture

Lemma 1. In a smallest voting group of size $n$, if the elected elector supports Miraflores, then that group contains more than $n/2$ supporters. This follows because ties lose, so a strict majority is required.

Lemma 2. Assume every subgroup electing a pro-Miraflores representative contains more than half supporters. Then any larger group electing a pro-Miraflores representative also contains more than half supporters. This follows because a strict majority of its subgroups must elect pro-Miraflores representatives.

Lemma 3. Every group at every level whose representative supports Miraflores contains more than half supporters. This is obtained by induction on the level using Lemmas 1 and 2.

Main claim. The whole country cannot elect Miraflores. The top representative would require more than half of all $20$ million voters to support him, but only $200,000$ do.

The hardest part is Lemma 2, where one must convert a majority of winning subgroups into a majority of supporters in the entire parent group.

Solution

Let the smallest voting groups contain $s$ voters each. In such a group an elector is chosen by majority vote, and ties are lost by Miraflores.

Suppose a smallest group elects a pro-Miraflores elector. Then the number of Miraflores supporters in that group is at least

$\left\lfloor\frac s2\right\rfloor+1,$

hence strictly greater than $s/2$. Thus every smallest group that elects a pro-Miraflores elector contains more than half supporters.

We prove by induction on the level of the hierarchy the following statement:

Every group whose elected representative supports Miraflores contains more than half supporters among all voters belonging to that group.

The statement has already been proved for the smallest groups.

Assume it holds for all groups at some level. Consider a group at the next higher level. Suppose this group consists of $m$ equal subgroups, each containing $N$ voters, so the whole group contains $mN$ voters.

Assume that the representative elected by this group supports Miraflores. Since ties are won by the opposition, more than half of the subgroup representatives must support Miraflores. Therefore at least

$$$$

subgroups elect pro-Miraflores representatives.

By the induction hypothesis, each of these subgroups contains more than $N/2$ supporters. Hence the total number of supporters in the whole group exceeds

$\left(\left\lfloor\frac m2\right\rfloor+1\right)\frac N2.$

Because

$\left\lfloor\frac m2\right\rfloor+1>\frac m2,$

we obtain

$$> \frac m2\cdot\frac N2 = \frac{mN}{2}.$$

Thus the group contains more than half supporters among all its voters. The induction step is complete.

By induction, every group whose representative supports Miraflores contains more than half supporters.

Apply this to the top level, namely the entire country. If Miraflores were elected president, then the final representative supporting him would correspond to the whole electorate. The theorem just proved would imply that more than half of all voters support Miraflores.

The country contains $20,000,000$ voters, so this would require more than

$10,000,000$

supporters.

In reality, only

$$$$

voters support him.

This contradiction shows that no hierarchical division of voters can lead to the election of Miraflores.

Hence such a "democratic election" cannot be organized.

$$\boxed{\text{No, Miraflores cannot arrange such an election.}}$$

Verification of Key Steps

The first delicate point is the base case. In a smallest group of size $s$, a pro-Miraflores elector cannot be elected with exactly $s/2$ supporters when $s$ is even, because ties are won by the opposition. Thus a winning elector requires strictly more than half supporters, not merely at least half.

The second delicate point is the induction step. A careless argument might say that if more than half the subgroups are won, then more than half the voters are supporters. That is not automatically true. The reason it becomes true here is that all subgroups have equal size. If the subgroup size is $N$, each winning subgroup contributes more than $N/2$ supporters, and there are more than $m/2$ such subgroups. Multiplying these two strict inequalities yields a total exceeding $(mN)/2$.

The third delicate point is the passage to the whole country. The induction statement concerns every group at every level. The entire electorate is itself the unique group at the top level. Thus the statement applies directly to the country as a whole and forces more than $10$ million supporters if Miraflores is elected.

Alternative Approaches

One may assign to each group a label "good" if its representative supports Miraflores. The key observation is that a good group contains a strict majority of good subgroups, and at the lowest level a good subgroup contains a strict majority of supporters. Repeatedly replacing each good group by a majority of its constituents yields a majority of supporters in the entire top group. This is essentially the same induction expressed in combinatorial language.

Another approach is to view the election tree from the root downward. A pro-Miraflores root forces a majority of pro-Miraflores children, each such child forces a majority of pro-Miraflores grandchildren, and so on. Following all these majority requirements to the leaves shows that more than half of all leaves, namely voters, must support Miraflores. The inductive proof given above is preferable because it converts this intuition into a precise quantitative statement at every level.