Two candidates participated in an election with $p+q$ voters. Candidate $A$ received $p$ votes and candidate $B$ received $q$ votes, with $p>q$. During the counting, only one vote is recorded at a time on a board. Let $r$ be the probability that the number associated with candidate $A$ on the board is always greater than the number associated with candidate $B$ throughout the entire counting process.

a) Determine the value of $r$ if $p=3$ and $q=2$.

b) Determine the value of $r$ if $p=1010$ and $q=1009$.
Solution

a) We can make lists with the letters $A$ and $B$ representing the possible orders of votes counted. For example, the list $A A B A B$ indicates that the first two and the fourth votes counted were for candidate $A$, the third and fifth for candidate $B$. There are exactly 10 lists with 3 letters $A$ and two letters $B$:

| A | A | A | B | B | A | A | B | A | B |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| A | B | A | A | B | B | A | A | A | B |
| A | A | B | B | A | A | B | A | B | A . |
| B | A | A | B | A | A | B | B | A | A |
| B | A | B | A | A | B | B | A | A | A |

Of these 10 lists, in only two the number of letters $A$ when counted from left to right is always greater than the number of letters $B$, namely,

## $A A A B B$ and $A A B A B$

Therefore,

$$
r=\frac{2}{10}=\frac{1}{5}
$$

b) Let's call a tie a moment during the counting when the number of votes for both candidates is the same. For candidate $A$ to always be ahead, there certainly cannot be any ties. Any count in which the first vote was for candidate $B$ will have a tie, because we know that in the end the number of votes for $A$ is greater and if we do not have a tie at any point, candidate $B$ will win. For any sequence that starts with $A$ and reaches a tie, associate another sequence by swapping the letters $A$'s and $B$'s up to the position of the first tie. For example, in the sequence

$A A A B B A B B A B$.

We have ties at the eighth and tenth counts. The position of the first tie is the eighth, and we will swap the previous sequence to

$$
B B B A A B A A A B
$$

With this operation, note that the quantities of letters $A$'s and $B$'s do not change and now the sequence starts with the letter $B$. With this operation, for every sequence that starts with $B$, which we already know has ties, we can uniquely associate another sequence starting with $A$ with ties, and vice versa. Thus, the number of sequences with ties starting with $A$ is equal to the number of sequences starting with $B$. With even more reason, we can conclude that the probability of a sequence starting with $A$ and having ties is equal to the probability of a sequence starting with $B$. Since there are $q$ letters $B$ in a universe of $p+q$ letters, the probability of a sequence starting with $B$ is $\frac{q}{p+q}$. Thus, as every sequence with ties starts with $A$ or $B$, the probability of choosing, among the possible sequences of $p$ letters $A$ and $q$ letters $B$, one with ties is $\frac{q}{p+q}+\frac{q}{p+q}=\frac{2 q}{p+q}$. Finally, the value of $r$ is the complement of this probability:

$$
\begin{aligned}
r & =1-\frac{2 q}{p+q} \\
& =\frac{p-q}{p+q} \\
& =\frac{1}{2019}
\end{aligned}
$$

Note: The result presented in this problem is known as Bertrand's Ballot Theorem, in reference to the mathematician Joseph Louis François Bertrand.