## Archive for January, 2011

### How many votes did Alice get?

January 5, 2011

Last month’s Ponder This challenge was as follows:

In an election, Charles came in last and Bob received 24.8% of the votes. After counting two additional votes, he overtook Bob with 25.1% of the votes. Assuming there were no ties and all the results are rounded to the nearest promille (one-tenth of a percent), how many votes did Alice get?

And here‘s the solution. It was the easiest Ponder This ever.

__________

My solution:

Let $a, b, c \in \mathbb{N}$ be the number of votes gotten by Alice, Bob, and Charles, respectively. If Charles came in last, then $a > c$ and $b > c$. Since Bob received 24.8% of the votes and he was not the last one, then we deduce that Alice was the first with more than 50% of the votes. Therefore, we have $a > b > c$.

In the first counting, Bob got 24.8% of the votes. Since the results are rounded off, we have

$\displaystyle \frac{b}{a + b + c} = 0.248 + \delta_1$

where $|\delta_1| < 0.001$ is the round-off error. Hence, we obtain

$(0.248 + \delta_1) a + (\delta_1 - 0.752) b + (0.248 + \delta_1) c = 0$.

Multiplying both sides by $10^3$, and letting $s_1 := 10^3 \delta_1$, we get

$(248 + s_1) a + (s_1 - 752) b + (248 + s_1) c = 0$.

Note that, since $|\delta_1| < 0.001$, we have that $|s_1| < 1$. After counting two additional votes, Charles overtook Bob with 25.1% of the votes. Let $c' = c+2$ be the new number of votes that Charles got. Hence,

$\displaystyle \frac{c+2}{a + b + c + 2} = 0.251 + \delta_2$

where $|\delta_2| < 0.001$ is the round-off error. Thus, we have

$(0.251 + \delta_2) a + (0.251 + \delta_2) b + (\delta_2 - 0.749) c = 1.498 - 2 \delta_2$

and, multiplying both sides by $10^3$, and letting $s_2 := 10^3 \delta_2$, we get

$(251 + s_2) a + (251 + s_2) b + (s_2 - 749) c = 1498 - 2 s_2$

where $|s_2| < 1$. Since there were no ties and these two additional votes were enough for Charles to overtake Bob, then we have $c+2 > b > c$. As $b,c$ are natural numbers, we conclude that $b = c +1$.

Hence, we have a linear system of equations in $(a,b,c) \in \mathbb{N}^3$

$\left[\begin{array}{ccc} (248 + s_1) & (s_1 - 752) & (248 + s_1) \\ (251 + s_2) & (251 + s_2) & (s_2 - 749) \\ 0 & 1 & -1 \end{array}\right] \left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \left[\begin{array}{c} 0 \\ 1498 - 2 s_2 \\ 1 \end{array}\right]$

where $|s_1|, |s_2| < 1$. Note that $a,b,c$ must be natural numbers, which means that there should exist $(s_1, s_2) \in (-1,1)^2$ such that the linear system of equations has a solution in $\mathbb{N}^3$. Let us relax the system of equations by making $s_1, s_2 = 0$ and allowing the unknowns to take values in $\mathbb{R}$ rather than $\mathbb{N}$. Then, we obtain the new linear system of equations

$\left[\begin{array}{ccc} 248 & -752 & 248 \\ 251 & 251 & -749 \\ 0 & 1 & -1 \end{array}\right] \left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \left[\begin{array}{c} 0 \\ 1498 \\ 1 \end{array}\right]$

whose solution is $(a^*, b^*, c^*) \approx (84.664, 41.168, 40.168)$. Taking the floor of each component, we obtain a solution in $\mathbb{N}^3$

$(a,b,c) = (84, 41, 40)$.

Note that $41 / 165 \approx 0.248485$, and $42 / 167 \approx 0.251497$, meaning that $s_1 = 0.485 < 1$ and $s_2 = 0.497 < 1$, which are admissible values. Note also that $c+2 > b > c$. Hence, all the conditions are satisfied. We thus conclude that Alice got 84 votes.