Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Feb 21, 2013

Mad Hat Party

Source: Australian Mathematical Society Gazette - Puzzle Corner 28

Problem: 
The Mad Hatter is holding a hat party, where every
guest must bring his or her own hat. At the party, 
whenever two guests greet each other, they have to 
swap their hats. In order to save time, each pair of 
guests is only allowed to greet each other at most 
once.



After a plethora of greetings, the Mad Hatter notices that it is no longer possible
to return all hats to their respective owners through more greetings. To sensibly 
resolve this maddening conundrum, he decides to bring in even more hat wearing 
guests, to allow for even more greetings and hat swappings. How many extra guests 
are needed to return all hats (including the extra ones) to their rightful owners?


Other "Hat" Problems on the blog:

14 comments:

  1. "How many extra guests are needed to .... " ... do you wish to say How many MINIMUM extra guests are needed to

    ReplyDelete
  2. I think it's 4.

    We can swap any hats, A and B, with two extra guests, C and D, by swapping as follows: AC, BD, AD, BC. However, a hat can only be swapped once using this operation.

    We can reorder the original hats using the above swapping operations, swapping each hat no more than twice. It's therefore possible to solve the problem with two pairs, or four extra guests. The extra pairs may be swapped at the end, but as they haven't greeted each other, can be fixed with a swap.

    Something like an initial permutation of ABCD to BCDA seems impossible to fix with less than 4 extra guests.

    ReplyDelete
  3. I notice one thing here - the poser (of the problem) has not mentioned how many guests are there to begin with. That means the answer is independent of this figure. That means that whether there are N = 20 , 30 or 1000 guests to begin with, the answer is going to be same. (this is not a proof but a hint to reach the answer). So one can assume that there are N=10 guests to begin with say and find the answer and then check that that is going to be the answer for all N.

    ReplyDelete
  4. Assumption : No more legal handshakes

    Draw a graph with owners as nodes and directed edges as the ownership of their hats, directed from the original owner to the current owner.
    Since each hat can only have one owner and each person can be wearing only one hat. We get all the nodes with one edge directed to them and one from them. [Except when the person is wearing his own hat, in which case he is redundant and doesnt need any more handshakes].

    We get a cyclic graph.. [or more than one, let's for simplicity assume case of 1 at the moment].

    And in this graph every node as already shook hands with their neighbours.[premise stating more handshakes wont solve the ownership issue]. So let us visualize the graph. Nodes named from N1 to Nm. N1->N2->N3->.....->Nm->N1.
    The new member (L1) shakes hand with N1, gets Nm's hat.. shakes Nm, gets Nm-1's hat, giving Nm his own hat back.... this proceeds, till he shakes N3, getting N2's hat.

    Now if we let L1 shake N2, we will end up getting a cyclic graph with L1 and N1 with no legal handshakes left... so let us add one more member L2, and let him shake N2... now the situation is as follows [person:wearing whose hat]

    N1:L1, N2:L2, L1:N2, L2: N1 -> L2 shakes N1, L1 shakes N2 -> N1:N1, N2:N2, L1:L2, L2:L1 -> L1,L2 shake..... problem solved.

    Not let us assume a more complicated case with more than one directed cyclic graphs.
    After solving for one directed cyclic graph, L1 and L2 have no more legal hand shakes.

    Let us insert a new member L3..
    L3 shakes hand with one directed cyclic graph and then another directed cyclic graph.. thereby combining the 2 cyclic graphs into one big cyclic graph... he proceeds [Since he is the new guy and hasnt shook hands within any ring] till it is all one big cyclic graph... Then L1 and L2 come and do their magic.

    So the with 3 people we can definitely do it.

    [Also for 2 cyclic graphs we can solve with just 2 people.... yet to try for 3 and see if it can be generalized over n directed cyclic graph and 2 people]
    {Solution for 2 cyclic graphs
    L2:L1, L1:L2, M1:Mk, M2:M1,... , Mk:M1
    Proceed as before. Start with L1 shaking M1 and moving to Mk, Mk-1
    L1: M2, L2: L1, M1:L2, M2:M1 - only L1 has shook with M1, rest combinations are still possible
    M2 shakes with L2
    L1:M2, L2:M1, M1:L2, M2: L1
    L1 and M2 shake and L2 and M1 shake}

    ReplyDelete
  5. Actually 2 would do the job.. generalizing for k cyclic graphs, Let L1 shake hands with every cycle members starting from Oy[1], where
    Oi[j] represents [w/o loss of generality, i>1] jth member of the ith cycle. L1 shakes backwards from Oy[1], to Oy[yk] {yk is the size of yth cycle}..
    Oy[k-1].... Oy[3]..
    Then he proceeds to O(y+1)[1]... and proceeds. Now at the end of covering all circles.
    We started with L1:L2 and L2:L1 after the first cyclic graph
    At the end of nth cycle [the last cycle] the state is

    L1 : On[2] L2 :L1
    O1[1] : L2 O1[2]: O1[1]
    O2[1] : O1[2] O2[2]:O2[1]
    O3[1] : O2[2] O3[2]:O3[1]
    ....
    ....
    On[1]: O(n-1)[2] On[2]:On[1]

    now, L2 shakes with On[2],On[1], O(n-1)[2], O(n-1)[1]........O3[2],O3[1],O2[2],O1[2] returning each person's hat as he shakes their hand [except for On[2] who is struck with L1's hat at the moment]

    Reducing the problem to

    L1:On[2], L2: O1[1], O1[1] : L2, On[2]:L1
    Let L1 and On[2] shake and L2 and O1[1] shake
    Solved.
    Reducing the problem to

    ReplyDelete
  6. Actually, I think it's possible with just one extra guest.

    Write the permutation of hat positions as a set of disjoint cycles. For example if the cycle (ABC) is included in the permutation, that means A is wearing B's hat, B is wearing C's hat and C is wearing A's.

    Then for each cycle, we let the extra guest, X, shake hands with each of the guests in the cycle in order. For the example above, we do the swaps XA, XB, XC. This will correct the positions of the hats in the cycle and will also return the extra guest's hat.

    ReplyDelete
  7. Small correction to my last comment: for a cycle (ABC) and an extra guest X, we should actually do the swaps XA, XB, XC, XA.

    ReplyDelete
  8. Assume there are 3 guest at the party originally - 1, 2 , 3. At the end of handshakes, 1z cap is with 2 , 2z cap is with 3 and 3z cap is with 1. Now introduce one more guest 4.
    At the end of handshakes with 4 ,
    1z cap will be with 4 , 2z with 2 and 3z with 3 and 4z with 1.........

    My hunch is : it is not possible to solve the problem with any number of extra guests

    ReplyDelete
  9. It should be possible to prove that it is not possible. Assume that (on the contrary) it is possible to do this with some n number of extra guests. Assume there are m guests originally. Then just before the last handshake the n + m - 2 guests should be in a state such that everybody has their original hats. Otherwise with the last handshake their would not be an 'equilibrium' state.
    Now with this we have to further conclude that n + m - 4 guests are in an equilibrium state. .....
    Thus we have to conclude last 2 guests are such that with their handshake they get their original hats.
    Not possible.
    So it is not possible that ....

    ReplyDelete
  10. Oh, you're right, my last answer doesn't work

    ReplyDelete
  11. I think the answer is a minimum of 2 guests. It can be shown as follows. First suppose there is a cycle of K people (A1,A2,A3,...,AK) wearing each others hats. Bring 2 new guests X and Y. Let X_A1 denote a hat exchange between X and A1. Then X can cyclically exchange hats with everyone till we are left with some AJ such that AJ has A1's hat, X has AJ's hat and A1 has X's hat. Now consider the following sequence of exchanges - Y_AJ, Y_A1, X_AJ - in the exact order. This brings us to the state where all members of the initial cycle have their own hats and X has Y's hat and Y has X's hat. Thus we see that in resolving a cycle X and Y will exchange their hats without greeting each other. Thus if there are an even number of cycles among the guests then X and Y can resolve all cycles without greeting each other. If there are odd number of cycles then X and Y greet each other after resolving the final cycle to regain their own hat.

    ReplyDelete
  12. assuming there are 'n' number of guests intially we'd need 'n+1' extra guests

    ReplyDelete
    Replies
    1. Does this work with n = 2 and n = 3 guests? What is the logic for saying that n+1 guests would do?

      Delete
  13. I think it should be 2...
    Suppose that there are 2 people who have their hats exchanged, then to get them their own hats I cant do it with one extra person. I can do this with 2 extra persons. Let A and B have their hats exchanged. Bring in C and D. A<-->C and B<-->D. Now A has hat of C and B has hat of D. Also C has hat of B and D has hat of A. Now A<-->D and B<-->C. After this A and B have their own hats.
    This can be extended as well. I can give every man his own hat using two extra persons. For instance A has B's hat and B has C's hat. Now extra persons E1 and E2 can be used along with A and B to give A his own hat.

    ReplyDelete