Party Puzzle: for your amusement



#4

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.


#5

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.


#6

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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Good puzzle for kids to solve on 35s? snaggs 11 496 09-18-2013, 10:40 PM
Last Post: David Hayden
  The answer to the second semi-mathematical puzzle Mike Reed 3 176 02-18-2013, 02:40 AM
Last Post: Derek Walker (UK)
  Answer to Mathematical Puzzle Mike Reed 2 179 02-08-2013, 12:11 AM
Last Post: LHH
  OT: a semi mathmatical puzzle 4 u Mike Reed 6 291 02-05-2013, 07:50 PM
Last Post: Mike Reed
  Good calc/math refresher/puzzle book? LHH 6 253 06-03-2012, 11:43 AM
Last Post: Don Shepherd
  EMU41: A Little Late to The Party, but Loving It! Les Wright 3 191 05-09-2012, 03:28 PM
Last Post: Christoph Klug
  (OT?) Buying new calculators from "third party sellers" (aka: calculator non-warranty) Eduardo Duenez 5 290 04-27-2012, 08:46 PM
Last Post: Calum Tait
  HHC 2011 Programming Puzzle SPOILERS Paul Dale 77 1,095 09-28-2011, 09:41 PM
Last Post: Jeff O.
  Did HP or any 3rd party make a 64K card for the 48 series? mr-scorpio 2 146 07-22-2011, 11:50 PM
Last Post: Martin Pinckney
  Re: a challenge related to the 15 puzzle Don Shepherd 0 76 01-20-2011, 11:06 PM
Last Post: Don Shepherd

Forum Jump: