  The 2048 game involves tiles labeled with powers of two that can be merged to
form bigger powers of two; variants of the same puzzle involve similar merges
of other tile values. We analyze the maximum score achievable in these games by
proving a min-max theorem equating this maximum score (in an abstract
generalized variation of 2048 that allows all the moves of the original game)
with the minimum value that causes a greedy change-making algorithm to use a
given number of coins. A widely-followed strategy in 2048 maintains tiles that
represent the move number in binary notation, and a similar strategy in the
Fibonacci number variant of the game (987) maintains the Zeckendorf
representation of the move number as a sum of the fewest possible Fibonacci
numbers; our analysis shows that the ability to follow these strategies is
intimately connected with the fact that greedy change-making is optimal for
binary and Fibonacci coinage. For variants of 2048 using tile values for which
greedy change-making is suboptimal, it is the greedy strategy, not the optimal
representation as sums of tile values, that controls the length of the game. In
particular, the game will always terminate whenever the sequence of allowable
tile values has arbitrarily large gaps between consecutive values.

Discrete Mathematics