How many election outcomes in the race for class presidents are there if there are five candidates and $40$ students in the class and
(a) Every candidate receives at least two votes?
My attempt: Total voters = $40$ = votes to be cast
Step 1: Give each candidate $2$ votes: There is one way to do this leaving $30$ votes remaining.
Step 2: Distribute the remaining $30$ votes to the five candidates: $\binom{30+3}{4}=\binom{33}{4}=40,920$ outcomes.
So there are $40,920$ outcomes where every candidate receives at least
two votes.
(b) One candidate receives at most $1$ vote and all the others receive at least two votes?
My attempt:
There will be two cases to this problem: either one candidate receives $0$ votes and all the others receive at least two votes, OR, one candidate receives only $1$ vote and all the others receive at least two votes.
Case 1:
Step 1: Choose candidate to receive no votes: $5$ options
Step 2: Give each of the four remaining candidates $2$ votes: There is $1$ way to do this leaving $40-8=32$ remaining votes.
Step 3: Distribute remaining $32$ votes to four candidates: $\binom{32+3}{3}=\binom{35}{3}$
Case 2: One candidate receives $1$ vote and all the others receive at least $2$ votes
Step 1: Choose candidate to receive $1$ votes: $5$ options
Step 2; Give candidate $1$ vote: There is one way to do this and there are $39$ votes remaining.
Step 3: Give each other candidate $2$ votes: There is only one way to do this and there are $31$ votes remaining.
Step 4: Distribute remaining $31$ votes to the four other candidates: $\binom{31+3}{3}=\binom{34}{3}$.
So there are $5\times \binom{35}{3}+5\times \binom{34}{3} =
> 32,725+29,920=62,645$ outcomes.
(c) No candidate receives a majority of the vote?
This would mean that no candidate receives at least $20$ votes.
Total outcomes with no restrictions: $\binom{40+4}{4}=\binom{44}{4}=135,751$ outcomes.
Consider the complement where one candidate receives at least $20$ votes.
Step 1: Choose candidate to receive at least $20$ (majority) votes: $5$ options
Step 2: Give this candidate $20$ votes: This leaves $20$ votes remaining.
Step 3: Distribute the remaining $20$ votes to the five candidates: $\binom{20+4}{4}=\binom{24}{4}$.
So there are $5\times \binom{24}{4}=53,130$ outcomes where one candidate receives a majority of the votes.
This gives us that $135,751-53,130=82,621$ outcomes where no candidate
receives a majority of the votes.
(d) Exactly three candidates tie for the most votes?
This is the problem that I am unsure of how to solve. And if it would be possible for someone to validate that my methodology for the other 3 parts of this problem are correct.
Best Answer
Your first two answers are correct.
Your only error was that the word majority means more than half. Thus, you should give the candidate who wins the majority $21$ votes, leaving $19$ votes to distribute to the five candidates in $$\binom{19 + 5 - 1}{5 - 1} = \binom{23}{4}$$ ways, which gives $$\binom{44}{4} - \binom{5}{1}\binom{23}{4}$$ possible outcomes.
Notice that the three winning candidates must each receive at least nine votes since if they each had only eight votes, at least one of the other two candidates would receive at least eight votes, which means there would be either be a five-way tie for first or one of the other two candidates would win the race if he or she received more than eight votes.
However, if three candidates each win nine votes, that does not ensure that there will be exactly three first place finishers since another candidate could win nine or more votes. Even if three candidates each win ten votes, that does not ensure that there will be exactly three first place finishers since one of the other two candidates could receive ten votes, which would produce a four-way tie. However, if three candidates tie with eleven or more votes each, that guarantees exactly three candidates tie for first place since no other candidate could receive more than seven votes. Therefore, we will consider three cases, depending on whether the top three candidates receive exactly nine, exactly ten, or at least eleven votes.
Case 1: Exactly three candidates tie for first with nine votes each.
For this to happen, neither of the other two candidates can receive more than eight of the remaining $40 - 3 \cdot 9 = 13$ votes. There are $\binom{5}{3}$ ways to select which three candidates tie for first. That leaves $13$ votes to distribute to the other two candidates in such a way that neither receives more than eight votes. This can occur in four ways: $(5, 8), (6, 7), (7, 6), (8, 5)$. Hence, the number of possible outcomes in this case is $$4\binom{5}{3}$$ If you want to take a more formal approach to the distribution of the $13$ votes not received by the three winning candidates, we must find the number of solutions of the equation $$x_1 + x_2 = 13$$ in the nonnegative integers subject to the restrictions $x_1, x_2 \leq 8$. Without restriction, the equation has $$\binom{13 + 2 - 1}{2 - 1} = \binom{14}{1}$$ solutions. At most one of the other two candidates could receive nine or more votes. There are two ways to choose this candidate. If we give that candidate nine votes, there are $$\binom{4 + 2 - 1}{2 - 1} = \binom{5}{1}$$ ways to distribute the remaining four votes, leaving $$\binom{14}{1} - \binom{2}{1}\binom{5}{1} = 14 - 2 \cdot 5 = 4$$ ways to distribute the remaining thirteen votes so that neither candidate receives more than eight votes.
Case 2: Exactly three candidates tie for first with ten votes each.
There are $\binom{5}{3}$ ways to select the three winning candidates. The remaining ten votes must be distributed among the remaining two candidates in such a way that neither of them receives all ten of the remaining votes. There are nine ways to distribute the remaining ten votes so that neither candidate receives all ten votes since a particular candidate may receive at most nine and must receive at least one of those votes. Hence, the number of possible outcomes in this case is $$9\binom{5}{3}$$ If you want to take a more formal approach to distributing the ten votes not received by the winning candidates, we must find the number of solutions of the equation $$x_1 + x_2 = 10$$ in the nonnegative integers subject to the restrictions that $x_1, x_2 \leq 9$. Without restrictions, there are $$\binom{10 + 2 - 1}{2 - 1} = \binom{11}{1}$$ ways to distribute those votes. There are two ways to distribute all ten of the votes to one of these candidates, giving $$\binom{11}{1} - \binom{2}{1} = 11 - 2 = 9$$ admissible ways to distribute the votes to the other two candidates. Equivalently, we must find the number of solutions of the equation $x_1 + x_2 = 10$ in the positive integers, of which there are $$\binom{10 - 1}{2 - 1} = \binom{9}{1} = 9$$ since we must place one addition sign in the nine spaces between successive ones in a row of ten ones.
Case 3: Exactly three candidates tie for first and each of those candidates receives at eleven votes.
There are $\binom{5}{3}$ ways to select which three candidates tie for first. That leaves us with seven votes to distribute among the other two candidates candidates, which can be done in $$\binom{7 + 2 - 1}{2 - 1} = \binom{8}{1} = 8$$ ways. Hence, there are $$\binom{5}{3}\binom{8}{1}$$ possible outcomes in this case.
Case 4: Exactly four candidates each receive $12$ votes.
There are $\binom{5}{3}$ ways to select which three candidates tie for first. That leaves us with four votes to distribute among the other two candidates, which can be done in $$\binom{4 + 2 - 1}{2 - 1} = \binom{5}{1} = 5$$ ways. Hence, there are $$\binom{5}{3}\binom{5}{1}$$ possible outcomes in this case.
Case 5: Exactly three candidates tie for first with $13$ votes each.
There are $\binom{5}{3}$ ways to select which three candidates tie for first. This leaves us with one vote to distribute between the other two candidates which can be done in $\binom{2}{1} = 2$ ways. Hence, there are $$\binom{5}{3}\binom{2}{1}$$ possible outcomes in this case.
Total: The number of ways exactly three candidates can tie for first is $$\binom{5}{3}\left[\binom{14}{1} - \binom{2}{1}\binom{5}{1}\right] + \binom{5}{3}\left[\binom{11}{1} - \binom{2}{1}\right] + \binom{5}{3}\binom{8}{1} + \binom{5}{3}\binom{5}{1} + \binom{5}{3}\binom{2}{1} $$