Given the following grid, how can I work out what the highest single value is and when I would need an additional square (or squares) to progess.
So in the first picture I've placed down four 1s. In the second picture two 1s have both been merged together to form a 2 and two more 1s have been placed. In the 3rd picture two 2s have been merged to form a 3, the two 1s have been merged to form a 2 and two more 1s have been placed. This process continues until I reach the bottom square with a 4,3,2,1
At this point I would need to increase the grid.
My question is, is there a way I can work out what the highest number is I can get with a particular grid size and after how many moves I would need to increase the size of the grid in order to progress?
Apologises if this is the wrong site. I wasn't sure whether to put this on here or whether it's suited more to one of the other communities.
There are a couple of things about this process that are unclear:
Do you need to perform all possible combinations in one move, or can you pick just one combination? (e.g. could you move from the first picture to having a single $2$ and three $1$'s?)
Do the numbers have to be located a certain way with respect to each other in order to be combined? (e.g from picture 4 to 5 you combined a couple of squares that are diagonal from each other, so I assume that is ok ... but can you combine squares that have other squares in between?)
If you can combine things in multiple ways, is there any forced preference to doing it one way rather than the other? (e.g from the first picture could you get the two $2$'s in the top row rather than the left column?)
Suppose we make the following assumptions in answer to these questions:
It is ok to just perform 1 combination at a time
We can combine any squares, no matter how far apart they are, as long as they have the same number
The result of combining two squares with number $n$ is to have 1 of the squares (doesn't matter with one) contain $n+1$, while the other contains $1$
With these assumptions, any grid (whether square, rectangular, hexagonal, irregular, etc.) starting with a $1$ in all of its $n$ squares will end up with the number $1$ through $n$ in its squares.
We'll prove by Induction:
Base: $n=1$. Trivial: the $1$ square ends up with $1$. Check!
Step: Suppose any grid of any shape ends up with numbers $1$ through $n$. Now consider a grid of any shape with $n+1$ squares. OK, focus on any subgrid with $n$ squares. By inductive assumption, this grid can be transformed into one with the numbers $1$ through $n$ in it. We still have one more square though, which has a $1$. Now, by another inductive proof we'll prove that:
For any grid that has $n+1$ squares, of which $n$ squares contain the numbers $1$ through $n$, and that has one 'extra' square containing the number $k$ with $1 \le k \le n$, can be transformed so that $n$ squares contain the numbers $1$ through $n$, and that has the extra square containing the number $k+1$
Proof by strong induction on $k$, assuming arbitrary $n$:
Suppose the claim holds true for all numbers smaller than $k$. Now consider that we have the number $k$ in the extra square, i.e. we have:
$$1 \ 2 \ 3 ... \ k-1 \ k \ k \ k+1 ... n$$
Combine the two $k$'s:
$$1 \ 2 \ 3 ... \ k-1 \ 1 \ k +1 \ k+1 ... n$$
By repeated use of the inductive assumption, we can now transform this step by step:
$$1 \ 2 \ 3 ... \ k-1 \ 2 \ k +1 \ k+1 ... n$$
$$1 \ 2 \ 3 ... \ k-1 \ 3 \ k +1 \ k+1 ... n$$
...
$$1 \ 2 \ 3 ... \ k-1 \ k \ k +1 \ k+1 ... n$$
And there you have it!