# 2048 Tiles

“2048 Tiles” [1], has recently gone viral on social network platforms. The aim of the game is to make the number 2048 appear on one of the tiles. Personally, I was able to reach 512 quite easily, but haven’t made any progress after that. However, since I have a natural inclination for lower bounds, here is a new (and less time consuming) challenge:

New Challenge: Is it possible to end the game with 4 as the largest number on any of the tiles?*

A lower bound of 4 is trivially true, otherwise we will have only 2′s on the board and this can be merged in any direction. It seems like a possible tight lower bound too. For instance, consider the following board:
2 4 2 4
4 2 4 2
2 4 2 4
4 2 4 2
The game would end in such a scenario, but is such a situation possible?
I think yes. If we just restrict to left-right movement, we can obtain any row of the above board and thus if the random opening of tiles is in our favour, then we get a lower bound of 4. However the probability that this happens is at most $10^{-13}$.

I played arbitrary moves for 10-20 games, and always ended up with a score of 64/128 (more of 128 and less of 64). If you were generous enough to call my arbitrary actions as random actions, then we know what the average score is and how far it is from the claimed lower bound and upper bound. (Also, can we prove the upper bound of 2048? — I think this should be possible, by accounting for the space needed to create one 2048 number).

[1] http://gabrielecirulli.github.io/2048/
* Piyush Kumar was one of the first to solve this challenge for largest number on board to be 8. (https://www.facebook.com/1piyush)

EDIT: As discussed in the comments, the upper bound of 131072 seems to be tight. This might provide some motivation to people who have already reached 4096.

## 2 thoughts on “2048 Tiles”

1. Looks like one can get 2^{n^2} as one upper bound (where n is the dimension of the square).
The arguement for this goes as follows. If you need to construct a 2^k, there must be a point when the board has at least one out of each of 2^{k-1}, 2^{k-2}, … 2^1. Hence, it is not possible to get a 2^{n^2+1}.

Can’t really say if this would be a tight upper bound.

• Your argument is almost correct, but you overlooked the possibility that sometimes, the tile opened at random contains 4 instead of 2. If 2^k was the highest possible value achievable, then we must have had two 2^{k-1}. One of those 2^{k-1} must have been formed using two 2^{k-2} and so on, we end up with there must exist two 8 and it must be formed with two 4. This gives us that 2^17 is an upper bound and this can be reached:
4 4 8 16
256 128 64 32
512 1024 2048 4096
65536 32768 16384 8192
The above table is theoretically possible to obtain and thus the upper bound of 2^17 is tight. Do you agree?