## Hats (One is a LARGE size)

Posted by ragknot on October 27, 2012 – 6:38 pm

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, all of them picked up one of the hats.

*One guy has a big head and hat, and if his hat is still there, he will get it!*

What is the probability of that at least two men get their own hats?

October 28th, 2012 at 8:08 pm

First man has six choices and so that is 1 out of six, second man has 5 choices so 1 out of 5.

1/5*1/6=1/30

October 29th, 2012 at 3:56 am

Just to clear things up: Are you saying that each will pick up a random hat (including the big guys hat) but that the big guy will only pick up his own hat if it is there but otherwise somone elses hat? Also I assume the answer has to account for them leaving in an unknown order?

October 29th, 2012 at 5:44 am

Hi Werner. That’s not quite right. As you say, bighead will always pick his own hat if it’s available. In all other cases, the picks are completely (and uniformly) random and so anyone could pick any of the remaining hats.

I believe that this is a difficult question to answer theoretically, but almost trivial to solve (exactly) with a computer. However, if the number of hats were extremely large, then even a computer wouldn’t be able to handle it exactly.

October 29th, 2012 at 5:54 am

… of course, it may be that these hat problems are simpler than I sometimes think they are. i.e. I think that the partial derangements that I wrote about http://trickofmind.com/?p=1684#comment-17704 may be the trick needed.

October 29th, 2012 at 5:54 am

Right so far.

A. 6 guys, numbered 1 to 6

B. One random guy has large head.

C. As the guys leave, they take a random hat,except

if it is the large head man, he gets his if it is still there, but it it is not, he takes a random hat.

I computed that about 81 1/2 Percent of the time, there will be at least one guy to get his own hat. But what percent for two getting their own hats?

October 31st, 2012 at 5:54 am

Excel VBA function, usually 10000 tries get a good solution. More tries increase the accuracy.

October 31st, 2012 at 6:49 am

Are these testing equality?

If LargeMan Hat(LargeMan) Then

If c d Then

October 31st, 2012 at 9:01 am

Hi cazayoux. The posting got messed up by the html interpreter. Should now be fixed.

I have only tested the code very briefly – just enough to make sure that Excel doesn’t complain about anything.

October 31st, 2012 at 2:05 pm

This problem needs a fair amount of effort to solve. Some of the considerations follow. I will repeat some parts of my other posts so it’s reasonably self-contained.

To start with, I’m going to ignore the LHM (large headed man).

In case it isn’t clear, the men alway pick in the order ABCDEF. A is simply the first man to pick a hat etc. Then it is easy to write down the hat picking order as e.g. adfcbe (where a => A’s hat etc.) and that means A picked a, B picked d, C picked f etc. It might have been wiser to use numbers rather than letters, but for consistency with my other posts, I’ll stick with letters.

If no-one picks his own hat, then the pick sequence will be such that hat x isn’t in the X position. Any such sequence is a (full) derangement of abcdef. In the adfcbe example, we have a partial derangement, as hat a is in the A position.

If we have n hats, and the pick order is such that m of the hats are picked by their owner, then there are d(n,m) ways that can happen. If m = 0, then write d(n) = d(n,0) for convenience. In the original “Hat Pick” problem, we found that d(1) = 0, d(2) = 1, d(3) = 2, d(4) = 9, d(5) = 44, d(6) = 265. It is useful to define d(0). Because d(n) obeys the recursion d(n) = (n-1)( d(n-1) + d(n-2)), we have

d(2) = (2-1)(d(1) + d(0)) => d(0) = 1. That also follows from d(6,6) = c(6,6) d(6-6) = d(0), because c(6,6) = 1 and d(6,6) = 1. NB for the latter, refer to http://trickofmind.com/?p=1684#comment-17704 where I showed that

d(n,m) = c(n,m) d(n-m), where c(n,m) = n!/((n-m)! m!)

As we are dealing with n = 6, we may as well note that as m varies from 0 to 6,

that c(6,m) = 1, 6, 15, 20, 15, 6, 1

The probability of a random permutation of n items where m are not moved is

p(n,m) = d(n,m)/n! = c(n,m) d(n-m)/n!. In the hat case, that’s the probability of exactly m men getting their own hats. More numbers (NB 720 = 6!):

Aside: If pick randomly, the average number of correctly drawn hats is

(0*265 + 1 *264 + 2*135 + 3*40 + 4*15 + 5*0 + 6*1)/720 = 1

That 1 is the average number is generally true.

The probability of at least two men getting their own hats is:

p(6,2) + p(6,3) + p(6,4) + p(6,5) + p(6,6) = (135 + 40 + 15 + 0 + 1)/720 = 191/720 = 0.26527777…

Or slightly simpler, 1 – (p(6,0) + p(6,1)) = 1 – 265/720 – 264/720 = 191/720

However, I’ve ignored the LHM. To deal with him, we have to revise the p(6,m) table to take the LHM’s behaviour into account. I’ll do that in a separate post.

October 31st, 2012 at 8:01 pm

Chris, Here is an example that shows what I think you did not get. The six men “assigned” random hats.

Like this…

—–Men#—-Hat#

—– 1——- 5

—– 2—— 2

—– 3—— 3

—– 4—— 6

—– 5—— 1

—– 6—— 4

Then the Large hat Man is assigned a random # so

Large Hat man is #4, his hat “assigned” to him is #6

For some reason the “Chris method” skips this because

4 is less that 6. But in this case the Large hat will go to the large headed man.

If his hat is not gone at his number, he will swap the hat his was “assigned” with his hat. His hat was “assigned” to man 6. He will get his HAT because man 6 has not got his large hat yet.

This will improve the chance of the man 6 because he was going to get the large hat.

October 31st, 2012 at 9:28 pm

Hi ragknot. I haven’t solved the problem with the large headed man – I did say so in my post. The reason is that even without the major complication of the LHM, the problem needs a fair amount of work. Including the LHM requires quite a lot more effort.

THe other problem you posted is far simpler, but my solution was quite long even for that.

I’ll be at least 24 hours (I’m very busy tomorrow) before trying for the LHM version. If my solution (assuming I actually can do it) doesn’t agree with your computer solution, then I’ll check out your code then.

If you can tweak your code to deal with the non-LHM version, you should be able to confirm my result. I’m 99.99% confident that my answer is correct.

October 31st, 2012 at 9:34 pm

I think the “reasoning” of this is not hard. If you wanted to test this without a computer, roll a dice.

First, there are six men, since they are first, just number them straight 1 to 6, and this will give their leaving the bar. Roll the “die” and give the men their hat number, but don’t use one you have already put down on a man. Then chose one of the six to be the large headed man, with another dice roll.

Then man one leaves and takes the hat number you “assigned” to him. Each man take what was assigned him. If man 2 gets hat 2, then it was right. When the large headed man number is ready to go, he will look for his hat, and if it is still there, he will get it instead of the one you randomly assigned. Also the one that was assigned to the large man him will be swapped to the man that was assigned the large hat. This means the large man has greatly increased his probability if he had a low number and the man that had the large hat assigned to him will improve his chances if the large man swaps to get his.

November 1st, 2012 at 4:40 am

Hi ragknot. In your last post you have simply replaced blurred vision with a die to provide the randomising. It isn’t reasoning and it provides no insight.

To get an answer experimentally would take tens of thousands of die rolls, and then you’d only get about two or three significant figures. Personally I’d run the simulator at least ten million times (after debugging with ten thousnad trials) to get decent accuracy. I’ll re-post a randomising function that can do that.

If the problem was a real-life engineering problem, then I’d happily use a computer to solve it. For more complex problems, computing techniques are the only viable ones.

It isn’t a real-life problem though, the actual probability is just some number, and that number, as such, is of no interest whatsoever. I only care about the theoretical method of finding it.

For this problem, the methods are the only thing of interest to me. The computed result is only useful as a check that no mistakes have been made.

Don’t misunderstand, I think computers and the Monte Carlo technique are wonderful. I also love programming as an end in itself – regardless of whether or not the program serves any genuinely useful purpose to me.

—-

Here’s a couple of very useful functions

November 1st, 2012 at 6:07 am

Well when you can get that complex system of getting approximately 44.90% instead of 40.80% of at least two men getting their “correct” hats, then it will be closer to right I think.

November 1st, 2012 at 10:53 pm

I figured out a quick way, and it should be perfect not a approximation. (table at end)

Each includes a man with a large hat.

Look at line 2, 44.93% of the time, st least two men should get their correct hats.

