elliott@aero.ARPA (Ken Elliott ) (02/13/86)
[munch, munch, munch...... urrrrrrrp]
The following puzzle is a real life puzzle (golly gee, batman), as well
as being interesting. There are two parts; one for the specific application,
and one for the general algorithm.
Part 1 ---------------
Given: 4 'teams' of people, 16 members to a team.
16 'stations'.
The Problem: We want every person (all 64) to go to every station exactly
once. No two members of the same team should be at the same
station at the same time. Every person on a team should see
all other people (aside from those on their team) exactly once.
List the arrangements for every round and station.
Notes: First of all, this is *not* a cutesy trick puzzle. If I've not
provided enough info, *mail* me and I'll try and get back to you.
Obviously, there will be the same number of rounds as stations.
For notational convenience, let's call the groups A,B,C, and D.
Members are referred to as A1,A2, ... etc. for group A, and so on.
If anyone manages to get the solution to the problem, suggested
form is
station station ......
1 2 ......
Round 1: (A1,B1,C1,D1) (A2,B2,C2,D2) ......
2: (A3,B4,C2,D8) (A1,B1,C7,D6) ......
. . .
. . .
This is only a suggestion. If anybody comes up with a solution, I'll
be more than happy to decipher however it is written.
As should be painfully obvious, *I* don't know of a solution to this
problem, so I can't offer to post it in N days. However, if for some
reason the solution is not posted, I'll take it upon myself to do so.
Part 2 -----------
Given: n teams, N members per team.
N stations.
The Problem: Give a general algorithm for arranging the members within the
constraints outlined above, i.e.
1) All persons must visit each station exactly once.
2) No person may meet a member of their own team.
3) No person may meet any other person more than once.
Notes: In the minimum case, N = n+1. Also, the case where N is prime does
have a general (simple) solution. Obviously, part 1 does not follow
this constraint, hence the need for a general algorithm. Again, any
questions should be addressed to me.
-----------
That's the end of the problems! Good luck.
Ken Elliott (elliott@aerospace.ARPA)
UUCP: (who knows)
The puzzle above represents my own views, and not those of this fine
organization for which I work.elliott@aero.ARPA (Ken Elliott ) (02/15/86)
[The line eater is dead. Long live the line e In the previous posting, I wrote .... > > station station ...... > 1 2 ...... >Round 1: (A1,B1,C1,D1) (A2,B2,C2,D2) ...... > 2: (A3,B4,C2,D8) (A1,B1,C7,D6) ...... > . . ^^ ^^. > . . . > > Ok, to get you all off to a good start, I made a boo-boo in the above. Kudos for those of you who noticed that in round 1, station 1, A1 and B1 play together, and in round 2, station 2, they again play together. I LIED. Bad example, but I hope you all get the idea anyway. Also, an implicit rule that I didn't state (but falls out of the others) is that you should have 4 (n in part 2) players per station. Below is a corrected example: station station ...... 1 2 ...... Round 1: (A1,B1,C1,D1) (A2,B2,C2,D2) ...... 2: (A3,B4,C2,D8) (A4,B1,C7,D6) ...... . . ^^ . . . . Ken Elliott (elliott@aerospace.ARPA) UUCP: (who knows) The correction above represents my own views, and not those of this fine organization for which I work.