The Most Malicious Maître D'
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916901693685760 |
|---|---|
| author | Madhavarapu, Tejo V. |
| author_facet | Madhavarapu, Tejo V. |
| contents | The problem of the malicious maître d' is introduced and solved by Peter Winkler in his book Mathematical Puzzles: A Connoisseur's Collection [1]. This problem is about a maître d' seating diners around a table, trying to maximize the number of diners who don't get napkins. Along with this problem, Winkler introduces a variation called the adaptive maître d' and presents a strategy. This problem was later investigated and a better strategy was discovered by Acton et al. [2]. We describe an even better strategy which we call ``long trap setting" and prove that it is optimal. We also derive a formula for the expected number of napkinless diners under our optimal strategy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09000 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Most Malicious Maître D' Madhavarapu, Tejo V. Combinatorics Discrete Mathematics 91A43 (Primary), 05C57 (Secondary) G.2.1 The problem of the malicious maître d' is introduced and solved by Peter Winkler in his book Mathematical Puzzles: A Connoisseur's Collection [1]. This problem is about a maître d' seating diners around a table, trying to maximize the number of diners who don't get napkins. Along with this problem, Winkler introduces a variation called the adaptive maître d' and presents a strategy. This problem was later investigated and a better strategy was discovered by Acton et al. [2]. We describe an even better strategy which we call ``long trap setting" and prove that it is optimal. We also derive a formula for the expected number of napkinless diners under our optimal strategy. |
| title | The Most Malicious Maître D' |
| topic | Combinatorics Discrete Mathematics 91A43 (Primary), 05C57 (Secondary) G.2.1 |
| url | https://arxiv.org/abs/2407.09000 |