tag:blogger.com,1999:blog-4115025577315673827.post6429672615042882780..comments2019-10-08T12:02:40.465+05:30Comments on CSE Blog - quant, math, computer science puzzles: Mad Hat PartyUnknownnoreply@blogger.comBlogger14125tag:blogger.com,1999:blog-4115025577315673827.post-55878134748922426072013-10-20T21:24:57.639+05:302013-10-20T21:24:57.639+05:30I think it should be 2...
Suppose that there are ...I think it should be 2... <br />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. <br />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. Kushagrahttps://www.blogger.com/profile/11664824535535246894noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-70698548552592604792013-03-22T16:43:51.979+05:302013-03-22T16:43:51.979+05:30This comment has been removed by the author.Vivek Ranjan Nemahttps://www.blogger.com/profile/04863121359660229833noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55324477080632048602013-03-08T00:00:28.413+05:302013-03-08T00:00:28.413+05:30assuming there are 'n' number of guests in...assuming there are 'n' number of guests intially we'd need 'n+1' extra guestssudeephttps://www.blogger.com/profile/07148347396293506771noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55635987817510060992013-03-05T13:50:10.293+05:302013-03-05T13:50:10.293+05:30I think the answer is a minimum of 2 guests. It ca...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.amithttps://www.blogger.com/profile/00189222868480786455noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-30502023405632197692013-02-26T13:17:58.340+05:302013-02-26T13:17:58.340+05:30Oh, you're right, my last answer doesn't w...Oh, you're right, my last answer doesn't worktakakihttps://www.blogger.com/profile/01295985839611242377noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-70746432028033239622013-02-26T13:17:57.514+05:302013-02-26T13:17:57.514+05:30This comment has been removed by the author.Vivek Ranjan Nemahttps://www.blogger.com/profile/04863121359660229833noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-9295385287597942572013-02-26T00:41:32.682+05:302013-02-26T00:41:32.682+05:30This comment has been removed by the author.Vivek Ranjan Nemahttps://www.blogger.com/profile/04863121359660229833noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-75188805537732676722013-02-25T22:17:10.777+05:302013-02-25T22:17:10.777+05:30Small correction to my last comment: for a cycle (...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.takakihttps://www.blogger.com/profile/01295985839611242377noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-13434530489395222822013-02-25T22:14:40.690+05:302013-02-25T22:14:40.690+05:30Actually, I think it's possible with just one ...Actually, I think it's possible with just one extra guest.<br /><br />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.<br /><br />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.takakihttps://www.blogger.com/profile/01295985839611242377noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-38018497255125023792013-02-25T15:15:33.169+05:302013-02-25T15:15:33.169+05:30Actually 2 would do the job.. generalizing for k c...Actually 2 would do the job.. generalizing for k cyclic graphs, Let L1 shake hands with every cycle members starting from Oy[1], where<br />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}..<br />Oy[k-1].... Oy[3]..<br />Then he proceeds to O(y+1)[1]... and proceeds. Now at the end of covering all circles.<br />We started with L1:L2 and L2:L1 after the first cyclic graph<br />At the end of nth cycle [the last cycle] the state is<br /><br />L1 : On[2] L2 :L1<br />O1[1] : L2 O1[2]: O1[1]<br />O2[1] : O1[2] O2[2]:O2[1]<br />O3[1] : O2[2] O3[2]:O3[1]<br />....<br />....<br />On[1]: O(n-1)[2] On[2]:On[1]<br /><br />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]<br /><br />Reducing the problem to<br /><br />L1:On[2], L2: O1[1], O1[1] : L2, On[2]:L1<br />Let L1 and On[2] shake and L2 and O1[1] shake<br />Solved.<br />Reducing the problem toGold and Ironhttps://www.blogger.com/profile/06432880847456391263noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-53321028385681328802013-02-25T14:56:35.903+05:302013-02-25T14:56:35.903+05:30Assumption : No more legal handshakes
Draw a grap...Assumption : No more legal handshakes<br /><br />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.<br />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].<br /><br />We get a cyclic graph.. [or more than one, let's for simplicity assume case of 1 at the moment].<br /><br />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.<br />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.<br /><br />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]<br /><br />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.<br /><br />Not let us assume a more complicated case with more than one directed cyclic graphs.<br />After solving for one directed cyclic graph, L1 and L2 have no more legal hand shakes.<br /><br />Let us insert a new member L3..<br />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.<br /><br />So the with 3 people we can definitely do it.<br /><br />[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]<br />{Solution for 2 cyclic graphs<br />L2:L1, L1:L2, M1:Mk, M2:M1,... , Mk:M1<br />Proceed as before. Start with L1 shaking M1 and moving to Mk, Mk-1<br />L1: M2, L2: L1, M1:L2, M2:M1 - only L1 has shook with M1, rest combinations are still possible<br />M2 shakes with L2<br />L1:M2, L2:M1, M1:L2, M2: L1<br />L1 and M2 shake and L2 and M1 shake}<br /><br />Gold and Ironhttps://www.blogger.com/profile/06432880847456391263noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-5513671847060824132013-02-23T19:27:22.755+05:302013-02-23T19:27:22.755+05:30This comment has been removed by the author.Vivek Ranjan Nemahttps://www.blogger.com/profile/04863121359660229833noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-29663544438778373992013-02-22T18:41:24.167+05:302013-02-22T18:41:24.167+05:30I think it's 4.
We can swap any hats, A and B...I think it's 4.<br /><br />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.<br /><br />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.<br /><br />Something like an initial permutation of ABCD to BCDA seems impossible to fix with less than 4 extra guests.takakihttps://www.blogger.com/profile/01295985839611242377noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-17411292632399024212013-02-21T21:01:16.121+05:302013-02-21T21:01:16.121+05:30This comment has been removed by the author.Vivek Ranjan Nemahttps://www.blogger.com/profile/04863121359660229833noreply@blogger.com