## April 2014 solution

The largest value that can appear on a square in our "2048" variant is 131,072.

The following amazingly-elegant proof that 131,072 is an upper bound was found by quite a few of this month's solvers. The version I am quoting here came from Yuping Luo, who was the first to present it. (Thanks, Yuping!)

"We evaluate a game by summing up the values in all squares and then calculating the number of 1's in the binary representation of the sum. This number of 1's is the minimum number of non-empty squares. It's easy to see that the sum can only increase by 0, 2 or 4 at each step. If we have one 218, the sum must be at least 218, and at some previous point in time it must have been 218-2 or 218-4. If the sum is 218-2, the number of 1's in its binary representation is 17, which is greater than 16. That's obviously impossible. If the sum is 218-4, the number of 1's is 16, so for each k in the range 2 ≤ k ≤ 17, there is exactly one 2k in some square. That means the board is filled and we cannot merge any more --- game over! So it's impossible to make 218."

To show that this upper bound is tight for our "2048" variant, we describe a game reaching 131,072.

Let us number the positions on the grid as follows.

 16 15 14 13 9 10 11 12 8 7 6 5 1 2 3 4

Because we are describing a "possible" game, rather than a "likely" game, we are free to choose at each turn which square will be created and at what position. We choose as follows:

Let k be the highest-numbered position that is occupied by a square. If the square's value is "4", we create a new "4" at position k+1. Otherwise, we create a new "4" at position k+2.

The player's strategy is as follows: if a new square was just created "at position k+2", the player's move is to drop it towards position k+1. In all other cases, there will necessarily be exactly one pair of identically-valued squares on the grid and these will necessarily be adjacent. (They will be the lowest-valued squares on the grid and the ones at the two highest-numbered occupied positions. All lower-numbered positions on the board will be occupied, and the squares occupying them will have values that are monotone strictly decreasing with position numbers.)

The player's move is to drop the identically-valued square in the higher-numbered position onto its counterpart with the lower-numbered position. This move will necessarily not cause any other square to shift its position and will retain all invariants described above (possibly allowing the player to continue with more "merge" rounds, as is permitted in our game variant).

I leave it as an exercise to the readers to show that this strategy does, indeed, culminate in a square of value 131,072, and, in fact, can be continued until the total of the values of all squares is 262,140, the maximum possible. (This is not, however, the strategy that allows the game to continue for the largest possible number of rounds. I leave this latter question as another exercise for the reader.)

Note that at no point in this strategy does the player ever choose the direction "up".

Last note: I do not know if 131,072 can also be attained in the original "2048". I suspect that it cannot.