-3
$\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$
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$
  • 1
    $\begingroup$ Can you prove there's a sequence of tile spawns and moves that leads to this tile's creation? $\endgroup$ – user2357112 supports Monica Oct 28 '15 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$ – Fimpellizieri Oct 28 '15 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$ – user2357112 supports Monica Oct 28 '15 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$ – Fimpellizieri Oct 28 '15 at 22:45
  • 1
    $\begingroup$ Tiles will spawn while you're doing that and mess you up. $\endgroup$ – user2357112 supports Monica Oct 28 '15 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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