Therefore, at some point we will either reach a 65536 tile, in which case we will be done, or we will reach an ideal state with the total value of all tiles equaling at least 65536. Moreover, the total value of all values on the board will do nothing but increase. We will be able to follow this strategy continually as long as there is no 65536 tile on the board. Thus after the entire process we are left in another ideal state. But due to the nature of our "ideal state" strategy, the left, right, and up slides will never modify any tiles but the two lowest ones which are combining. After this, we can recursively combine the lowest two tiles if they have equal value, by sliding left, right, or up, depending on the board state. Then we can choose to spawn the 2 in the open space with the highest label. Since there are only 15 distinct tile values less than 2^16, there must be an open space. Then, suppose we are in an ideal state with all the tiles less than 65536 = 2^16. This matches the general pattern of the picture above. , k for some k, and (2) if two tiles a and b are on the board, with a located on a bigger label than b, then the value of tile a is greater than the value of tile b. Label the 4 x 4 grid with the numbers 1 through 16, with the numbers in the following pattern: 13 14 15 16Ĭall a board state "ideal" if it has the following properties: (1) the tiles that are filled are exactly 16, 15, 14. Proof that 65536 is theoretically possible.
no two tiles could have combined and there was no space left on the board. But then the position would have been a losing position, i.e. , 2^15, 2^16, and the entire 4x4 grid must have been filled. Therefore the set S must have initially consisted of one each of the numbers 2, 4, 8. + 2^1 cannot be written as a sum of anything less than exactly 16 distinct powers of two (using unique representation in binary). Recursively adding together pairs of equal elements of S until all the elements are distinct (i.e., adding them as if they had combined in the game), we obtain a set R with at most 16 distinct powers of two adding to get 131070. Then at this time there was a set S of at most 16 powers of two adding to get 131070. Thus at some point in time, the sum of all the tiles was exactly 131070 (= 131072 - 2). That at this time the sum of all the tiles is at least 131072. Suppose towards contradiction that at some point in time the 131072 tile is attained. It is easy to adapt the proof to show that 131072 is the maximum when 4 may also appear.Īt every step of the game, the total value among all tiles goes up by 2, or stays the same. I will prove that 65536 is the maximum when 2 is the only tile which appears newly on the board. Next is 131072 which will require at least 17 tiles which can't fit on the board.ĮDIT: Since the game pops up some 4's at times, 131072 is still theoretically possible if the last tile that pops up is a 4 making the board look like this:ġ31072: 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 4īlueFlame gives an essentially correct answer, but I wanted to add a rigorous proof (for anyone looking for it). Since that's less than 16 (max number of tiles that can fit), 4096 is possible. These can be combined from right to left to get to 4096. We've 16 squares in total and considering the new tile popped up at the position we chose, to make it to 4096, we need minimum these tiles:Ģ048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 2 Let's ignore that possibility for the sake of simplicity. In the original game, sometimes the new tile that pops up is a 4.