wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Always Ahead
        
(Message started by: That Don Guy on Dec 5^th, 2002, 12:03pm)

Title: Always Ahead
Post by That Don Guy on Dec 5^th, 2002, 12:03pm

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][hide]
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][/hide]

Title: Re: Always Ahead
Post by william wu on Dec 15^th, 2002, 3:19am

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.

Title: Re: Always Ahead
Post by william wu on Dec 16^th, 2002, 10:46pm

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.

Title: Re: Always Ahead
Post by yoyoy on Oct 13^th, 2013, 12:17am

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?

Title: Re: Always Ahead
Post by yoyoy on Oct 13^th, 2013, 1:25am

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