Party Puzzle: for your amusement « Next Oldest | Next Newest »

 ▼ hugh steers Senior Member Posts: 536 Threads: 56 Joined: Jul 2005 05-27-2013, 04:38 PM 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 Member Posts: 82 Threads: 15 Joined: Jan 2008 05-28-2013, 10:28 AM 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 Senior Member Posts: 536 Threads: 56 Joined: Jul 2005 05-28-2013, 03:00 PM 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 2,781 09-18-2013, 10:40 PM Last Post: David Hayden The answer to the second semi-mathematical puzzle Mike Reed 3 1,199 02-18-2013, 02:40 AM Last Post: Derek Walker (UK) Answer to Mathematical Puzzle Mike Reed 2 1,007 02-08-2013, 12:11 AM Last Post: LHH OT: a semi mathmatical puzzle 4 u Mike Reed 6 1,692 02-05-2013, 07:50 PM Last Post: Mike Reed Good calc/math refresher/puzzle book? LHH 6 1,792 06-03-2012, 11:43 AM Last Post: Don Shepherd EMU41: A Little Late to The Party, but Loving It! Les Wright 3 1,194 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 1,520 04-27-2012, 08:46 PM Last Post: Calum Tait HHC 2011 Programming Puzzle SPOILERS Paul Dale 77 12,192 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 916 07-22-2011, 11:50 PM Last Post: Martin Pinckney Re: a challenge related to the 15 puzzle Don Shepherd 0 659 01-20-2011, 11:06 PM Last Post: Don Shepherd

Forum Jump: