Subscribe via feed.

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?

This post is under “Tom” and has 19 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

19 Responds so far- Add one»

  1. 1. Your name Said:

    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

  2. 2. Werner Said:

    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?

  3. 3. Chris Said:

    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.

  4. 4. Chris Said:

    … 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.

  5. 5. ragknot Said:

    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?

  6. 6. ragknot Said:

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

    Option Explicit
    'To load this into Excel: open Excel, click on a cell, press ALT+F11.
    'The Visual Basic window should open. On the menu click "Insert", then "Module".
    'Paste this code into the "Module1" code window. Add the Debug tool bar.
    
    Sub Main()
      Debug.Print Hats(6, 1, 10000, True)
    End Sub
    
    Function Hats(People As Integer, MinRight As Integer, Tries As Long, _
                  LargeHatTF As Boolean) As Double
    
    'Dim People As Integer     'usually 6 men
    'Dim MinRightAs Integer    'minimum right hats for a "success"
    'Dim Tries As Long         'how many attempts made until end
    'Dim LargeHatTF As Boolean 'True of False
    Dim Man(20) As Integer
    Dim Hat(20) As Integer
    Dim LargeMan As Integer    'the Man number with Large Head
    Dim Successes As Long
    Dim Attempts As Long
    Dim CorrectHat As Integer  'Counts hats right, up to MinRight was recieved
    Dim a As Integer, b As Integer, c As Integer, d As Integer, x As Integer
    
    Randomize
    For a = 1 To People:  Man(a) = : Next a
    
    LargeMan = 0
    For b = 1 To People: Hat(b) = b: Next b
    For x = 1 To 100: GoSub swaphats: Next x
    
    Begin: Attempts = Attempts + 1
    CorrectHat = 0
    For x = 1 To 36: GoSub swaphats: Next x
    
    If LargeHatTF Then
      LargeMan = Int(Rnd() * 6 + 1)
      For x = LargeMan To People  'is large man's hat unpick yet? if so swap it
        If Man(LargeMan) = Hat(x) Then 'x is where the large hat is found
          a = Hat(LargeMan) '"a" is the hat that was in order for the large man
          Hat(LargeMan) = Hat(x)  'swap the large man's hat so he will get it.
          Hat(x) = a
        End If
      Next x
    End If
    
    ' Example
    ' Man#   Hat#
    '  1      5
    '  2      3   if large hat man is #2 his hat is still there,
    '             swap hats 3 and 2, man 5 will get hat #3
    '  3      6   if large hat man is #3 his hat has been taken by Man 2
    '  4      4   Man 4 will gets his hat also
    '  5      2
    '  6      1
    'CorrectHat will be score of TWO... large man # 2 and man #4
    'if MinRight is 2 or less, then successes will increase 1 point
    
    For x = 1 To People       'see if man gets "his hat"?
      If Man(x) = Hat(x) Then CorrectHat = CorrectHat + 1
    Next x
    
    done:
    If CorrectHat >= MinRight Then Successes = Successes + 1
    If Attempts < Tries Then GoTo Begin
    'Debug.Print "With "; People; "guys... Success must be at least "; _
       MinRight; " getting right hat..., and a large HAT is "; LargeHatTF
    'Debug.Print "Out of"; Attempts; "attempts, the percent of Success is " & _
      (Successes / Attempts) * 100 & "%    and Failures is " & _
      ((Attempts - Successes) / Attempts) * 100 & "%"
    'Debug.Print
    Hats = (Successes / Attempts)
    Exit Function
    
    swaphats:
      c = Int(Rnd() * People + 1)
      d = Int(Rnd() * People + 1)
      If c <> d Then
        a = Hat(c):  b = Hat(d):
        Hat(c) = b: Hat(d) = a
      End If
      Return
    End Function
    
  7. 7. cazayoux Said:

    Are these testing equality?

    If LargeMan Hat(LargeMan) Then
    If c d Then

  8. 8. Chris Said:

    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.

  9. 9. Chris Said:

    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!):

    m   c(6,m) d(6-m)  p(6,m)
    
    0      1     265   265/720
    1      6      44   264/720
    2     15       9   135/720
    3     20       2    40/720
    4     15       1    15/720
    5      6       0    0     (NB it is impossible to get 5 right and 1 wrong)
    6      1       1    1/720 (hence the need to define d(0))
    

    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.

  10. 10. ragknot Said:

    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.

  11. 11. Chris Said:

    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.

  12. 12. ragknot Said:

    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.

  13. 13. Chris Said:

    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

    'the next declaration is really part of the RndM() function
    'a pro programmer would put RndM() in a separate module
    'and make them be private. so I'm tipping my hat to that
    Private lngX As Long, lngY As Long, lngZ As Long, blnInit As Boolean
    
    Public Function RndM(Optional ByVal Number As Long) As Double
    'I've moved the statics up to module level for performance reasons
    ' Static lngX As Long, lngY As Long, lngZ As Long, blnInit As Boolean
      Dim dblRnd As Double
      'nb like Rnd(), RndM() returns a value in the range 0 to 0.99999...
    
      'if initialized and no input number given
      If blnInit And Number = 0 Then
        'lngX, lngY and lngZ will never be 0
        lngX = (171 * lngX) Mod 30269
        lngY = (172 * lngY) Mod 30307
        lngZ = (170 * lngZ) Mod 30323
      Else
        'if no initialization, use Timer, otherwise ensure positive Number
        If Number = 0 Then Number = Timer * 60 Else Number = Number And &H7FFFFFFF
        lngX = (Number Mod 30269)
        lngY = (Number Mod 30307)
        lngZ = (Number Mod 30323)
        'lngX, lngY and lngZ must be bigger than 0
        If lngX <= 0 Then lngX = 171
        If lngY <= 0 Then lngY = 172
        If lngZ <= 0 Then lngZ = 170
        'mark initialization state
        blnInit = True
      End If
      'generate a random number
      dblRnd = CDbl(lngX) / 30269# + CDbl(lngY) / 30307# + CDbl(lngZ) / 30323#
      'return a value between 0 and 1
      RndM = dblRnd - Int(dblRnd)
    End Function
    
    Sub ShuffleArray(ByRef nArray() As Integer)
    'see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
    'I've tweaked it for an arbitrarily based array (rather than 0 based)
    
      Dim nCurrent As Integer
      Dim nRandom As Integer
      Dim nTemp As Integer
      Dim lb As Integer, ub As Integer
    
      lb = LBound(nArray)
      ub = UBound(nArray)
      For nCurrent = ub To lb + 1 Step -1
      'to generate a random integer in the range min to max
      'use Int((max-min+1)*RndM()+min)
      'for this shuffler, max = nCurrent and min = lb
        nRandom = Int((nCurrent - lb + 1) * RndM() + lb)
        nTemp = nArray(nCurrent)
        nArray(nCurrent) = nArray(nRandom)
        nArray(nRandom) = nTemp
      Next nCurrent
    
    End Sub
    
  14. 14. ragknot Said:

    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.

  15. 15. ragknot Said:

    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.

  16. 16. Chris Said:

    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.

  17. 17. ragknot Said:

    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″

  18. 18. ragknot Said:

    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

  19. 19. Chris Said:

    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.

Post a reply




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