-4

Playing on an $ n \times n $ grid, how can we determine the largest possible title you can achieve in a game, assuming the computer places tiles in the perfect spots.

warspyking
  • 14,500
  • 10
  • 78
  • 144

1 Answers1

1

The answer is $2^{n^2+1}$. This is because $n^2$ is the number of squares in an $n\times n$ grid, and the $+1$ comes from requiring that the last square spawned be a $4 = 2^2$.

Fimpellizzeri
  • 2,567
  • 1
  • 13
  • 21
  • 1
    Can you prove there's a sequence of tile spawns and moves that leads to this tile's creation? – user2357112 Oct 28 '15 at 21:47
  • It's easy to see that in order to form a square of value $2^{m+1}$, having already a square of value $2^m$, you will need to fill $m$ squares ($m \geq 2$); of course, this assumes perfect conditions. For instance, in order to form a square of value $8$, having already a square of value $4$, you will need two $4$'s, for a total of two squares. In order to to form a square of value $16$, having already a square of value $8$, you will need two $4$'s and one $8$, for a total of three squares. This goes on, and the maximum number of squares you can use is $n^2$. – Fimpellizzeri Oct 28 '15 at 22:23
  • 1
    That only argues that it's impossible to create a bigger tile. Can you prove creating a tile of value $2^{n^2+1}$ is actually possible? – user2357112 Oct 28 '15 at 22:29
  • Use the strategy described above, with base case a square $4$ spawned in a corner and going row by row in a zig-zag fashion. – Fimpellizzeri Oct 28 '15 at 22:45
  • 1
    Tiles will spawn while you're doing that and mess you up. – user2357112 Oct 28 '15 at 22:45
  • 'perfect spots' – Fimpellizzeri Oct 28 '15 at 22:46
  • Seriously, say you're merging 4+4+8+16+32+64+128 to produce 256. 6 tiles will spawn while you're doing that. How do you prove that you can place the spawns and perform the merges in such a way that once you have your 256, the rest of the board state isn't completely screwed up? – user2357112 Oct 28 '15 at 22:48
  • To produce $2^{n+2}$ ($n = 6$ in your example) we will have $n$ tile spawns. We may have these all be $2$ tiles if we wish, so they add up to $2n$, which is much much less than $2^{n+2}$. Even if the spawns were mostly all over the place there is, plenty of room to correct that with future spawns. We can continue this discussion in chat if you wish. – Fimpellizzeri Oct 28 '15 at 23:09
  • Let us continue this discussion in chat. – user2357112 Oct 28 '15 at 23:11