Here's a problem that my dad and I came up with today:
n friends are drawing straws to see who will be the designated driver. Instead of drawing straws the usual way, however, a guy draws a straw, and if it's shorter than the rest the guy gets/has to be the designated driver. If it's not shorter than the rest, however, the guy puts the straw back into the pile. Is this a fair game? If not, which person should you be if you don't want to draw the shortest straw?
skip to main |
skip to sidebar
Thoughts and experiences from a computer science chick, juggler and powder hound.
4 comments:
Do we have any information about the number of straws?
And, one question about the wording. Does the person have to be the designated driver if he draws a straw such that there is no straw shorter than his, or does he have to be the designated driver if his straw is strictly the shortest straw? This really matters if there's a small number of straws, as the game would last for an infinite number of turns if there is one straw and the rule is the second of the two that I've given.
One more thing - are the lengths of the straws distinct?
Okay, the length of the straws isn't the point of the problem. There are n -1 "long" straws and 1 short straw. They keep drawing until somebody gets the short one. The guy who gets the short straw is the designated driver. For you, I'll say that the long straws are all 5 cm and the short one is 3 cm (so they can find out which one is shortest).
Yes, that answers my question. It's definitely important, though - sure, it's not the "point" of the problem, but the problem would be vastly different if there were 3 straws as opposed to n^3, say, or 3 short straws and 20 long ones, et cetera.
Here's my solution (I wrote it quickly, so don't get angry if I'm wrong!):
No, the game is not fair.
Take the first person to draw. There is a 1/n chance that he will draw the shortest straw on the first turn. The next possibility for the person to draw the shortest straw will be if the first n people (including himself) do not draw the shortest straw, and he then draws the shortest straw, on his second turn.
Now, take the kth person to draw. The probability of this person getting a first turn will be the 1/(n^(k-1)), which is the probability that none of the k - 1 people before this person draw the shortest straw.
I won't give the details of the summing of the infinite series here, but this method shows that the probability for the kth person to draw the shortest straw is given by
(n - 1)^(k - 1) * n^(n - k)
----------------------------
n^n - (n - 1)^n .
This shows that the game is not fair, and that, if you do not want to draw the shortest straw, you should be the nth person to draw.
Post a Comment