Mad Hat Party
Source: Australian Mathematical Society Gazette - Puzzle Corner 28
Problem:
The Mad Hatter is holding a hat party, where every
After a plethora of greetings, the Mad Hatter notices that it is no longer possible
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:
This comment has been removed by the author.
ReplyDeleteI think it's 4.
ReplyDeleteWe 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.
This comment has been removed by the author.
ReplyDeleteAssumption : No more legal handshakes
ReplyDeleteDraw 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}
Actually 2 would do the job.. generalizing for k cyclic graphs, Let L1 shake hands with every cycle members starting from Oy[1], where
ReplyDeleteOi[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
Actually, I think it's possible with just one extra guest.
ReplyDeleteWrite 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.
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.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteOh, you're right, my last answer doesn't work
ReplyDeleteI 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.
ReplyDeleteassuming there are 'n' number of guests intially we'd need 'n+1' extra guests
ReplyDeleteThis comment has been removed by the author.
DeleteI think it should be 2...
ReplyDeleteSuppose 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.