**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:

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

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.

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.

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.

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

ReplyDeleteAt 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

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.

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

Oh, 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

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

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.