HP Forum Archive 21

[ Return to Index | Top of Index ]

Party Puzzle: for your amusement Message #1 Posted by hugh steers on 27 May 2013, 4:38 p.m. Here is a puzzle put to me yesterday. I've not seen this before, so i thought i'd post it here, since some of you guys might be interested, or indeed may have already solved it! There are `n' people at a party. Each person must talk to everyone else exactly once. The guests all talk in pairs, each for a minute then change to another person for the next minute. When n is even, it is possible to achieve this in `n' minutes. How many combinations are there for this optimum time given `n' and what is the best way to find a solution. For example, there is exactly one solution for 4 people. Call them A, B, C and D. The solution can be tabulated as follows: A B C D B A D C C D A B D C B A Columns represent time whilst rows list people. So, for example (row 1), A talks to B, then C then D, whilst (row 2) B talks to A then D then C, and so on. Here is one solution for 6 people, A B C D E F B A D E F C C E A F D B D F B A C E E C F B A D F D E C B A tip: there are 6240 solutions for 8 people.

Re: Party Puzzle: for your amusement Message #2 Posted by mike reed on 28 May 2013, 10:28 a.m., in response to message #1 by hugh steers Hugh, I think what you're looking for are the combinations (not permutations) possible for n objects, taken x at a time. In the example you have given for n=4, all 4 of your answers are the SAME combination in 4 different permutations! AB, CD is the same pairing as BA, DC etc. The actual number of Combinations possible is 6: AB CD AC BD AD CB Any other pairings result in reforming pairs that have already been paired. AB is the same pair as BA, AC the same as CA, etc. resulting in a possible 12 Combinations for 4 objects taken 2 at a time. Having the pairs grouped in pairs for 1 minute at a time = 3 minutes. In the second example, the possible pairs are: AB AC AD AE AF BC BD BE BF CD CE CF DE DF and EF, or 15 possible pairs, with 3 pairs speaking at any given time which yields 455 combinations, and 2730 permutations. This would have repeated pairs in it though. Only 5 groups of 3 are possible without repeating a pairing, so that is 5 minutes. 8 people then are 28 pairs, taken 4 at a time for 7 minutes. It's been a horribly long time since I had Probability and Statistics in High School (I'm 64 now~!) but I THINK my analysis is correct. The contrary may be shown! Edited: 28 May 2013, 10:58 a.m.

Re: Party Puzzle: for your amusement Message #3 Posted by hugh steers on 28 May 2013, 3:00 p.m., in response to message #2 by mike reed Hello Mike, Thanks for having a go at the problem. You have correctly highlighted a mistake in my statement of the problem; for an even number of people, it is achievable in n-1 minutes, not n minutes as i originally wrote. So, n=4, gives 3 mins; n=6, gives 5 etc. However, my tables do show the solutions. They are unfortunately a bit confusing. Taking the first table for n=4 A B C D B A D C C D A B D C B A The first line indicates A talks to B (min 1), A talks to C (min 2) and A talks to D (min 3) ie 3 mins in total. It does not mean A talks to B whilst C talks to D (although confusingly C does talk to D). The second line is the story according to B, so B talks to A (min 1), B talks to D (min 2), B talks to C (min 3). You are right that these all look like the same thing repeated over, because they are! The whole table shows the unique solution for 4 people. It might be clearer if i show two solutions for n=6 A B C D E F B A D E F C C E A F D B D F B A C E E C F B A D F D E C B A A B C D E F B A E C F D C F A B D E D E F A C B E D B F A C F C D E B A In the first minute (column 2) C talks to E in the first solution, but talks to F in the second. it's possible to convert the second table into the first showing that these are, in fact, just one solution. But how to easily generate a solution and are they always permutations of each other. regards, -- hugh.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall