4
$\begingroup$

There are $N^2$ guests at a party. How can we seat these guests at $N$ tables, in a number of rounds, so that each guest sits with every other guest exactly once?

I've come up with an algorithm that works only for prime $N$

In each round, row $i$ consists of the "diagonal elements" stemming from the first element of row $i$ in the previous round. After N rounds, also include the transpose of the original matrix.

This works for $N = 3$

1 2 3
4 5 6
7 8 9

1 5 9
4 8 3
7 2 6

1 8 6
4 2 9
7 5 3

1 4 7
2 5 8
3 6 9

But not for $N = 4$

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

 1  6 11 16
 5 10 15  4
 9 14  3  8
13  2  7 12

 1 10  3 12
 5 14  7 16
 9  2 11  4
13  6 15  8

 1 14 11  8
 5  2 15 12
 9  6  3 16
13 10  7  4

 1  5  9 13
 2  6 10 14
 3  7 11 15
 4  8 12 16

Note $1$ and $3$ in arrangements 1 and 3

This isn't a homework problem.

$\endgroup$
  • 1
    $\begingroup$ For prime $N$, you've discovered (in a different but equivalent form) the solution: in rounds $r=0,1,\dots,N-1$, take the lines of the form $y=rx+b$ ($0\le b\le N-1$), while in round $N$, take the lines of the form $x=b$ ($0\le b\le N-1$). $\endgroup$ – Greg Martin Sep 9 '14 at 1:16
  • 1
    $\begingroup$ This can be generalized to cases where $N$ is a prime power, rather than only prime $N$. It is a famous open problem whether these are the only possibilities. $\endgroup$ – hardmath Sep 9 '14 at 1:24
  • $\begingroup$ I've written a program that performs this algorithm, verifies the result, and prints the permutations, if anyone would like to play around with it: stackoverflow.com/a/25734046/384954 and yes, I have thought about this problem before answering that SO question :) $\endgroup$ – OregonTrail Sep 9 '14 at 3:51
1
$\begingroup$

Before we tackle the general $N^2$ problem, let's give a solution of the $4^2 = 16$ diner problem, grouping them into five courses seated at four tables of four diners each:

First course:

X X X X    O O O O    O O O O    O O O O
O O O O    X X X X    O O O O    O O O O
O O O O    O O O O    X X X X    O O O O
O O O O    O O O O    O O O O    X X X X

Second course:

X O O O    O X O O    O O X O    O O O X
X O O O    O X O O    O O X O    O O O X
X O O O    O X O O    O O X O    O O O X
X O O O    O X O O    O O X O    O O O X

Third course:

X O O O    O O X O    O X O O    O O O X
O X O O    O O O X    X O O O    O O X O
O O O X    O X O O    O O X O    X O O O
O O X O    X O O O    O O O X    O X O O

Fourth course:

X O O O    O O O X    O X O O    O O X O
O O X O    O X O O    O O O X    X O O O
O X O O    O O X O    X O O O    O O O X
O O O X    X O O O    O O X O    O X O O

Fifth course:

X O O O    O X O O    O O X O    O O O X
O O O X    O O X O    O X O O    X O O O
O O X O    O O O X    X O O O    O X O O
O X O O    X O O O    O O O X    O O X O

The arrangement of $N^2$ diners at $N$ tables through $N+1$ courses of a meal amounts to what in incidence geometry is called a finite affine plane.

An affine plane is a system of points and lines such that:

  • Any two distinct points lie on a unique line.
  • Each line has at least two points.
  • Given a line and point, there is a unique parallel line containing the point.
  • There exist three non-colinear points (points not all on the same line).

NB: By parallel lines we mean either disjoint or equal lines.

The diners are our points, and the $N$-sets of diners served at separate tables during one course are our parallel lines: each diner is at exactly one of the $N$ tables during a course.

If a line of an affine plane contains $n$ points, we say it is a finite affine plane of order $n$. The following deductions can be made:

  • All lines contain $n$ points.
  • Every point is contained in $n+1$ lines.
  • There are $n^2$ points in all.
  • There are a total of $n^2 + n$ lines in all.

In all the known examples of finite affine planes, $n$ is either a prime or a prime power. A finite affine plane of order $n$ exists if and only if a finite projective plane of order $n$ exists, and thus is equivalent to existence of $n-1$ mutually orthogonal latin squares of order $n$.

A famous open problem is posed by the conjecture that $n$ not a prime power is impossible. This Prime Power Conjecture remains a topic of active research.

The nonexistence of two orthogonal latin squares of order 6 (Euler/Tarry; see D. Stinson's A Short Proof... for a modern 4 page treatment) implies there is no finite affine plane of that order, and Lam's extensive computer investigations proved there is no finite affine plane of order 10. Many additional nonexistence results ($n=14,21,22,\ldots$) are shown by the Bruck-Ryser-Chowla Theorem.

The smallest open case is currently order $n=12$.

Linear algebra can be used to construct affine planes or projective planes from finite fields (necessarily of prime power order), and the results are called Galois geometries. It is known that there are affine planes that are not isomorphic to any of these (but so far only for prime power orders).

Construction: Let finite field $\mathbb{F}_q$ where $q=p^k$ have a prime power order. Partition the Cartesian product $\mathbb{F}_q\times \mathbb{F}_q$ into $q+1$ families of parallel lines through every pair of distinct points $(x_1,y_1),(x_2,y_2)$. Each line has $q$ points, so each point will have $q+1 = \frac{q^2-1}{q-1}$ lines through it. Any $q$ parallel lines must cover the plane, and the required $q+1$ classes of parallel lines are parameterized by their "slope" $s=0,\ldots,q-1,\infty$, where infinite slope means "vertical" lines (first coordinate held constant) and otherwise $s= \frac{y_2-y_1}{x_2-x_1}$.

Constructing the finite field of order $q=p^k$ can be done as a quotient ring $\mathbb{Z}_p[X]/f(X)$ where $f(X)\in \mathbb{Z}_p[X]$ is an irreducible polynomial of degree $k$. I had occasion to construct a finite field of order $5^3=125$ by this method in this Answer.

$\endgroup$
  • $\begingroup$ Excellent answer $\endgroup$ – OregonTrail Sep 11 '14 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.