In this paper we study a variant of the Malicious Maître d' problem. This problem, attributed to computer scientist Rob Pike in Peter Winkler's book Mathematical Puzzles: A Connoisseur's Collection, involves seating diners around a circular table with napkins placed between each pair of adjacent settings. The goal of the maître d' is to seat the diners in a way that maximizes the number of diners who arrive at the table to find the napkins on both the left and right of their place already taken by their neighbors. Previous work described a seating algorithm in which the maître d' expects to force about 18\% of the diners to be napkinless. In this paper, we show that if the maître d' learns each diner's preference for the right or left napkin before they are placed at the table, this expectation jumps to nearly $1/3$ (and converges to $1/3$ as the table size gets large). Moreover, our strategy is optimal for every sequence of diners' preferences.
@article{10_37236_12788,
author = {Reed Acton and T. Kyle Petersen and Blake Shirman and Bridget Eileen Tenner},
title = {The clairvoyant ma{\^\i}tre d'},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/12788},
zbl = {1560.91065},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12788/}
}
TY - JOUR
AU - Reed Acton
AU - T. Kyle Petersen
AU - Blake Shirman
AU - Bridget Eileen Tenner
TI - The clairvoyant maître d'
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/12788/
DO - 10.37236/12788
ID - 10_37236_12788
ER -
%0 Journal Article
%A Reed Acton
%A T. Kyle Petersen
%A Blake Shirman
%A Bridget Eileen Tenner
%T The clairvoyant maître d'
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/12788/
%R 10.37236/12788
%F 10_37236_12788
Reed Acton; T. Kyle Petersen; Blake Shirman; Bridget Eileen Tenner. The clairvoyant maître d'. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/12788
