3
$\begingroup$

50 people have voted in an election, in which they are two candidates, and 25 people have voted for one candidate, and 25 people have voted for the other. You don’t know this yet, and are counting the votes, by looking at the ballots in sequence. What is the number of sequences for which, as you count the votes, neither candidate is ever ahead of the other by more than 15 votes, but the end result is a tie?

I just want to know if I'm doing it right by:

C(10) * C(15) + C(11) * C(14) + C(12) * C(13) and flip it to get the rest.

But I think there is some overcounting - for example,

All three will count some form of ENENENENENENENE ...

$\endgroup$
2
  • 1
    $\begingroup$ What does $C(10)$ mean? or $C(15)$ etc? $\endgroup$ Commented Mar 15, 2019 at 23:00
  • $\begingroup$ C(10) - the 10th Catalan Number $\endgroup$ Commented Mar 15, 2019 at 23:08

1 Answer 1

Reset to default
1
$\begingroup$

Hint: You can use the reflection principle. Let

  • $A$ be the orderings where the first candidate is at some point ahead by $16$

  • $B$ be the orderings where the second candidate is at some point ahead by $16$.

Note $A$ and $B$ are disjoint (why?), so the desired answer is $\binom{50}{25}-|A|-|B|$. To count $A$, realize each ordering as a lattice paths, where votes for the first candidate are an up step and votes for the second candidate are a right step, find the first time this path hits the line $y=x+16$, and reflect the path through that line afterwards. While the original path ended at $(25,25)$, the reflected path will end at$\dots$ I will let you do the rest.

$\endgroup$
5
  • $\begingroup$ Why do I use y = x + 16? $\endgroup$ Commented Mar 15, 2019 at 23:15
  • $\begingroup$ The $y$ coordinate is the number of ballots for candidate one so far. The $x$ coordinate is the number of ballots for the other candidate. Once $y-x=16$, that means the first candidate is ahead by $16$. $\endgroup$ Commented Mar 15, 2019 at 23:17
  • $\begingroup$ How would it look if $A$ and $B$ were not disjoint ($d<n/3$, where $d$ is deviation from the "diagonal")? Can the reflection method be somehow adapted for this case? $\endgroup$ Commented Mar 15, 2019 at 23:34
  • $\begingroup$ @user There is a nice answer! I'd be happy to share it if you ask it as a separate question. $\endgroup$ Commented Mar 15, 2019 at 23:36
  • $\begingroup$ math.stackexchange.com/q/3149930 $\endgroup$ Commented Mar 15, 2019 at 23:48

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.