The Cookie Monster Problem

This chapter examines the problem of the “Cookie Monster number.” In 2002, Cookie Monster® appeared in the book The Inquisitive Problem Solver by Vaderlind, Guy, and Larson, where the hungry monster wants to empty a set of jars filled with various numbers of cookies. The Cookie Monster number is the minimum number of moves Cookie Monster must use to empty all the jars. The chapter analyzes this problem by first introducing known general algorithms and known bounds for the Cookie Monster number. It then explicitly finds the Cookie Monster number for jars containing cookies in the Fibonacci, Tribonacci, n-nacci, and Super-n-nacci sequences. The chapter also constructs sequences of k jars such that their Cookie Monster numbers are asymptotically rk, where r is any real number, 0 ≤ r ≤ 1.