Dreidel Lasts $O(N^2)$ Spins
Abstract
Description
Dreidel is a popular game played during the festival of Chanukah. Players start with an equal number of tokens, donate one token each to a common pot, and take turns spinning a four-sided top, called the dreidel. Depending on the side showing up, the spinner takes all the tokens in the pot, takes half the tokens in the pot, gives a token to the pot, or does nothing. Whenever the pot goes empty, everyone donates a token to the pot. The game continues till all players, except one, go broke.
We prove that the expected length of a game of dreidel is at most quadratic in the number of tokens, irrespective of the number of players. This proves a conjecture of Doron Zeilberger.