He stole my ball!
Six balls are at the front of the classroom, and six students are each assigned a different colored ball.
Then they are asked to go up one at a time and take the ball they were assigned.
However, the first student doesn't like the color he was assigned, so he picks randomly from the remaining five.
After that, each successive student takes the color they were assigned if it's available, otherwise they choose randomly from the remaining balls.
What is the probability that the last student gets the ball they were assigned?
Image credit : cdna.4imprint.com
The answer is 0.4.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Nice variation of the Airplane Seating puzzle , (in which the first person can also take their own seat at random).
I guessed 1/2 at first and then took the scenic route to the correct value. :/
Log in to reply
I, too, guessed 1/2 at first and then reread the problem more closely.
Ah yes, the scenic route! :-) And the airplane seating problem was indeed the inspiration... And this answer approaches that one for large n ... The only difference being that the first person can't choose his own... Anyway, glad you enjoyed it!
Log in to reply
What is the scenic route?
Log in to reply
@Atomsky Jahid – I just looked at cases with fewer balls and listed out all possible scenarios, and noticed the pattern that with n balls the desired probability was 2 1 − 2 ( n − 1 ) 1 = 2 ( n − 1 ) n − 2 , which is the generalization of Geoff's solution.
Suppose at a given instance there are n balls (and n people) left, of which k could be matched correctly. Call this situation S(n,k).
With probability n k there is a match for the next person. In that situation he picks his assigned ball, the new situation is S(n-1, k-1).
With probability n n − k there is no match for the next person. Given that situation he picks a random ball:
- the probability is n k that he picks a ball that still could be matched, bringing us also into S(n-1,k-1)
- the probability is n n − k that he picks a ball that could not be matched, bringing us into S(n-1,k)
So the total probability to end up in S(n-1, k-1) (and propagate the problem) is P p r o p a g a t e = n k + n n − k n k = n 2 2 k n − k 2 and the probability to end up in S(n-1, k) (and thus solve the problem) is P s o l v e = n 2 ( n − k ) 2 = n 2 n 2 − 2 k n + k 2
We also observe that the number n-k of remaining unmatchable balls will never increase, but may decrease.
In our case we start with n=5, k=4, (with one unmatchable ball: k=n-1) and our formula for the probability to propagate the problem to the next person becomes P p r o p a g a t e = n 2 2 ( n − 1 ) n − ( n − 1 ) 2 = n 2 n 2 − 1 . The probability to pass the problem on all the way to the last person then is 2 5 2 4 × 1 6 1 5 × 9 8 × 4 3 which can also be written as 5 × 5 × 4 × 4 × 3 × 3 × 2 × 2 4 × 6 × 3 × 5 × 2 × 4 × 1 × 3 = 5 × 2 6 × 1 = 0 . 6 . The last person thus has chance 1 − 0 . 6 = 0 . 4 to get his assigned ball.
The first person has a 5 4 chance of not picking the last person's ball (the only way the last person has any chance of getting the ball they were assigned).
After that, the fate of the last person is decided by either someone picking his ball or the first person's ball, which is always 50/50, whoever ends up locking in that fatal decision.
Therefore the probability the last person will get the ball he was assigned is
5 4 ⋅ 2 1 = 5 2 = 0 . 4