Is there a solution to this Seating Plan problem?

916 Views Asked by At

So a colleague asked me for some Help on an interesting Problem, which we both couldn't find the optimal answer for. The event which needed it is already in the past, so this is just me trying to satisfy my curiosity.

Problem
There are 15 Participants, 5 Tables, 3 Seats per Table, 3 Roles (one for each seat at a Table, so each table has all three roles) and 5 Rounds. The requirements are to find the seating (one for each Round) where each Participant meets another at most once for the whole 5 Rounds. Bonus points if each Participant can do all 3 Roles once or twice.

Can you find the optimal seating plan and is there more than one? Or is there not even one?

The best solution i found is the picture attached below. The colors are to highlight the people who see each other more than once. Optimally it shouldn't be coloured at all.

Solution

2

There are 2 best solutions below

0
On
Table   Round   Role 1   Role 2   Role 3
1       1       1        2        3
        2       12       1        14
        3       6        1        11
        4       8        15       1
        5       5        9        1
2       1       4        5        6
        2       15       4        2
        3       9        4        14
        4       11       3        4
        5       8        12       4
3       1       7        8        9
        2       3        7        5
        3       12       7        2
        4       14       6        7
        5       11       15       7
4       1       10       11       12
        2       6        10       8
        3       15       10       5
        4       2        9        10
        5       14       3        10
5       1       13       14       15
        2       9        13       11
        3       3        13       8
        4       5        12       13
        5       2        6        13

Do you see the pattern? What properties of the numbers involved does it rely upon?

0
On

Here is a solution to the problem as set (each person takes each role at least once, each shares a table with another at most once). This was done by keeping the people in role 1 constant and permuting through the other sets shifting one along by 1, and the other along by 2. This ensured no-one met the same person twice. Then I permuted the roles for rounds 2 and 3 so that everyone does each role at least once.

seating table http://s9.postimg.org/yg7vwrrn1/Seatingtable.gif