Maths Olympiad Prep

Library / /17 of 17

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, 1p1001 \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 p73p \ge 73 and wrong for p72p \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(Na)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=Np100cN' = N - \frac{p}{100}c. There are (1p100)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+(1p100)ca_{\text{max}} = a + \left(1 - \frac{p}{100}\right)c.

We are interested in the difference N2amaxN' - 2a_{\text{max}} (whose sign determines the chances of AA):
N2amax=(Np100c)21136N2(1p100)c=718N200p100c. 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 p73p \ge 73 and p72p \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 12711=1397<1400=10027<12811=1408127 \cdot 11 = 1397 < 1400 = 100 \cdot 2 \cdot 7 < 128 \cdot 11 = 1408).

Suppose that p73p \ge 73. Then 200p100c<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 200p100c<718N\frac{200-p}{100}c < \frac{7}{18}N, i.e. N2amax>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 p72p \le 72 there are examples showing that either candidate can win. In this case 200p100c128100c\frac{200-p}{100}c \ge \frac{128}{100}c.
Now the inequality 718<1281001136\frac{7}{18} < \frac{128}{100} \cdot \frac{11}{36} (see above) implies 100128718<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 200p100c128100c\frac{200-p}{100}c \ge \frac{128}{100}c was shown above for p72p \le 72, which implies N2amax<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 p72p \le 72 even if all of AA's supporters vote for him again in the second round. Indeed if p72p \le 72 then c<ac < a implies N=Np100c>N72100a=N721001136N=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 p72p \le 72, the key number for the construction is 100128718N=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.