Author |
Topic: Always Ahead (Read 5763 times) |
|
That Don Guy
Guest
|
In an presidential election between Willywutang and Billybutane, the winning candidate Willywutang has received n+k votes, whereas Billybutane has received n votes. (n and k are positive integers.) If ballots are counted in a random order, what is the probability that Willywutang's accumulating count will always lead his opponent's, and why?
The best answer to this I saw came out of Litton's Problematical Recreations (as have a number of "riddles" in the rec.puzzles forum...), although it dealt with putting checkers into a box:
[Solution begins here]
Every count in which Willywutang does not always have more votes counted than Billybutane has at least one number X where both have X votes (if the first vote counted is for Willywutang, there has to be a point where they are tied, otherwise Willywutang always had the lead; if the first vote counted is for Billybutane, there has to be a point where Willywutang ties and then passes Billybutane (otherwise it would contradict the fact that Willywutang has more votes)).
For every vote count that is tied for the first time at X votes, there is a vote count that is also tied for the first time at X votes that is the same as the first count except that the first X votes all switch (i.e. the Willywutang votes are noe for Billybutane, and vice versa). Thus, every "bad" vote count can be paired with exactly one other "bad" vote count, one of which begins with a Billybutane vote and the other beginning with a Willywutang vote.
Here's the "light bulb moment": every vote count that begins with a Billybutane vote is bad (as Billybutane has a 1-0 lead at that point). Therefore, the probability of having a "bad" vote count is twice the probabillity that the first vote counted is for Billybutane, or 2n / (2n+k), and the probability of Willywutang always being ahead is 1 minus this, or k / (2n + k).
[/color]
|
| « Last Edit: Oct 29th, 2003, 3:57am by william wu » |
 IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Re: Always Ahead
« Reply #1 on: Dec 15th, 2002, 3:19am » |
 Quote  Modify
|
Surprised more people weren't interested in this one.
[hidden comments on Don Guy solution begin here]
Nice. However, I would say that the true light bulb trick is in the second paragraph of your solution. The proof might be easier for others to understand with a graph, showing number of votes counted so far on the x-axis, and number of votes by which Willywutang is ahead on the y-axis. Tallying a count then corresponds to a random walk from either (1,-1) or (1,1) to (n+k,k), where the vertical position of the walk is either 1 plus or 1 minus the previous step. In this graphical interpretation, you reflect a "bad" counting path starting at (1,-1) across the x-axis, to pair it with an equivalent "bad" counting path starting from (1,1). This cunning observation is called the Reflection Principle:
Let (p,q) and (r,s) be positive integers and p < r. The number of random walk paths from (p,q) to (r,s) that touch or cross the x-axis is the total number of paths from (p,-q) to (r,s).
[hidden comments on Don Guy solution end here]
Consider the following apparently analogous problem, which if solved "normally", should offer an alternative way to prove the n / n + k result in the Willywutang vs. Billybutane voting problem, without using the trick in That Don Guy's solution:
There are n+k men and n women seated around a circular table (where n is a nonnegative integer and k is a positive integer) A man is special if, starting at his position and continuing clockwise around the table, the cumulative count of men always strictly exceeds the cumulative count of women. Prove: there are exactly k special men.
|
| « Last Edit: Dec 15th, 2002, 3:22am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Always Ahead
« Reply #2 on: Dec 16th, 2002, 10:46pm » |
Quote Modify
|
Another interesting thing to note is the probability of always being ahead is the slope of a straight line drawn from (0,0) to (2n+k,k) on the graph of # votes tallied vs. # votes willywutang is ahead by. I don't know if there's a special reason for this though.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
titan
Newbie
Posts: 33
|
|
Re: Always Ahead
« Reply #3 on: Oct 13th, 2013, 12:17am » |
Quote Modify
|
Can someone please explain the solution to:
There are n+k men and n women seated around a circular table (where n is a nonnegative integer and k is a positive integer) A man is special if, starting at his position and continuing clockwise around the table, the cumulative count of men always strictly exceeds the cumulative count of women. Prove: there are exactly k special men.
And "Let (p,q) and (r,s) be positive integers and p < r. The number of random walk paths from (p,q) to (r,s) that touch or cross the x-axis is the total number of paths from (p,-q) to (r,s)." - This is because of a property of brownian motion. right?
But how does it help here?
|
|
IP Logged |
|
|
|
titan
Newbie
Posts: 33
|
|
Re: Always Ahead
« Reply #4 on: Oct 13th, 2013, 1:25am » |
Quote Modify
|
I think I have understood this problem!! Thanks to http://mathforum.org/library/drmath/view/66860.html and posts here.
The question discussed on math forum is just p= 1=(n2+n3)/N
But, I'm not been able to get the numeric value of 2n/2n+k
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove