Skip to main content
MathOverflow

Return to Answer

added 2117 characters in body
Source Link
David E Speyer
David E Speyer
  • 156.2k
  • 14
  • 420
  • 763

Solving this problem for $d$ days is equivalent to constructing $d-2$ mutually orthogonal $N \times N$ Latin squares, which we'll call $L_3$, $L_4$, ..., $L_d$. So your problem is equivalent to finding the maximum number of $N \times N$ mutually orthogonal magic squares. See OEIS sequence A001438 and the references there.

Here is how to go from MOLS to a seating plan. Label the people by pairs $(i,j)$ with $1 \leq i,j \leq N$. On the first day, people with the same $i$-coordinate eat together. On the second day, people with the same $j$ coordinate eat together. On day $k$, for $k \geq 3$, group people according to the entries of the corresponding cells in $L_k$.

This construction is easily reversible: Given a seating arrangement, number the tables arbitrarily on each day. The $(i,j)$ entry in $L_k$ is given by finding the unique person who ate at table $i$ on day $1$ and table $j$ on day $2$, and writing down the number of the table where they ate on day $k$.

This means that your conference choose uniquely poorly in taking $N=6$! It is possible to achieve $4$ days for every $N$ except $N=2$ and $N=6$. See:

Bose, R. C.; Shrikhande, S. S.; Parker, E. T., Further results on the construction of mutually orthogonal latin squares and the falsity of Euler’s conjecture, Can. J. Math. 12, 189-203 (1960). ZBL0093.31905.

If $N$ is odd, the solution for $4$ days is particularly easy to describe: Seat the people by $i$-coordinate on day $1$, by $j$-coordinate on day $2$, by $i+j$ on day $3$ and by $i+2j$ on day $4$.

More generally, if $p$ is the smallest prime divisor of $N$, then I believe that we can achieve $p+1$ days by using $i$, $j$, $i+j$, $i+2j$, ..., $i+(p-1)j$. I also have a construction which gets $\min(p_i^{e_i})+1$ days, when $N = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ is the prime factorization of $N$, but I'm going to hold off writing it up.

Solving this problem for $d$ days is equivalent to constructing $d-2$ mutually orthogonal $N \times N$ Latin squares, which we'll call $L_3$, $L_4$, ..., $L_d$. So your problem is equivalent to finding the maximum number of $N \times N$ mutually orthogonal magic squares. See OEIS sequence A001438 and the references there.

Here is how to go from MOLS to a seating plan. Label the people by pairs $(i,j)$ with $1 \leq i,j \leq N$. On the first day, people with the same $i$-coordinate eat together. On the second day, people with the same $j$ coordinate eat together. On day $k$, for $k \geq 3$, group people according to the entries of the corresponding cells in $L_k$.

This construction is easily reversible: Given a seating arrangement, number the tables arbitrarily on each day. The $(i,j)$ entry in $L_k$ is given by finding the unique person who ate at table $i$ on day $1$ and table $j$ on day $2$, and writing down the number of the table where they ate on day $k$.

This means that your conference choose uniquely poorly in taking $N=6$! It is possible to achieve $4$ days for every $N$ except $N=2$ and $N=6$. See:

Bose, R. C.; Shrikhande, S. S.; Parker, E. T., Further results on the construction of mutually orthogonal latin squares and the falsity of Euler’s conjecture, Can. J. Math. 12, 189-203 (1960). ZBL0093.31905.

If $N$ is odd, the solution for $4$ days is particularly easy to describe: Seat the people by $i$-coordinate on day $1$, by $j$-coordinate on day $2$, by $i+j$ on day $3$ and by $i+2j$ on day $4$.

More generally, if $p$ is the smallest prime divisor of $N$, then I believe that we can achieve $p+1$ days by using $i$, $j$, $i+j$, $i+2j$, ..., $i+(p-1)j$. I also have a construction which gets $\min(p_i^{e_i})+1$ days, when $N = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ is the prime factorization of $N$, but I'm going to hold off writing it up.

Source Link
David E Speyer
David E Speyer
  • 156.2k
  • 14
  • 420
  • 763

It is possible to achieve $N+1$ days if and only if there is a finite projective plane with $N^2+N+1$ points.

Given the plane: Choose a special line $L_{\infty}$ in the plane. Let the $N+1$ points on $L_{\infty}$ be $(D_1, D_2, \dots, D_{N+1})$; these will index the days of the conference. Let the $N^2$ points not on $L_{\infty}$ be $(P_1, P_2, \ldots, P_{N^2})$, these will index the people. For each $D_k$, there are $N$ lines through $D_k$ other then $L_{\infty}$; each of these lines contains $N$ of the $P_i$'s. Use this seating arrangement on day $k$. Since every pair $(P_i, P_j)$ is on a unique line, and that unique line intersect $L_{\infty}$ at a unique $D_k$, there is a unique day on which $i$ and $j$ sit together.

This construction is easily reversible: Given the seating arrangement, let the points of our underlying plane be $N^2$ points $P_i$ for the people and $N+1$ points $D_k$ for the days. Define a line to consist of $D_k$, together with all of the $P_i$ for people $i$ who sat together on day $k$. Also, add one more line $\{ D_1, D_2, \ldots, D_{N+1} \}$. It is straightforward to check that this obeys the axioms of a projective plane.

As the Wikipedia link above says, projective planes exist whenever $N$ is a prime power, and have been proved not to exist for $N=6$, $10$. The particular case of $N=6$, which you raise, is impossible. Moral: Conferences should be $5$ days long, not $7$ !