CHICAGO — An intriguing and whimsical pure math puzzle has a new solution, thanks to three recent DePaul University mathematics alumni and their professor, T. Kyle Petersen. “The Malicious Maitre d’” problem was formulated with input from great mathematicians and computer scientists from Google, Bell Labs and Princeton in the early 2000s. The DePaul students took a detour from their assigned reading to make a new discovery, which is now published in
The American Mathematical Monthly.
In the problem, diners are seated at a round table with napkins centered between place settings. The puzzle asks: As diners reach left and right, unsure of which napkin to take, how many will be left napkinless? And to make things more interesting: What if the maitre d’ is sabotaging the table, plotting to leave diners without a napkin?
There are many variables to consider, but one analysis shows that if the diners sit completely randomly, and select napkins completely randomly, about 12% of diners are left without a napkin. If the diners are seated by a malicious maitre d’, a previously described strategy showed you could expect more than 16% of the diners to be napkinless. The DePaul students used tools from enumerative combinatorics to create a solution that leaves about 18% of diners napkinless: “A More Malicious Maitre d’.”
Math 'for the sake of beauty'
As pure mathematicians, the alumni — Reed Acton, Blake Shirman and Daniel Toal — don’t always have an accessible way to talk about their work. The napkin problem, however, was easy to chat about with colleagues and friends. “In pure math, you’re doing it for the sake of beauty and rigorous, logical thought,” said Acton, who graduated in June with a master’s degree.
Petersen first learned about the puzzle from the work of Dartmouth professor Peter Winkler, a longtime researcher at Bell Labs and author of “Mathematical Puzzles: A Connoisseur’s Collection.” Winkler’s tome contains the original problem attributed to Princeton’s John H. Conway. Later, computer scientist Rob Pike, now of Google, proposed to find the worst possible order for the diners to be seated.
As a graduate student himself, Petersen and coauthor Anders Claesson reproduced the main result of Conway’s napkin challenge. In 2021, Petersen assigned his own 2007 paper as reading for the students, with the goal to teach them more about a tool in combinatorial mathematics known as generating functions. Instead, the students kept returning with questions about Winkler’s puzzle.
“It was true serendipity how this all played out,” said Acton. “We veered off course doing our own research, but it turned out the best way to prove what needed to be proved was by using generating functions.” Winkler’s best strategy for the maitre d’ set traps—leaving diners stranded without napkins.
Finding a more malicious algorithm
The DePaul students wondered what would happen if the maitre d focused on the napkins rather than the diners. They created a solution that intentionally seats each sequential diner at a place with two napkin options, including one they would have to shun or abandon. They call this approach napkin shunning, and it greatly increased the number of napkinless diners.
“We were just starting to realize there was something interesting happening. We decided to just keep going and to see what we could prove here,” Petersen said. And while the students had certainly taken a different path, the research returned them back to the original learning objectives.
“To my delight, generating functions play a big role in key pieces of this,” Petersen said. “Winkler was so brief about trap setting, so a third of the paper is devoted to defining Winkler’s theory really crisply. Then we use generation function techniques to prove that yes, we had found a new formula.”
Petersen praised the students for their persistence. “What we’re hoping to develop in students is ownership of ideas,” he said. “We want to empower students to ask good questions and to demand answers they can understand themselves.”
As far as applications for the new algorithm, it may be of use to computer scientists or others creating models for worst case scenarios. For Acton and his classmates, that wasn’t really the point.
“Pure math is foundational to science,” Acton said. “But we also did this because it was fun.”
###
Source:
T. Kyle Petersen
t.kyle.petersen@depaul.edu
Media Contact:
Kristin Claes Mathews
kristin.mathews@depaul.edu