Maths Olympiad Prep

Library / Argentina competition problems /20 of 20

Argentina competition problems

Algebra Difficulty 7.3 National Olympiad, round 2 Prove it Argentina

There were three candidates AA, BB, CC in the elections for a provincial governor. In the first round AA won 44%44\% of the number of votes given for BB and CC together and CC had fewest votes. No candidate had the majority necessary for a first-round win, so there was a second round for AA and BB. The voters in the second round were the same as in the first round, except p%p\% of the voters for CC who chose not to participate in the second round; pp is an integer, 1≤p≤1001 \le p \le 100. In addition the ones who voted for BB in the first round did so again in the second round.

A journalist claims that, knowing all the above, one can infer who the winner is with certainty. For what values of pp is he right?

Note. The winner in the second round is the one who obtains more than half of the total number of votes in the second round.

Solution

The journalist is right for p≥73p \ge 73 and wrong for p≤72p \le 72.

Let a,b,ca, b, c denote the number of votes for A,B,CA, B, C in the first round, and let N=a+b+cN = a + b + c be the total number of voters in this round. By hypothesis a=44100(b+c)=1125(N−a)a = \frac{44}{100}(b + c) = \frac{11}{25}(N - a), hence a=1136Na = \frac{11}{36}N; also c<ac < a.

The number of voters in the second round is N′=N−p100cN' = N - \frac{p}{100}c. There are (1−p100)c\left(1 - \frac{p}{100}\right)c persons who voted for CC in the first round and participate in the second round. For brevity call them and their votes additional. Since BB's supporters voted for him in both rounds, the most AA can achieve is that his own supporters vote for him again in the second round, and also the additional voters. So the maximum number of votes AA can get is amax=a+(1−p100)ca_{\text{max}} = a + \left(1 - \frac{p}{100}\right)c.

We are interested in the difference N′−2amaxN' - 2a_{\text{max}} (whose sign determines the chances of AA):
N′−2amax=(N−p100c)−2⋅1136N−2(1−p100)c=718N−200−p100c. N' - 2a_{\text{max}} = \left(N - \frac{p}{100}c\right) - 2 \cdot \frac{11}{36}N - 2\left(1 - \frac{p}{100}\right)c = \frac{7}{18}N - \frac{200-p}{100}c.

Let us say already here that the different outcomes for p≥73p \ge 73 and p≤72p \le 72 are due to the inequalities
127100+1136<718+128100<1136 \frac{127}{100} + \frac{11}{36} < \frac{7}{18} + \frac{128}{100} < \frac{11}{36}
(which hold as 127⋅11=1397<1400=100⋅2⋅7<128⋅11=1408127 \cdot 11 = 1397 < 1400 = 100 \cdot 2 \cdot 7 < 128 \cdot 11 = 1408).

Suppose that p≥73p \ge 73. Then 200−p100c<127100c<127100a=127100N\frac{200-p}{100}c < \frac{127}{100}c < \frac{127}{100}a = \frac{127}{100}N. Since 127100<1136<718\frac{127}{100} < \frac{11}{36} < \frac{7}{18}, it follows that 200−p100c<718N\frac{200-p}{100}c < \frac{7}{18}N, i.e. N′−2amax>0N' - 2a_{\text{max}} > 0. So AA cannot win even if he gets the maximum possible number of votes. Therefore BB wins with certainty, and the journalist is right.

For p≤72p \le 72 there are examples showing that either candidate can win. In this case 200−p100c≥128100c\frac{200-p}{100}c \ge \frac{128}{100}c.
Now the inequality 718<128100⋅1136\frac{7}{18} < \frac{128}{100} \cdot \frac{11}{36} (see above) implies 100128⋅718<1136N\frac{100}{128} \cdot \frac{7}{18} < \frac{11}{36}N. Take NN such that both sides of the inequality are integers differing by more than 1, for instance N=2lcm⁡(36,128)N = 2\operatorname{lcm}(36,128). Then an integer cc can be chosen so that 100128<718N<1136N\frac{100}{128} < \frac{7}{18}N < \frac{11}{36}N. The condition c<ac < a for the first round is satisfied. For this choice of cc we have 718N<128100c\frac{7}{18}N < \frac{128}{100}c, and 200−p100c≥128100c\frac{200-p}{100}c \ge \frac{128}{100}c was shown above for p≤72p \le 72, which implies N′−2amax<0N' - 2a_{\text{max}} < 0. So AA wins if he gets amaxa_{\text{max}} votes. This is possible if all of his supporters vote for him again, and also all additional voters.

On the other hand it is clear that BB is a possible winner for any pp, for instance if AA gets no votes at all (which is not excluded by the conditions). It is of more substance to note that BB can also win for p≤72p \le 72 even if all of AA's supporters vote for him again in the second round. Indeed if p≤72p \le 72 then c<ac < a implies N′=N−p100c>N−72100a=N−72100⋅1136N=3950NN' = N - \frac{p}{100}c > N - \frac{72}{100}a = N - \frac{72}{100} \cdot \frac{11}{36}N = \frac{39}{50}N. This is greater than 2a=1118N2a = \frac{11}{18}N, so if all additional votes go to BB then BB wins.

Remark. There are values of NN for which the situation can describe actual elections, for instance, N=1800000N = 1800000. Then a=1136N=550000a = \frac{11}{36}N = 550000 and, for p≤72p \le 72, the key number for the construction is 100128⋅718N=546875<550000\frac{100}{128} \cdot \frac{7}{18}N = 546875 < 550000. So there are plenty of (integer) choices for cc in [546875,550000][546875, 550000].

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.