Also less than 1/2 of one percent of the time there should be at least 5 men correct (if 5 men are correct, then then 6th will get his because it will be the only one left.

Min Hats

to right man……… Percent

1…………….. 81.5972222222%

2…………….. 44.9305555556%

3…………….. 16.8055555556%

4…………….. 5.6944444444%

5…………….. 0.4861111111%

6…………….. 0.4861111111%

Another point of “insight”, It took only 4320 tests.

November 2nd, 2012 at 6:57 am

Hi ragknot. I gues you’ve now writtten the non Monte Carlo version that I would have done at the outset. i.e. generate all 720 permutations. Let the LHM go 1st, 2nd, 3rd,… and count how many picked their own hats in each permutation.

Thank you for the numbers, they’ll be very useful in helping me to check my math before posting.

If you’ve got a cunning permutations generator, I’d love to see it.

November 2nd, 2012 at 10:27 am

yes Chris, you got what I did.

“123456″ can be arranged in 720 diferent orders.

But then to each, I added a 7th character for the Large Hat Man. So there are 720 than a 1 is added to, then another 720 with a 2 added… go up to “6″ and 720 * 6 = 4320. Then the 4320 different strings show the order of six men leaving the bar, plus which man is the LHM.

Let’s test this… “2341653″

1. Last is the LHM and he will be the third to leave.

2. He will not get his hat because Hat(3) left with the second to leave. If his hat was after the 3rd spot, he would get his hat so the #3 would be swapped, and the order would change. For this string, the number getting the correct hat would be zero.

So what about this? “2461531″

November 4th, 2012 at 10:23 pm

Answer? This is how this works… 2461531; the Large Hat Man (seventh digit is a ONE) is the first person to go get his hat, the hat he would get is hat #2, but being the owner of a big hat, he see his hat is the FOURTH hat, so he takes his hat (hat #1 in the 4th position, and puts hat #2 where hat #1 was…(the fourth place.

1st man to leave gets hat #1 (cause he swapped)

2nd man to leave gets hat #4,

3rd man to leave gets hat #6,

4th man to leave gets hat #2 (swapped by LHM”)

5th man to leave gets hat #5… Right hat!

6th man to leave gets hat #3

November 10th, 2012 at 9:14 pm

Greetings Earthmen.

In the following I’ll use the notation abcdef/ABCDEF to indicate the collection of hats and men – the sequence of letters is irrelevant.

I’m going to calculate the solution p(2+) = 1 – (p(0) + p(1)). I’ve already dealt with p(0) in One large hat and got (265/2)/720.

I’ll be using the LHM case from the outset. Let’s see what happens if C is the LHM. If neither A nor B pick C, then C will take his own hat and then we’re left with abdef/ABDEF and then there are d(5) ways where none of the others take their own hats.

But if e.g. A takes C, then we’re left with abdef/CBDEF. Define h(n) to be the number of ways that for n hats/men, where one hat isn’t owned by any of them, and exactly one man picks his own hat. So for abdef/CBDEF there are h(5) complying permutations.

If C then picks a (i.e. A and C have exchanged hats), then we’re left with bdef/BDEF and for that there are d(4,1) ways that exactly one man picks his own hat. But if C picks e.g. e (or b,d or f), then we’d be left with abdf/EBDF (etc.) and in each case there are h(4) ways for exactly one match.

Let’s examine h(n). From the previous we had h(5) = d(4,1) + 4*h(4).

More generally h(n) = d(n-1,1) + (n-1) h(n-1). Now d(n,m) = c(n,m) d(n-m), so

d(n-1,1) = c(n-1,1) d(n-2) = (n-1) d(n-2). So h(n) = (n-1)(d(n-2) + h(n-1)).

Obviously h(1) = 0 and h(2) = 1. Now compare this to the recursion for d(n):

(see Hat pick I used f(n) rather than d(n) back in those days.)

d(n) = (n-1)(d(n-2) + d(n-1)) and also d(1) = 0 and d(2) = 1 => h(n) = d(n). That’s nice. It also suggests that there is likely to be a shortcut to that result.

Let the probability that the LHM picks his own hat be P (= 21/36 as it happens).

Altogether we get that the probability of exactly one man picking his own hat is:

P d(5)/5! + (1 – P) d(5)/5! = d(5)/5! = 44/120 (= 264/720) = 0.366666…

That agrees with ragknot’s computations (by subtracting his 44.930555% from 81.59722222%) in post 15 above. Because that result is independent of P, it follows that it makes no difference (for exactly one successful pick) that there is a LHM. That’s a nice surprise. i.e. the desired probability might be remebered better as d(n,1)/n!

The probability of no men picking their own hat when one is a LHM is (265/2)/720, so the probability of two or more men picking their own hat is

1 – (265/2)/720 – 264/720 = 0.449305555555…, which agrees with ragknot’s exact computation in post 15 above.