Social squares of prime size

by Richard A. DeVenezia, back to round robin

I call this a social square, and first encountered the problem from an entry in the guestbook. If you know a more mathematical or formal name, please let me know.

This analysis resulted in an extravagant algorithm but led to a much better algorithm for squares of primes. The better algorithm was not found initially because there were unconcious construction constraints related to the way the plan was originally hand written out. Only after writing this page and displaying the assignment matrices (as a matrix instead of as a long row) did the better algorithm become embarassingly obvious.

Problem

Schedule M x M players to play in M+1 rounds of M teams of M players each, so that every player is paired with every other player only once.

N = M x M. What if you have N players and N is slightly less than a square N*?
Plan for N^*=N+G players, where G is the number of ghost players. Some teams will have more players than others.

What if you have N players and N is slightly more than a square N*?
Plan for N^*=N-X players, where X is the number of excess players. In the first round, put X players on standby. In subsequent rounds randomly replace X players with those on standby. Some players will play more (or less) than other players.

Solution

A wandering and unfocused study of the patterns for the schedules found by the bulldozer method led to the concept of a seed of a map that lays out the schedule. I do not know why this algorithm works, nor how to prove if it is true for all primes.

Step 1

Start with a row listing 0..m-1. In the example I will use m=5

Step 2

Create m-2 additional rows using this scheme.
Select row i column j and note it's value v. In row i+1 column j+v place the value v. If j+v > m-1 then wrap around using modulus m.

• Show me
• Stop showing me

Step 3

Create m mapping matrices, M₀...M_m-1. M₀ = Seed matrix. M_i+1 = Rotate(M_i,1)

• Show me
• Stop showing me

Step 4

Create m planning matrices, P₀...P_m-1 from the mapping matrices M₀...M_m-1 .
Select row i, column j of M_k and note it's value v. In row i, column v of P_k place the value j. row 0 and col 0 of P_k is k regardless.

• Show me
• Stop showing me

Step 5

Create m assignment matrices, A₀...A_m-1 from the planning matrices P₀...P_m-1 .
When the planning matrices are lined up in a row, the first row represents the first round, ..., the m^th represents the m^th round.
A value v in the j^th column of a matrix represents the selection of the v^th item from group j, where group x contains items labeled m*x to m*x+m-1, x=0..m-1.

• Show me
• Stop showing me

At this point a much simpler generator is painfully obvious. Round 0 is 0..N-1 listed column-wise, Round M is Round 0 transposed. Round k is Round k-1 after column j has been rotated by j positions.