It is time for the apéritif. $n$ friends sit around a round table and, before drinking, everybody wants to clink glasses with everybody else. Nobody wants to leave their seat, and crossing arms while toasting is considered bad luck (and is, in any case, a reliable way to spill a glass). So the toasts happen in rounds: at each instant, some pairs of people clink, each person clinks with at most one other person, and the arms of two pairs that clink at the same instant must not cross.
The question. What is the minimum number of instants after which everybody has clinked glasses with everybody?
Before reading on, try for yourself: click on two people to make them clink, and move to the next instant when no other toast fits.
I first asked myself this question while having a drink with friends, as a fun little puzzle for the minutes before the first sip. The direct answer, $n$, turns out to be rather easy, and it is even known. But the question would not let go of me, so I dug into it deeper with Claude Opus 5.5. It turns out that this innocent apéritif leads to a few actual contributions in discrete geometry, more precisely in the study of geometric graphs, where one asks how many non-crossing matchings it takes to cover all the segments between $n$ points of the plane.
Discrete geometry is not my usual research area, so I keep this as what it started as, a fun project, and present it here as a blog post (which also gives a a great opportunity to start one :D), which you can cite if needed (see the end of the post).
Tournaments
Without the table, this is a classical question: scheduling a round-robin tournament, in which every player meets every other player once and plays at most one match per round. The answer is well known: $n - 1$ rounds suffice when $n$ is even, and $n$ rounds when $n$ is odd [5].
The geometry already matters for four people seated at the corners of a square table. Each diagonal toast forces the two other people to sit out, since their arms would cross the diagonal, so each diagonal needs an instant of its own, and the four toasts between neighbours need two more instants: accounting for the geometry, it thus needs four instants rather than three.
In mathematical terms, the people are $n$ points on a circle, a toast is a segment between two of them, and an instant is a set of segments that neither share an endpoint nor cross, i.e. a non-crossing matching.
The answer is $n$
Theorem 1 (Araujo, Dumitrescu, Hurtado, Noy and Urrutia [1]; Overbay [2]). For every $n \geq 3$, $n$ people seated around a round table need exactly $n$ instants to all clink glasses without crossing arms.
Lower-bound
The lower bound fits in a few sentences about a fixed drinker Alice. She has to clink with the $n - 1$ other people, at $n - 1$ different instants. Her two neighbours have to clink with each other too, and they cannot do it at any of these instants: whenever Alice clinks, either she clinks with one of them, or her arm separates them. So the $n$ toasts of the figure below pairwise conflict, and they need $n$ different instants.
Upper-bound
For the upper bound, here is a schedule with $n$ instants. Pick an axis of symmetry of the table, and let everybody toast their mirror image with respect to this axis. All these arms are perpendicular to the axis, hence parallel, so nobody crosses arms. Then turn the axis to the next position, and so on: the table has $n$ axes of symmetry, and every two people are the mirror images of each other with respect to exactly one of them.
With the people numbered $0, 1, \dots, n-1$ clockwise and the numbers taken modulo $n$, the instant associated with the axis $s$ is the mirror round
\begin{equation}\label{eq:mirror} C_s = \big\{ \{i, j\} : i \neq j \text{ and } i + j \equiv s \pmod n \big\}, \end{equation}so that the pair $\{i, j\}$ clinks at the instant $C_{i+j}$, and only then.
Unicity of the optimal solution
Theorem 2 (uniqueness). For every $n \geq 3$, every way to toast in $n$ instants consists of the $n$ mirror rounds $C_0, \dots, C_{n-1}$, in some order.
Show the proof
Let us call an event of an instant either a person who sits out, or two neighbours who clink. The whole proof rests on the following observation.
Lemma 3 (two events). Let $n \geq 3$. At every instant, at least two events occur, i.e., if $u$ people sit out and $h$ pairs of neighbours clink, then $u + h \geq 2$.
Show the proof of Lemma 3
Take a toast between two people who are not neighbours, so that each of the two sides of the table that it separates contains somebody. Look at one side. If nobody there sits out, everybody there clinks with somebody on the same side, since a toast to the other side would cross ours. Among these toasts, take one whose two people are closest around the table: nobody sits between them, since such a person would clink with somebody even closer. So they are neighbours, and each side contains an event. If there is no toast between non-neighbours, either nobody clinks, and $u = n \geq 3$, or two neighbours clink, which is an event, and the rest of the table contains another one by the same argument.
When nobody sits out, Lemma 3 says that an instant where everybody clinks contains at least two toasts between neighbours, which was already known [3]. Now, give the weight $1$ to every pair of neighbours, and the weight $2$ to every other pair. An instant $M$ with $|M|$ toasts, $u$ people sitting out and $h$ toasts between neighbours has weight
\begin{equation}\label{eq:weight} 2|M| - h = n - u - h \leq n - 2, \end{equation}since $2|M| = n - u$, while the total weight of all the pairs is $2\binom{n}{2} - n = n(n-2)$. Hence at least $n$ instants are needed, which gives a second proof of Theorem 1. But we get more: in a schedule with exactly $n$ instants, nothing can be wasted. No pair clinks twice, and every instant has exactly two events, i.e. \eqref{eq:weight} is an equality.
It remains to understand the instants with exactly two events, and this is where the mirror appears. By the proof of Lemma 3, every toast that is not an event has an event on each of its sides, so when there are only two events, every other toast separates them. The toasts are therefore nested between the two events, like the rungs of a ladder between its two ends. Walking from one event to the other, the first person on the left clinks with the first person on the right, the second with the second, and so on. Every instant of an optimal schedule is thus a mirror round, and since no pair clinks twice, the $n$ instants are the $n$ different mirror rounds.
I could not find the uniqueness of the optimal schedule anywhere in the literature, although its length has been known for more than twenty years. The closest result I managed to find is a special case, due to Trao, Chia, Ali and Kilicman [9]: at a table of an even number $n$ of people, there can be at most $n/2$ instants where everybody clinks with no toast repeated [3], and when there are that many, they are necessarily mirror rounds. With fewer of them, there is no such rigidity.
Greedy toasting
A natural strategy is to be greedy: at each instant, make as many new toasts as possible. With some luck, this finds the mirror rounds, but it can also go badly, as the figure below shows: at a table of $9$ people, an unlucky greedy schedule takes $18$ instants, twice the optimum, and a computer finds tables of $11$ and $12$ people where it takes $24$ and $26$ instants (code in the appendix). It never goes completely wrong, though: it always finishes within $n(1 + \ln(n/2))$ instants (proof in the appendix). Whether its worst case grows like $n$ or like $n \log n$ seems to be open: I could not find the answer anywhere.
Changing the rules
Once the round table is understood, it is tempting to change the rules of the apéritif. Here is a quick tour. The short arms variant has already been studied, and one step of the analysis of a short apéritif was already known: both are credited below. I could not find the other variants in the literature, so their results seem to be new. For each variant, I give the answer and the key idea behind it, with the complete proofs in the appendix. The variant I find the most interesting, the standing apéro, gets a section of its own afterwards.
Toasting several times, or running out of time
Some tables like to toast several times. If every pair has to clink $t$ times, $tn$ instants are needed, and once again the only way is to repeat each mirror round $t$ times: the weight argument works word for word, since the total weight to cover is now $t\,n(n-2)$, while every instant still weighs at most $n - 2$. Conversely, the apéritif may be too short. In $k \leq n$ instants, at most $k(n-1)/2$ different pairs can clink when $n$ is odd, simply because somebody always sits out, so that at most $(n-1)/2$ pairs clink at each instant, and the mirror rounds reach this bound. When $n$ is even, at most $k(n/2 - 1) + \min(k, n/2)$ pairs can clink: an instant where everybody clinks uses two pairs of neighbours by Lemma 3, and there are only $n$ of them, so at most $n/2$ instants can bring $n/2$ new pairs (an observation already made by Biniaz, Bose, Maheshwari and Smid [3]), while the others bring at most $n/2 - 1$. Again, the mirror rounds reach this bound.
Toasting with the hosts
Sometimes only the toasts with the hosts matter. A host has to clink with $n - 1$ people, one at a time, so at least $n - 1$ instants are needed. For a single host, they suffice: skip the mirror round in which the host sits out. They also suffice for two hosts $a$ and $b$ who do not sit next to each other. First, the hosts clink with each other. Then both go around the table clockwise at the same pace, as the figure below shows. Click on somebody to change the second host.
But two neighbouring hosts $a$ and $a + 1$ already need as much time as the whole table: in $n - 1$ instants, both would have to clink at every instant, yet when $a$ clinks with $a + 2$, the host $a + 1$, enclosed by this toast, has to sit out. Three hosts, wherever they sit, also need $n$ instants: the toasts of each host with the people sitting between the other two hosts need one instant each, and so do the three toasts between hosts.
Short arms
At a large table, people can only reach the $d$ people closest to them on each side. When $d \geq 2$, $2d + 1$ instants are needed, by Alice's argument on a smaller scale: her $2d$ toasts and the toast of her two neighbours still pairwise conflict. This variant has already been studied by Kainen, Joslin and Overbay [7], in the language of book embeddings of circulant graphs: they showed that $2d + 1$ instants suffice when $2d + 1$ divides $n$, and, for $d = 3$, when $n$ is a multiple of $12$. For the first case, let's number the people $0, 1, \dots, 2d$ around the table, again and again. The large table is thus made of copies of a small table of $2d + 1$ people. At each instant, play a mirror round of the small table, and let everybody clink with the nearest person bearing the number of their partner in this round, who is within reach.
Beyond these cases, I could not find the following results in the literature. When $2d + 1$ does not divide $n$, $2d + 1$ instants still suffice for every $n \geq 8, 18, 32, 50$ when $d = 2, 3, 4, 5$ (computer search, code in the appendix). Below these values, the answer is irregular. For $d = 3$, for instance, $7$ instants suffice for $12$, $14$, $15$ and $16$ people, but not for $8$ to $11$, $13$ or $17$ people. What looks regular is the largest table where $2d + 1$ instants are not enough: $7$, $17$, $31$ and $49$ people for $d = 2, 3, 4, 5$, that is, $2d^2 - 1$ people.
Conjecture. For every $d \geq 2$, the largest table at which people who reach their $d$ closest neighbours on each side cannot all clink in $2d + 1$ instants has $2d^2 - 1$ people.
The standing apéro
Let us now leave the table: people stand anywhere in the room, no three of them in a line. Whatever the configuration, $n$ instants are needed when $n$ is odd, since somebody always sits out, so that at most $(n-1)/2$ of the $n(n-1)/2$ pairs clink at each instant, and $n - 1$ when $n$ is even, since everybody has $n - 1$ people to clink with. So for odd $n$, the round table is the best place to toast. For even $n$, the following configuration improves the round table bound.
Theorem 4 (the bar). For every even $n \geq 4$, $n$ people can stand so that they all clink in $n - 1$ instants.
Picture a bar: the figure below shows how its customers and the person behind it toast, before the proof.
Show the proof
Let $n - 1$ people, an odd number, stand along a bar curved like an arch, and the last person, $a$, behind the bar like a barman, above every line through two people at the bar. The people at the bar are in convex position, so they can follow the round-table schedule, the $n - 1$ mirror rounds of a table of $n - 1$ people. As $n - 1$ is odd, each of these instants leaves exactly one of them out, a different one each time, who clinks with the barman instead.
This answers a question of Biniaz, Bose, Maheshwari and Smid [3], who studied the instants at which everybody clinks: how many of them can a configuration of $n$ people offer, without ever repeating a toast? Since everybody has only $n - 1$ people to clink with, at most $n - 1$, and they asked whether some configuration of more than six people reaches this bound. The bar does, for every even $n$, since everybody clinks at each of its $n - 1$ instants. As far as I could find, the question was still open.
At the other end of the spectrum, here is how bad things can get.
Theorem 5 (the crowd in the middle). For every $n \geq 2$, some configurations of $n$ people need at least $\tfrac32 n - \sqrt{3n/2} - 3$ instants.
Since 2005, the best known lower bound for the worst configuration was $n$, the value of the round table, against an upper bound of order $n^{3/2}$ [1], and as far as I could find, Theorem 5 is the first improvement on this lower-bound. Pairwise conflicting toasts, as in Alice's argument, cannot give it, since in any configuration at most $n$ toasts pairwise conflict [6].
The configuration behind this lower bound is a regular polygon with a small crowd at its centre. Its longest toasts, which nearly cut it in half, are the bottleneck: no instant can make much progress on the long toasts and on the toasts of the crowd at the same time, and a weighting argument as in Lemma 3 shows that about $\tfrac32 n$ instants are needed.
Show the proof
Let $m = 2k + 1 \geq 5$ people stand at the corners of a regular polygon. A toast between two corners splits the other corners into two sides. We call its short side the one with fewer corners. Two kinds of toasts matter: the long toasts, between corners at distance $k$ around the polygon, which have $k - 1$ corners on their short side and $k$ on the other, and the almost long toasts, between corners at distance $k - 1$, which have $k - 2$ corners on their short side. There are $m$ of each.
A long toast and its short side, with $k - 1$ corners.
An almost long toast and its short side, with $k - 2$ corners.
A long toast and its only compatible almost long toast: they cover every corner.
Two almost long toasts cover all corners but one, circled.
Three facts about these toasts, illustrated above, are all we need. Say that a corner is free for some toasts if it is neither one of their ends nor on one of their short sides.
- Two long toasts always conflict. A toast compatible with a long toast has both ends on the same side of it, which has at most $k$ consecutive corners, so this toast is shorter.
- A long toast is compatible with only one almost long toast, and together they leave no corner free. An almost long toast does not fit on the short side of a long toast, which has only $k - 1$ corners, and on its long side, which has $k$ corners, the only two corners at distance $k - 1$ are the ends. The ends and short sides of these two toasts then account for $4 + (k - 1) + (k - 2) = m$ corners, that is, all of them.
- An instant contains at most two almost long toasts, and two of them leave a single corner free. An almost long toast and its short side take up a stretch of $k$ consecutive corners. Two compatible almost long toasts take up disjoint stretches, since each lies on the long side of the other, the short side being too small. Three of them would need $3k$ corners, more than the $2k + 1$ available, and two of them take up $2k$ corners, leaving a single one free.
Now let $t \geq 1$ more people stand in a small crowd closer to the centre than all the long toasts, no three people in a line. Then a toast between the crowd and a corner crosses a toast between two other corners exactly when the corner is on the short side of the latter: the long toasts are the toasts between corners closest to the centre, so the crowd is on the same side of every toast between corners as the long side of that toast, while the corners of its short side are on the other side. Give the weight $t + 1$ to the long toasts, $t$ to the almost long ones, $1$ to the toasts between the crowd and a corner, and $0$ to the others, for a total weight of $(t + 1)m + tm + tm = (3t + 1)m$, and take an instant. If it contains a long toast and an almost long one, no corner is left for the crowd, and it weighs $2t + 1$. If it contains a long toast but no almost long one, it weighs at most $(t + 1) + t$, since each person of the crowd clinks at most once. If it contains two almost long toasts, at most one person of the crowd clinks with a corner, and it weighs at most $2t + 1$ again. Otherwise, it weighs at most $t + t$. So at least
\begin{equation*} \frac{(3t + 1)m}{2t + 1} = \frac32 m - \frac{m}{2(2t + 1)} \end{equation*}instants are needed. For $n \geq 8$, take $t = \lceil \sqrt{n/6} \, \rceil$ and $m$ the largest odd number at most $n - t$, and put the last person, if any, anywhere: adding people never helps. Since $m \geq n - t - 1$ and $m \leq n$, there are at least $\tfrac32 (n - t - 1) - \tfrac{n}{4t} \geq \tfrac32 n - \sqrt{3n/2} - 3$ instants. For $n \leq 7$, this is less than $n$, and the round table is enough.
Is this lower bound sharp, or could these configurations need even more instants? To see whether the weighting argument loses anything, we can test it on the very configurations it is applied to. For a regular polygon of $n - 1$ people with a single person at its centre, the case $t = 1$, it gives $\lceil 4(n-1)/3 \rceil$ instants when $n \geq 6$ is even, and an explicit schedule, built from the mirror rounds of the polygon, reaches exactly this number (proof in the appendix). So, at least in this case, the argument is tight: these configurations need exactly as many instants as it predicts.
Theorem 5 also answers a question of Dumitrescu, Pach, Saghafian and Scott [4] about paths. A non-crossing path is a sequence of people in which everybody toasts the next one, without any two of these arms crossing. A path has at most $n - 1$ toasts, so at least $n/2$ paths are always needed to cover all the toasts, and they asked whether some configurations need $cn$ paths, for some $c > 1/2$. They do. The first, third, fifth… toasts of a non-crossing path share nobody and do not cross, so they can all happen at the same instant, and so can its second, fourth, sixth… toasts. Covering all the toasts with $p$ paths thus gives a schedule in $2p$ instants, and the configurations of Theorem 5 need about $\tfrac32 n$ instants.
If any of this gives you an idea, or if you have seen some of these results somewhere before, I would be happy to discuss it. In the meantime, at your next apéritif with an even number of friends, you know what to expect: $n$ instants, not $n - 1$, unless you all stand around a bar. Santé!
Appendix: proofs of the variants
Here are the complete proofs of the results on the variants, folded so as not to stand in the way. The ideas are those of the round table: counting what every instant wastes, and mirror rounds.
A polygon with one person at its centre
For odd $m = 2k + 1 \geq 5$, the $m$ people at the corners of a regular polygon and one more at its centre can all clink in $m + \lceil m/3 \rceil = \lceil 4m/3 \rceil$ instants, which matches the lower bound of Theorem 5 with $t = 1$.
Show the proof
We number the corners modulo $m$. As around a round table, the toasts between corners split into the $m$ mirror rounds $C(u) = \{\{u - t, u + t\} : 1 \leq t \leq k\}$, in which $u$ sits out. The toast from the centre to a corner $v$ crosses a toast between two other corners exactly when $v$ is on its short side, as in the proof of Theorem 5. The toast $\{u - t, u + t\}$ has $u$ on its short side exactly when $2t \leq k$. A toast between two corners of a stretch of at most $k + 1$ consecutive corners has its short side inside the stretch. And toasts lying in disjoint stretches do not cross. Let $q = \lceil m/3 \rceil$ and $U = \{1, 4, 7, \dots, 3q - 2\}$: these $q$ numbers are distinct modulo $m$, and every corner is in $U$ or next to one of its elements.
A mirror round $C(u)$: $u$ sits out, and the toasts with $2t \leq k$, in amber, have $u$ on their short side.
The toasts from the centre to the corners on the short side of a toast, shaded, cross it (dashed), and the others do not.
Toasts inside a stretch of at most $k + 1$ corners keep their short side inside it, and toasts in disjoint stretches do not cross.
$U = \{1, 4, 7\}$, circled: every corner is in $U$ or next to one of its elements.
If $k$ is odd, let $a = (k + 1)/2$, and split each mirror round $C(u)$ into $A(u)$, its toasts with $t \lt a$, which lie in the stretch of the $k$ corners from $u - a + 1$ to $u + a - 1$, and $B(u)$, its other toasts, which do not have $u$ on their short side. Let $W = aU$ be the set of the corners $au$ for $u \in U$. Every corner is in $W$ or at distance $a$ from a corner of $W$. Indeed, $a$ has an inverse modulo $m = 4a - 1$, namely $4$, since $4a = m + 1$, so every corner $x$ can be written $x = ay$ for some corner $y$. This $y$ is in $U$ or next to an element $u$ of $U$, so $x$ is either $au$, in $W$, or $au \pm a$, at distance $a$ from $au$.
$A(u)$, in amber, and $B(u)$, in blue: the toast from the centre to $u$, dashed, crosses $A(u)$ only.
$W = \{0, 1, 2\}$, circled: every other corner is at distance $a = 2$ from one of them (dotted).
There are three kinds of instants in the schedule: one for each corner $v$ that is not in $W$, and two for each corner $w$ of $W$. The last paragraph counts them and checks that every pair clinks.
- for each corner $v$ not in $W$: the centre with $v$, and $B(v)$;
- for each corner $w$ in $W$: the centre with $w$, $A(w + a)$, which lies in the stretch from $w + 1$ to $w + k$, and $A(w - a)$, which lies in the stretch from $w - k$ to $w - 1$;
- for each corner $w$ in $W$: the mirror round $C(w)$.
A corner $v$ not in $W$, here $4$: the centre with $v$, and $B(v)$.
A corner $w$ of $W$, here $0$: the centre with $w$, and $A(w + a)$ and $A(w - a)$ in their stretches.
The whole mirror round $C(w)$ of the same corner $w = 0$.
If $k$ is even, let $b = k/2$ and $s = 3b$, and split $C(u)$ into $A(u)$, its toasts with $t \leq b$, in the stretch of the $k + 1$ corners from $u - b$ to $u + b$, and $B(u)$, its other toasts, in the stretch of the $k$ corners from $u + b + 1$ to $u - b - 1$. Let $W = kU - b$ be the set of the corners $ku - b$ for $u \in U$. Every corner is in $W + s$ or at distance $b$ from a corner of $W$. Indeed, $k$ has an inverse modulo $m = 2k + 1$, namely $-2$, since $2k = m - 1$, so every corner $x$ can be written $x = ky$ for some corner $y$, which is $u$, $u - 1$ or $u + 1$ for some $u \in U$. With $w = ku - b$, a corner of $W$, and $k = 2b$, the corner $x$ is then $w + b$, $w - b$ or $w + 3b = w + s$.
$A(u)$, in amber, and $B(u)$, in blue: the toast from the centre to $u$, dashed, crosses $A(u)$ only.
$W = \{2, 5, 8\}$, circled, which is here also $W + s$: every other corner is at distance $b = 2$ from one of them (dotted).
There are three kinds of instants in the schedule: one for each corner $v$ that is not in $W$, and two for each corner $w$ of $W$. The last paragraph counts them and checks that every pair clinks.
- for each corner $v$ not in $W$: the centre with $v$, and $A(v + s)$, which lies in the stretch from $v + k$ to $v + 2k$;
- for each corner $w$ in $W$: the centre with $w$, $B(w - b)$ and $B(w + b)$, which lie in the stretches from $w + 1$ to $w + k$ and from $w + k + 1$ to $w + 2k$;
- for each corner $w$ in $W$: the mirror round $C(w + s)$.
A corner $v$ not in $W$, here $0$: the centre with $v$, and $A(v + s) = A(6)$ in the stretch from $v + k$ to $v + 2k$.
A corner $w$ of $W$, here $2$: the centre with $w$, and $B(w - b) = B(0)$ and $B(w + b) = B(4)$ in their stretches.
The whole mirror round $C(w + s)$, here $C(8)$ for $w = 2$.
In both cases, by the four facts above, no arms cross: the toasts between corners of an instant either form part of a mirror round or lie in disjoint stretches, and the centre clinks with a corner that is on the short side of none of them. Every toast with the centre happens exactly once. It remains to see that every toast between corners happens, that is, that every mirror round $C(u)$ is played, either whole or in its two parts $A(u)$ and $B(u)$:
- for odd $k$: if $u$ is in $W$, then $C(u)$ is played whole. Otherwise, $B(u)$ is played with the centre and $u$ itself, and $A(u)$ with the centre and the corner $w$ of $W$ at distance $a$ from $u$, since $u = w + a$ or $u = w - a$;
- for even $k$: if $u$ is in $W + s$, then $C(u)$ is played whole. Otherwise, $A(u)$ is played with the centre and $u - s$, which is not in $W$, and $B(u)$ with the centre and the corner $w$ of $W$ at distance $b$ from $u$, since $u = w + b$ or $u = w - b$.
In total, this makes $(m - q) + q + q = m + \lceil m/3 \rceil$ instants.
Greedy toasting
A greedy schedule, which makes as many new toasts as possible at each instant, takes at most $n(1 + \ln(n/2))$ instants. The proof is the classical analysis of the greedy algorithm for set cover [8].
Show the proof
When an instant makes $g$ new toasts, charge each of them $1/g$, so that the number of instants is the total charge. Fix a mirror round $C_s$, and list its $c \leq n/2$ pairs in the order in which they first clink, $e_1, \dots, e_c$. Just before $e_i$ first clinks, the pairs $e_i, \dots, e_c$ have not clinked yet, and together they form a valid instant, as part of a mirror round. So the greedy schedule makes at least $c - i + 1$ new toasts at that instant, and $e_i$ is charged at most $1/(c - i + 1)$. The pairs of $C_s$ are thus charged at most $1 + \tfrac12 + \dots + \tfrac1c \leq 1 + \ln(n/2)$ in total, and the $n$ mirror rounds contain every pair exactly once.
Appendix: computer searches
Here is the code behind every computer search of this post. Each script is self-contained and needs Python 3, and one of them a SAT solver, installed with pip install python-sat, which had no build for Python 3.14 yet when I wrote this.
Greedy toasting
The worst greedy schedules, by an exhaustive search over the ways greedy can break ties: up to 18 instants for 9 people, 24 for 11 and 26 for 12.
Show the code
"""Worst greedy schedules around a round table.
A greedy schedule makes, at each instant, as many new toasts as possible. For each
table, this finds the largest number of instants a greedy schedule can take, over
all the ways of breaking ties, by an exhaustive search. The search skips the runs
that cannot beat the current target, using the bound of the appendix: from the set
U of pairs that have not clinked yet, a greedy run lasts at most the sum over the
mirror rounds C_s of 1 + 1/2 + ... + 1/|C_s & U| more instants.
Run: python3 greedy.py 12 (about five minutes, mostly for 12 people)
"""
import sys
from fractions import Fraction
from functools import lru_cache
def worst_greedy(n):
pair = {} # each pair is a bit of an integer
for i in range(n):
for j in range(i + 1, n):
pair[i, j] = 1 << len(pair)
@lru_cache(maxsize=None)
def matchings(lo, hi): # instants among the people lo..hi
if lo > hi:
return (0,)
out = list(matchings(lo + 1, hi)) # lo does not clink
for j in range(lo + 1, hi + 1): # lo clinks with j
out += [a | b | pair[lo, j] for a in matchings(lo + 1, j - 1) for b in matchings(j + 1, hi)]
return tuple(out)
size = lambda m: bin(m).count('1')
instants = sorted(set(matchings(0, n - 1)) - {0}, key=size, reverse=True)
mirror = [sum(pair[i, j] for (i, j) in pair if (i + j) % n == s) for s in range(n)]
H = [sum(Fraction(1, i) for i in range(1, c + 1)) for c in range(n + 1)]
def bound(U): # no greedy run from U lasts longer
return int(sum(H[size(U & c)] for c in mirror))
def greedy_choices(U): # instants with the most new toasts
best, out = 0, []
for m in instants:
if m & U == m:
if size(m) < best:
break
best = size(m)
out.append(m)
return out
reached, failed = {}, {}
def lasts(U, T): # can a greedy run from U last T more instants?
if T <= 0:
return True
if U == 0 or bound(U) < T or failed.get(U, T + 1) <= T:
return False
if reached.get(U, 0) >= T:
return True
for m in greedy_choices(U):
if lasts(U & ~m, T - 1):
reached[U] = T
return True
failed[U] = T
return False
everybody = sum(pair.values())
T = bound(everybody)
while not lasts(everybody, T):
T -= 1
return T
for n in range(3, int(sys.argv[1]) + 1 if len(sys.argv) > 1 else 10):
print(f'{n} people: an unlucky greedy schedule takes up to {worst_greedy(n)} instants', flush=True)Running python3 greedy.py 12 prints the following, in about five minutes.
3 people: an unlucky greedy schedule takes up to 3 instants
4 people: an unlucky greedy schedule takes up to 4 instants
5 people: an unlucky greedy schedule takes up to 7 instants
6 people: an unlucky greedy schedule takes up to 8 instants
7 people: an unlucky greedy schedule takes up to 12 instants
8 people: an unlucky greedy schedule takes up to 14 instants
9 people: an unlucky greedy schedule takes up to 18 instants
10 people: an unlucky greedy schedule takes up to 19 instants
11 people: an unlucky greedy schedule takes up to 24 instants
12 people: an unlucky greedy schedule takes up to 26 instantsShort arms
Which tables can toast in $2d + 1$ instants when everybody reaches the $d$ closest people on each side, by a SAT solver, and the gluing that covers every table from $2d^2$ people on.
Show the code
"""Short arms: everybody only reaches the d closest people on each side.
For each reach d, this checks with a SAT solver which tables can toast in 2d + 1
instants, and proves that every table of at least 2d^2 people can. As people only
reach their neighbours, two schedules that coincide on the toasts of d consecutive
people can be cut there and glued into a schedule for the sum of the two tables. So
it is enough to find schedules for every table of 2d^2 to 4d^2 - 1 people that all
coincide on the toasts of the people 0, ..., d - 1: gluing them gives every larger
table.
Needs: pip install python-sat
Run: python3 short_arms.py (about two minutes)
"""
from itertools import combinations
from pysat.solvers import Cadical153
def conflict(p, q, n):
"""Do two toasts share somebody, or cross?"""
(a, b), (c, d) = p, q
if len({a, b, c, d}) < 4:
return True
inside = lambda x: 0 < (x - a) % n < (b - a) % n
return inside(c) != inside(d)
def schedule(n, d, fixed=None):
"""Instants (from 0 to 2d) for the toasts {i, i + a}, a = 1..d, numbered
t = d*i + a - 1, or None if 2d + 1 instants are not enough."""
R = 2 * d + 1
toasts = [(i, (i + a) % n) for i in range(n) for a in range(1, d + 1)]
x = lambda t, r: R * t + r + 1 # "toast t happens at instant r"
with Cadical153() as solver:
for t in range(len(toasts)):
solver.add_clause([x(t, r) for r in range(R)])
for t, u in combinations(range(len(toasts)), 2):
if conflict(toasts[t], toasts[u], n):
for r in range(R):
solver.add_clause([-x(t, r), -x(u, r)])
if fixed is None:
# Person 0's 2d toasts and the toast of their two neighbours pairwise
# conflict, so they happen at different instants, which we may number.
alice = [(0, a) for a in range(1, d + 1)] + [(n - a, 0) for a in range(1, d + 1)] + [(n - 1, 1)]
fixed = {d * i + (j - i) % n - 1: r for r, (i, j) in enumerate(alice)}
for t, r in fixed.items():
solver.add_clause([x(t, r)])
if not solver.solve():
return None
model = set(solver.get_model())
return {t: next(r for r in range(R) if x(t, r) in model) for t in range(len(toasts))}
def report(d, small):
L = 2 * d * d
fail = [n for n in small if schedule(n, d) is None]
print(f'd = {d}: {2 * d + 1} instants are not enough for n in {fail}', flush=True)
first = schedule(L, d)
window = {t: first[t] for t in range(d * d)} # the toasts of the people 0, ..., d - 1
glued = all(schedule(n, d, window) is not None for n in range(L, 2 * L))
print(f' schedules through a common stretch for every n from {L} to {2 * L - 1}: {glued}', flush=True)
if glued:
print(f' so {2 * d + 1} instants suffice for every n >= {L}', flush=True)
for d in (2, 3, 4):
report(d, range(2 * d + 1, 2 * d * d))
report(5, [49]) # smaller tables are not checked for d = 5Running python3 short_arms.py prints the following, in about two minutes.
d = 2: 5 instants are not enough for n in [7]
schedules through a common stretch for every n from 8 to 15: True
so 5 instants suffice for every n >= 8
d = 3: 7 instants are not enough for n in [8, 9, 10, 11, 13, 17]
schedules through a common stretch for every n from 18 to 35: True
so 7 instants suffice for every n >= 18
d = 4: 9 instants are not enough for n in [10, 11, 12, 13, 14, 15, 16, 17, 19, 21, 22, 23, 26, 31]
schedules through a common stretch for every n from 32 to 63: True
so 9 instants suffice for every n >= 32
d = 5: 11 instants are not enough for n in [49]
schedules through a common stretch for every n from 50 to 99: True
so 11 instants suffice for every n >= 50How to cite this post
If this post is useful for your work, you can cite it as: C. Lalanne, A few reflections surrounding toasts around a round table, blog post, October 2026, clemlal.github.io/blog/round-table-toasts. Or, with BibTeX:
@misc{lalanne2026toasts,
author = {Lalanne, Cl{\'e}ment},
title = {A few reflections surrounding toasts around a round table},
year = {2026},
month = oct,
howpublished = {\url{https://clemlal.github.io/blog/round-table-toasts/}},
note = {Blog post}
}References
- G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy and J. Urrutia. On the chromatic number of some geometric type Kneser graphs. Computational Geometry, 32(1):59–69, 2005.
- S. B. Overbay. Generalized Book Embeddings. PhD thesis, Colorado State University, 1998.
- A. Biniaz, P. Bose, A. Maheshwari and M. Smid. Packing plane perfect matchings into a point set. Discrete Mathematics & Theoretical Computer Science, 17(2):119–142, 2015.
- A. Dumitrescu, J. Pach, M. Saghafian and A. Scott. Covering complete geometric graphs by monotone paths. Combinatorics and Number Theory, 15(1):73–82, 2026.
- E. Mendelsohn and A. Rosa. One-factorizations of the complete graph: a survey. Journal of Graph Theory, 9(1):43–65, 1985.
- H. Hopf and E. Pannwitz. Aufgabe Nr. 167. Jahresbericht der Deutschen Mathematiker-Vereinigung, 43:114, 1934.
- P. C. Kainen, S. Joslin and S. Overbay. On dispersability of some circulant graphs. Journal of Graph Algorithms and Applications, 28(1):225–241, 2024.
- V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233–235, 1979.
- H. M. Trao, G. L. Chia, N. A. Ali and A. Kilicman. Non-crossing perfect matchings and triangle-free geometric graphs. arXiv:1611.10058, 2016.