On an n x n grid with each space filled with a number between 1 and 4, such that each 2 x 2 sub grid of the grid contains no duplicate numbers, prove that in any 32 x 32 grid satisfying these properties that each corner will contain a different number.
An example grid that satisfies the properties:
1 2 1 2
3 4 3 4
2 1 2 1
4 3 4 3
I have the base case that in a 2 x 2 grid to fulfil the properties the corners must be different, but in the induction step I am having trouble proving that the corners must be different as the grid get larger.
Currently for my induction step I have:
When we expand the grid 2 to the right (from a 2x2) we must have the top right corner be a number from column 2 to hold the condition.
1 2 1 2
3 4 3 4
Therefore the top left and top right will be different. Next we expand 2 down and the bottom left corner must be a number from row 2 of the original 2x2 grid to hold the condition.
1 2 1 2
3 4 3 4
2 1
4 3
Therefore the bottom left and top left are different and the bottom right must be different from the top right for the condition to hold, similarly it must be different from the bottom left.
1 2 1 2
3 4 3 4
2 1 2 1
4 3 4 3
1 2 1 2
3 4 3 4
2 1 2 1
4 3 4 3
This all holds true to ensure the 2x2's between the for 2x2 grids that make up a 4x4 all have different numbers.
I am unsure how to prove the diagonally opposite corners are different.
First, if you do this by induction (which seems like an excellent idea!), then in your step you should not go from $2 \times 2$ to $4\times 4$, but from $2^n \times 2^n$ to $2^{n+1} \times 2^{n+1}$
OK, so assume the claim is true for any $2^n \times 2^n$ grid and take a $2^{n+1} \times 2^{n+1}$ grid. We can of course split that into $4$ square $2^n \times 2^n$ grids: let's call the top left square $A$, the top right square $B$, the bottom left square $C$, and the bottom right square $D$ (sorry, I am not good with graphics ... so please draw a schematic picture to follow my reasoning). Likewise, let's call the cell in the top left corner of any of these squares cell $1$, the top right cell $2$, the bottom left cell $3$, and the bottom right square $4$. Thus, when I use $C2$, I refer to the top right cell of the bottom left $2^n \times 2^n$ grid.
Now, as you already noted, you can never have the same number in the two corners on any of the sides of the grid: if there are two of the same numbers in the corners of the $2^{n+1} \times 2^{n+1}$ grid, then they have to be at opposite corners.
So, let's do a proof by contradiction to rule out having any two opposite corners having the same number. Now, by symmetry considerations, it is clear that without loss of generalization, we can assume that both $A1$ and $D4$ contain the same number $1$. How can we rule that out?
Well, if you look at the $2 \times 2$ square in the very middle of the $2^{n+1} \times 2^{n+1}$ grid, which consists of $A4$, $B3$, $C2$, and $D1$, by inductive hypothesis we cannot have a $1$ in $A4$ or $D1$, but this being a $2 \times 2$ square, it must contain a $1$, so there is a $1$ in either $B3$ or $C2$. Again by symmetry considerations, we can without loss of generalization assume there is a $1$ in $B3$.
Now, the two numbers in $A4$ and $B3$ will have to be the same numbers as in $C4$ and $D3$, but with a $1$ already in $D4$, and using the inductive hypothesis that the four corners of each of the $2^n \times 2^n$ grids will have to contain four different numbers, that means that there has to be a $1$ in $C4$.
Likewise, the two numbers in $B3$ and $D1$ will have to occur in $A3$ and $C1$, so there has to be a $1$ in either $A3$ or $C1$. But with a $1$ already in $A1$, and using the inductive hypothesis, there cannot be a $1$ in $A3$. And the $1$ in $C4$ rules out a $1$ in $C1$. So, we have a contradiction!
So, we see that assuming that the same number can occur in opposite corners leads to a contradiction, and so the same number cannot occur in opposite corners.