Party Puzzle: for your amusement

[hugh steers]

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.

[Mike Reed]

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.

[hugh steers]

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.