# 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

Seed row
 0 0 0 0 0 0 1 2 3 4

### 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
Seed matrix
 0 0 0 0 0 0 1 2 3 4

`Seed i+1 , ( j + Seed i , j ) % m = Seed i , jfor i=2..m-1, j=0..m-1`

### Step 3

Create m mapping matrices, M0...Mm-1. M0 = Seed matrix. Mi+1 = Rotate(Mi,1)

• Show me
 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, P0...Pm-1 from the mapping matrices M0...Mm-1 .
Select row i, column j of Mk and note it's value v. In row i, column v of Pk place the value j. row 0 and col 0 of Pk is k regardless.

• Show me
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, A0...Am-1 from the planning matrices P0...Pm-1 .
When the planning matrices are lined up in a row, the first row represents the first round, ..., the mth represents the mth round.
A value v in the jth column of a matrix represents the selection of the vth item from group j, where group x contains items labeled m*x to m*x+m-1, x=0..m-1.

• Show me
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 2 3 4
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
 0 1 2 3 4
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
 0 1 2 3 4
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
 0 1 2 3 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
 0 1 2 3 4
4

 0 1 2 3 4
5

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.