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^{*}=NX 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..m1. In the example I will use m=5
Step 2
Create m2 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 > m1 then wrap around using modulus m.
Seed matrix
Seed_{ i+1 , ( j + Seed i , j ) % m }= Seed_{ i , j}
for i=2..m1, j=0..m1
Step 3
Create m mapping matrices, M_{0}...M_{m1}. M_{0} = Seed matrix. M_{i+1} = Rotate(M_{i},1)
0  0  0  0  0 
0  1  2  3  4 
0  3  1  4  2 
0  2  4  1  3 
0  4  3  2  1 
Step 4
Create m planning matrices, P_{0}...P_{m1} from the mapping matrices M_{0}...M_{m1} .
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.
k 
Mapping 
Planning 
0 
0  0  0  0  0 
0  1  2  3  4 
0  3  1  4  2 
0  2  4  1  3 
0  4  3  2  1 


1 
0  0  0  0  0 
4  0  1  2  3 
2  0  3  1  4 
3  0  2  4  1 
1  0  4  3  2 


2 
0  0  0  0  0 
3  4  0  1  2 
4  2  0  3  1 
1  3  0  2  4 
2  1  0  4  3 


3 
0  0  0  0  0 
2  3  4  0  1 
1  4  2  0  3 
4  1  3  0  2 
3  2  1  0  4 


4 
0  0  0  0  0 
1  2  3  4  0 
3  1  4  2  0 
2  4  1  3  0 
4  3  2  1  0 


P_{ i , ( M i , j , k ) , k} = j
Step 5
Create m assignment matrices, A_{0}...A_{m1} from the planning matrices P_{0}...P_{m1} .
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+m1, x=0..m1.
k 
Planning 
Assigment 
group 
round 
0 
0  0  0  0  0 
0  1  2  3  4 
0  2  4  1  3 
0  3  1  4  2 
0  4  3  2  1 



0 
1 
1  1  1  1  1 
1  2  3  4  0 
1  3  0  2  4 
1  4  2  0  3 
1  0  4  3  2 



1 
2 
2  2  2  2  2 
2  3  4  0  1 
2  4  1  3  0 
2  0  3  1  4 
2  1  0  4  3 



2 
3 
3  3  3  3  3 
3  4  0  1  2 
3  0  2  4  1 
3  1  4  2  0 
3  2  1  0  4 



3 
4 
4  4  4  4  4 
4  0  1  2  3 
4  1  3  0  2 
4  2  0  3  1 
4  3  2  1  0 



4 




5 
At this point a much simpler generator is painfully obvious. Round 0 is 0..N1 listed columnwise, Round M is Round 0 transposed. Round k is Round k1 after column j has been rotated by j positions.