Solving the Hat Puzzle: Chance of Getting Right Hat

[musicgold]

Hi,

I am struggling with the following puzzle.

Six people, on their way out from a restaurant, waiting to collect their hats. The attendant mixes up the tags and hands the hats over randomly. What are the chances that at least one of them gets the right hat?

I tried to find the probability of no one getting his hat. I reconfigured the problem as follows: each of them picks a hat, one by one, from the hat pool, without looking at the pool.

First I tried to calculate the following probabilities. However, I am not able to go beyond the first person. In the case of the second person, I have two cases 1. #1 chose his hat, and 2. his hat is still in the pool.
I am not sure how to find his probability.

P (1st not getting his hat) = 5/6
P(2nd not getting his hat ) =
P(3rd not getting his hat ) =
….

How should I go about this problem?

Thanks.

 

[chiro]

Hey musicgold.

The best way to think about this in terms of no-one gets the hat (which is what you have done). Probabilistically P(Someone-gets a ticket) = 1 - P(No-one gets a ticket).

You had the right idea with what you are doing: the only thing to use though are the multiplicate laws of probability, and note how the state-space changes with each player.

For the first player we have probability of not getting a ticket = 5/6. For second player we have five choices, and four of them are not the right one which gives 4/5. For third player we have 4 choices which gives probability 3/4 and so on.

Now each of these things is independent so we multiply them to give the probability that no-one actually gets their ticket which is:

P(No-one gets their ticket) = 5/6 * 4/5 * 3/4 * 2/3 * 1/2 * 1 (The last one will definitely not get their ticket with certain probability) = 120/720 = 1/6.

P(Someone gets their ticket) = 1 - P(No-one gets their ticket) = 1 - 1/6 = 5/6.

 

[musicgold]

Chiro,

I did think about this approach, and that is why I was trying to calculate those probabilities.

However, your solution assumes that, #2's hat is still in the pool when his turn comes, which may not be always true. I think we need to use conditional probabilities here.

 

[chiro]

Chiro,

I did think about this approach, and that is why I was trying to calculate those probabilities.

However, your solution assumes that, #2's hat is still in the pool when his turn comes, which may not be always true. I think we need to use conditional probabilities here.

Yes you are absolutely right.

So to handle this you need to basically consider for the nth person n-1 conditional statements of whether the n-1 people before them has their ball. If one of them has their ball then probability is 1, otherwise it's the probability stated above.

So you are going to get basically a 1 probability or the probability mentioned at each stage. Notice by stage I mean like 5/6 for stage 1, 4/5 for stage 2 and so on just like the post above.

You can represent this with some really Heaviside functions that are used to factor in the if statements if you want to get mathematical, or you can just write all the conditional statements down for the conditioning on all levels as general as you can.

 

[haruspex]

Generalise to n people. Let P_n be the prob no-one gets the right hat. Consider a slightly different scenario: n people, n hats, but one of the hats belongs to none of the n. Now let the prob of none getting the right hat be Q_n.
In the first scenario, the first person takes a hat; if they get the wrong one we're in the second scenario:
P_n = Q_n-1(n-1)/n
In the second scenario, consider the person whose hat is missing; if they get the spare hat then we're back in the first scenario, and if not we continue in the second:
Q_n = P_n-1/n +Q_n-1(n-1)/n
With a bit of shuffling:
n(P_n-P_n-1) = -(P_n-1-P_n-2)
Easy from there.