wu :: forums
« wu :: forums - Always Ahead »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 7:03am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Icarus, william wu, SMQ, ThudnBlunder, Eigenray, towr, Grimbal)
   Always Ahead
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Always Ahead  (Read 5744 times)
That Don Guy
Guest

Email

Always Ahead  
« on: Dec 5th, 2002, 12:03pm »
Quote Quote Modify Modify Remove Remove

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
*****





   
WWW

Gender: male
Posts: 1291
Re: Always Ahead  
« Reply #1 on: Dec 15th, 2002, 3:19am »
Quote Quote Modify 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
*****





   
WWW

Gender: male
Posts: 1291
Re: Always Ahead  
« Reply #2 on: Dec 16th, 2002, 10:46pm »
Quote Quote Modify 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 Quote Modify 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 Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board