Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site aero.ARPA
Path: utzoo!linus!decvax!ittatc!dcdwest!sdcsvax!sdcrdcf!trwrb!trwrba!aero!elliott
From: elliott@aero.ARPA (Ken Elliott )
Newsgroups: net.puzzle
Subject: Arrangement Puzzle
Message-ID: <266@aero.ARPA>
Date: Thu, 13-Feb-86 12:45:15 EST
Article-I.D.: aero.266
Posted: Thu Feb 13 12:45:15 1986
Date-Received: Wed, 19-Feb-86 08:07:02 EST
Reply-To: elliott@aero.UUCP (Ken Elliott)
Distribution: net
Organization: The Aerospace Corporation, El Segundo, CA
Lines: 64
Summary: Permutations are helpful ...


[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.