-4
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
9
  • 1
    $\begingroup$ Can you prove there's a sequence of tile spawns and moves that leads to this tile's creation? $\endgroup$ Commented Oct 28, 2015 at 21:47
  • $\begingroup$ 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$. $\endgroup$ Commented Oct 28, 2015 at 22:23
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Oct 28, 2015 at 22:29
  • $\begingroup$ 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. $\endgroup$ Commented Oct 28, 2015 at 22:45
  • 1
    $\begingroup$ Tiles will spawn while you're doing that and mess you up. $\endgroup$ Commented Oct 28, 2015 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.