  In this paper we study the problem of the Malicious Maitre d', as described
in Peter Winkler's book Mathematical Puzzles: A Connoisseur's Collection. This
problem, attributed to computer scientist Rob Pike, involves seating diners
around a circular table with napkins placed between each pair of adjacent
settings. The goal of the maitre 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.
Winkler proposes a solution to the problem that he claims is optimal. We
analyze Winkler's solution using tools from enumerative combinatorics, then
present a new strategy that performs better.
