7
$\begingroup$

There are N tables at a party seating N people each, for a total of N^2 people. Every seat is initially empty.

At each round, every person must sit with a new group of people. If each person were given a number, they would need to see unique numbers at their table every round - numbers they have seen in previous rounds also count.

Question: How many rounds can occur before a person sees a duplicate?

The upper bound is (N^2 - 1) / (N - 1) = (N + 1) rounds trivially if you consider the problem from one person's perspective.

For N = 2 (4 people, 2 tables of 2) it is correct:

AB CD
AC BD
AD BC

Is there a general formula for this maximum number of rounds, or is it as obvious as I have written?

Inspiration: I was at a workshop with 36 people around 6 identical tables; at the end of each intermission, we were encouraged to sit with entirely new people.

$\endgroup$
10
  • 1
    $\begingroup$ Just to add some language in case it helps you Google, we can say we’re starting with a complete graph on $n^2$ vertices, and we have a sequence of partitions of the vertices $P_1, P_2, \dots$ where each $P_i$ has $n$ parts of size $n$, and we are wondering how long the sequence can be before the induced subgraph on $P_j$ shares an edge with $P_i$ for $i < j$. $\endgroup$ Commented Jul 24, 2023 at 5:04
  • 2
    $\begingroup$ This is the $S(2,n,n^2)$ Steiner system, see mathworld.wolfram.com/SteinerSystem.html for a construction $\endgroup$
    – Peter Wu
    Commented Jul 24, 2023 at 8:13
  • 3
    $\begingroup$ I see someone went to Oberwolfach recently ;) $\endgroup$ Commented Jul 24, 2023 at 9:15
  • 1
    $\begingroup$ @PeterWu It seems slightly harder then that? You also need to group the $n^2$ blocks into $n$ collections of $n$, one for each day. Unless I am missing something. $\endgroup$ Commented Jul 24, 2023 at 15:46
  • 3
    $\begingroup$ PS I don't know why people have voted to close this, it is a perfectly reasonable question about block designs. $\endgroup$ Commented Jul 24, 2023 at 15:46

1 Answer 1

9
$\begingroup$

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$ !


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.

$\endgroup$
1
  • 1
    $\begingroup$ Remark: I wrote this answer using the standard description of mutually orthogonal Latin squares, but the definition I prefer is that having $d-2$ MOLS's is the same as having an $N^2$ element subset of $[N]^d$ which projects bijectively onto every $2$-dimensional coordinate plane. From this perspective, the subset is given by, for each person, listing the sequence of $d$ tables at which they have sat. $\endgroup$ Commented Jul 24, 2023 at 17:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .