Optimal Token Allocations in Solitaire Knock'm Down

Authors

Arthur T. Benjamin, Harvey Mudd CollegeFollow
Mark L. Huber, Claremont McKenna CollegeFollow
Matthew T. Fluet '99, Harvey Mudd CollegeFollow

Student Co-author

HMC Undergraduate

Document Type

Article

Department

Mathematics (HMC), Mathematics (CMC)

Publication Date

8-14-2000

Abstract

In the game Knock 'm Down, tokens are placed in N bins. At each step of the game, a bin is chosen at random according to a fixed probability distribution. If a token remains in that bin, it is removed. When all the tokens have been removed, the player is done. In the solitaire version of this game, the goal is to minimize the expected number of moves needed to remove all the tokens. Here we present necessary conditions on the number of tokens needed for each bin in an optimal solution, leading to an asymptotic solution.

Comments

Previously linked to as: http://ccdl.libraries.claremont.edu/u?/irw,451.

First published in the Electronic Journal of Combinatorics, vol. 8, no. 2 (2001).

Publisher pdf, posted with permission.

Rights Information

© 2001 The Electronic Journal of Combinatorics

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

Benjamin, Arthur T., Mark L. Huber, and Matthew T. Fluet. "Optimal Token Allocations in Solitaire Knock'm Down." The Electronic Journal of Combinatorics 8.2 (2001): 1-8.