Solution: Conversations during the Last Supper

This is the solution to the Divertimento Conversations during the last supper.

The fun

A group of \(n\) people agree to have dinner together on different evenings. Each time they sit around a round table so that each person has different diners at different meals on either side of them. If everyone wants to sit next to everyone else, how many evenings should they have dinner together?

The solution

Solution submitted by Juan Arias de Reyna.

We will prove that if \(n=2m+1\) or \(n=2m\), then \(m\) dinners will be sufficient and necessary for any two diners to sit together some evening.

Proposition: If \(n=2m+1\) is odd or \(n=2m\) is even, then at least \(m\) dinners are needed to get all couples to sit together some night.

Note: We assume here that \(m \geq 1\). In the case of 1 person we can say that no evening is necessary, because there are no couples.

Proof: If there are \(n\) diners and they sit at a round table, there will be \(n\) couples who have already achieved the goal at a dinner. The total number of couples is \({{n}\choose{2}}=\frac{n(n-1)}{2}\). If \(K\) dinners are enough, then at most we have \(nK\) couples that have sat together, then it must be
$$Kn\geq \frac{n(n-1)}{2}, \qquad K\ge \frac{n-1}{2}.$$
If \(n=2m+1\) is odd we will have \(K\ge m\) and if \(n=2m\) is even we will have \(K\ge m-\frac12\). That is, \(K\ge m\), since it is an integer.

Proposition: If \(n=2m+1\) is odd or \(n=2m\) is even, \(m\) dinners are enough to get all couples to sit down some night together.

Proof: We first describe the arrangement in which the diners have to sit each of the \(m\) nights to achieve their goal. We first consider the case \(n=2m\) of an even number of diners. We assign each diner a number from \(0\) to \(n-1\). It is convenient to think of the diners as elements of the ring \(\mathbb{Z}/(n\mathbb{Z})\) of the remainders modulo \(n\).

On the first night we arrange the commensals in the form

$$\begin{array}{cccccccccccccccccccccccccccc}
0 & 1 & n-1 & 2 & n-2 & 3 & n-3 & \dots & m-1 & m+1 & m \\
\end{array}$$
(remember that \(n=2m\)).

For example, when \(m=8\), the diners will be seated in the following configuration
\[\begin{array}{ccccccccccccccccccccccccc}
0 & 1 & 7 & 2 & 6 & 3 & 5 & 4 \\
\end{array}\]
The arrangement on each night is obtained from the previous one by adding one unit (modulo \(n\)) to the diners of the previous evening, until reaching \(m\) evenings. Thus, in the case of \(8\) diners, the solution will be
\[\begin{array}{ccccccccccccccccccccccccc}
0 & 1 & 7 & 2 & 6 & 3 & 5 & 4 \\
1 & 2 & 0 & 3 & 7 & 4 & 6 & 5 \\
2 & 3 & 1 & 4 & 0 & 5 & 7 & 6 \\
3 & 4 & 2 & 5 & 1 & 6 & 0 & 7
\end{array}\]
which can be found to be sufficient in this case.

Let us return to the general case. If we group the diners arranged as in the first night in the form
\[0, (1,n-1), (2,n-2), (3,n-3), \dots (m-1,m+1), m ,\]
we see that any pair \((a,b)\in(\mathbb{Z}/(n\mathbb{Z}))^2\) such that \(a+b=0\) will have sat next to each other the first night (bearing in mind that pairs \((m,m)\) or \((0,0)\), which satisfy the condition \(m+m=0\), are not pairs). These are in total \(m-1\) pairs.

Apart from these, on the first evening the pairs \((a,b)\in(\mathbb{Z}/(n\mathbb{Z}))^2\) that satisfy \(a+b=1\) sit together, as we see in the following diagram:
\[(0,1), (n-1,2), (n-2,3), \dots, (m+1,m).\]
In total there are \(m\) pairs. Then on the first dinner all \((a,b)\) pairs that add up to \(0\) or \(1\) have sat together. On the second dinner all pairs of the form \((a+1,b+1)\), i.e. all pairs that add up to \(2\) or \(3\), will have sat together. On the third one the pairs that add up to \(4\) or \(5\) sit together. So on the \(m\)-th evening all the pairs \((a+m-1, b+m-1)\) sit together, that is all the pairs that add up to \(a+b+2m-2\), namely all pairs that add up to \(n-2\) or \(n-1\). But given any pair \((a,b)\) their sum will be \(a+b=0\), \(1\), \(2\), \(\dots\), or \(n-1\). And so they will have sat together on some of the \(m\) evenings. This ends the proof in the even case.

To solve the case \(n+1=2m+1\) we consider a special diner. Let us think of the Last Supper: Jesus Christ with the twelve apostles. We assign as before the apostles to the additive group \(\mathbb{Z}/(12\mathbb{Z})\) and designate Jesus Christ as the diner \(\infty\). The first evening we seat them in the form

\[\infty\quad 0\quad 1\quad 11\quad 2\quad 10\quad 3\quad 9\quad 4\quad
8\quad 5\quad 7\quad 6\]
And we follow the same rule as before by adding one unit to each to get the position on the following evening. This means that Jesus Christ sits at a fixed place, the presidency of the table. Since the table is now round, Jesus Christ is seated on the first day between \(0=\)John and \(6=\)Judas. That implies that on the following days he will be seated between \(1\) and \(7\), between \(2\) and \(8\), \(\dots\), and between \(5\) and \(7\). Then they will all have sat one evening or another with Jesus Christ. We see that this reasoning is general. The president sits the first dinner in the middle of \((0,m)\), and on the following dinners in the middle of \((1, m+1)\), \((2, m+2), \dots, (m-1,n-1)\) and he will have sat with everyone.