Subscribe via feed.

One large hat? (Similar ToM)

Posted by ragknot on October 21, 2012 – 8:33 am

Six gentlemen hung their hats in the cloakroom at their club. After imbibing for several hours, when it came time to leave, each had blurred vision, and in consequence,  five of them select one of the hats and leave,  but one guy has a large head and if his hat is still there, he will find his hat.  But his time to select his hat could be from first to last.  If his hat is not there, he still takes one.

What is the probability of no one getting the right hat?

This post is under “Tom” and has 8 respond so far.

8 Responds so far- Add one»

1. 1. ragknot Said：

If the large headed man is first to leave, then he will get his hat. If not the first, then he will get his hat unless a prior man got it. But even he does not get his, someone else, maybe before or after the big head man, might get his own.

2. 2. Chris Said：

Hi Ragknot. That’s a good question. Unfortunately it’s also quite a tough one. To get some idea of how tough it is see: Stacked Deck solution

Your hat problem might be less tedious than the Stacked Deck one, as the entire “deck” is dealt each time, but there again, there are more “hands” and “players”.

Of course, there may be a better approach that I’ve missed.

Obviously I’m talking about a non-number-crunching solution.

3. 3. ragknot Said：

Chris?
To Hard? Can you estimate the percent when all six fail to get their own hats?

4. 4. Chris Said：

Hi ragknot. Although I haven’t, I could do it exactly with number crunching (or a large sheet of paper).

5. 5. ragknot Said：

I emailed someone with my “computations”.

Ok, if this is too hard, I say 18.41% of the time, no one will get their own hat.

As an engineer, I don’t use “probability”, but I do like to see how that would be used.

6. 6. Chris Said：

Hi ragknot. I am going to try to solve the general problem. I think it’s an excellent extension to the original “Hat pick” problem.

I have considered a sub-problem that may (or may not) prove useful, as follows:

A derangement is a permutation of a set such that a specified number of the elements remain in their original, “fixed”, position. A full derangement is one where none of the elements are in their original position. A partial derangement is one where at least one element is in its original position.

Let d(n,m) be the number of derangements of n elements with m (m ≤ n) fixed elements. Let d(n) = d(n,0) for readabilty.

If a particular m elements are fixed, then there are d(n-m) full derangements of the remaining elements. There are c(n,m) = n!/((n-m)! m!) ways of choosing exactly m fixed elements. So d(n,m) = c(n,m) d(n-m).

Every permutation must be a full or partial derangement and vice versa. So if we add up all the derangements (with m = 0, 1, 2…, n) we must also have exactly included all n! permutations of the n elements => n! = Sum(d(n,m)) =>
n! = Sum(c(n,m) d(n-m)) = c(n,0)d(n) + c(n,1) d(n-1) + … + c(n,n) d(0)

Bearing in mind that there are several formulae for d(n), a whole bunch of other whacky identities can be found. e.g. d(n) = [n!/e] where [] => nearest integer. So n! = c(n,0) [n!/e] + c(n,1) [(n-1)!/e] + … + c(n,n) [0!/e].

7. 7. ragknot Said：

Wow, that does seem hard. But I don’t understand how to do that, but tell me what you think of my solution.

Well, this is “randomness” to me, I can can understand that your method should get very accurate. But I understand that to get more accuracy, it would take a little more time, but if accuracy to the nearest 1 percent would be good enough for this problem.

My method? I use VBA in Excel.
First, I write a subroutine to give me a random number from 1 to 6.

Second, I make Man(1) to Man(6) and Hat(1) to Hat(6)

Third, I write a Swap that will Swap the hats around so that Hat(1) will have about 1/6 of the provability of being 1 like it began, but all 6 hats will have different numbers, and may or may not be the same value as it began.

Forth, I test to see if at least one of the six men have the right hat, ie., does Man(1)’s Hat(1) =1?

Fifth, Did at least one of the the six men have the right hat? Then it’s success, if none got the right hat then it’s a failure.

Sixth, I do steps 3 to 5 over and over and count “successes” and “failures”, and figure the percents.

This was my solution to the first ToM. Then second, with the Large Head Man, it is very similar. I made a random number 1 to 6 be the large man and add this part. If he is number one, he will get his hat for a quick success, If he is number 3, then if man(1) and man(2) gets their hat and don’t get hat(3) then the Large Head man will get his hat. This extra step was not difficult, and Excel VBA can to 10 million test for success vs. failure, and I get …

Success =81.6080% and Failure= 18.3920%

Next, What is I said at least two men hat to get the correct hat for a success?. That would still be easy
step… or what if 3,4,5 or 6, had to get the right hat for a success? Well, that would be pretty easy with an extra step in my VBA.

8. 8. Chris Said：

Hi all, I finally found the time to do this.

A derangement is a permutation of (distinguishable) items such that none of the items are in their original position. If d(n) is the number of derangements of the n hats, then (as I showed in the recent “Hat Pick” problem) there is a recursion:
d(n) = (n-1)(d(n-1) + d(n-2)) => d(n) is divisible by n-1.

To simplify the typing effort, I’ll use the six men case for discussion. If the six men always pick in the order ABCDEF and none of them pick their own hat, then a typical pick order will be bcdefa, i.e. A picks b, B picks c …
a will never be in the A position, b will never be in the position B etc.

For the derangements, a is equally likely to be in position B,C,D,E or F, and similarly for the other hats. e.g. for 6 hats, the probability of hat x being in the X position is 0, and for being in a particular one of the other positions is 1/5.

Now for the case of there being a large headed man (= LHM from now). The possibilities must be a subset of the d(6) = 265 derangements.

If A is the LHM, then for all cases, a will be in position B,C,D,E or F and he will pick it. If B is the LHM then b will be in position A in 1/5 th of the derangements i.e. B will be unable to pick his own hat 1/5 th of the time. If C is the LHM, then c will be in position A or B in 2/5 ths of the derangements, etc. If F is the LHM, then hat f will be in position A,B,C,D or E for all 5/5 ths of the derangements (and so not pickable by F).

Let p(6) = d(6)/6! ≈ 0.36805555…. As it is equally likely that any of the six men is the LHM, we get, altogether, that the probability of none of the men picking their own hat is (1/6)(0/5 + 1/5 + 2/5 + 3/5 + 4/5 + 5/5)p(6) = p(6)/2 ≈ 0.184027777…. That shows that Ragknot’s Monte Carlo computations are pretty good, but not up to the 10 decimal places that he sometimes desires

This easily generalises to n hats and one LHM:
(1/n)(0+1+2+…+(n-1))/(n-1)p(n) = p(n)/2, where p(n) = d(n)/n! ≈ 1/e

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0