We'll prove that the number of color needed for input n is ceiling((n-1)^2/2),
ie. this OEIS sequence with offset 1.
First we prove that this number is needed.
To satisfy the condition, a square color should be different from all other
squares in a specific range related to n. This range is the union of all
retangles containing the initial square, and is a diamond shape centered at
this square. For example, n=5 corresponding to this diamond shape:
*
***
*****
***X***
*****
***
*
This diamond is the key throughout this whole proof.
We take n=5 for illustration purpose on this part, but the same procedure can
be used on any other n values.
Let's begin with any required rectangle. For example, consider 1x4 rectangle.
These 4 squares should have different color. Let's use @ to mark these
squares:
@@@@
There are a bunch of squares that needs to have different color with these
4. To find out which, put the diamond shape above on each @ position,
and take intersection of them. Stacking these 4 diamonds becomes:
1111
123321
12344321
123@@@@321
12344321
123321
1111
Where numbers represents a square that is covered by that many diamonds, and
@ still represents the original 1x4 square. The intersection of these four
diamonds is the original square and those 4 squares, namely:
44
@@@@
44
Because these squares are the intersection of all the diamonds, any two squares in it can be enclosed by a rectangle of required size. Therefore all these squares must use different colors.
You can try the same procedure on 2x3 squares; the intersection of those 6
diamonds is also in this shape.
Now we can list the final shape for differnt n values. They are:
n=6 n=7
n=4 n=5 # ##
n=2 n=3 # ## ### ####
# ## ### #### ##### ###### etc.
# ## ### ####
# ##
It's easy to conclude that the number of squares in this final picture is
ceiling((n-1)^2/2), hence the number of colors should be at least this many.
Now we prove that this number of colors is sufficient.
Consider this arrangement.
Alone one row in the plane, all these colors are lined up in a repeating
fashion. For example, n=6 requires 13 colors. If we label them A through
M, that row looks like:
..ABCDEFGHIJKLMABCDEFGHIJKLM..
Now, we find a "shift" value, call it s. The color of every other square is
the same of the square one above and s right, or one below and s left.
If we take s=5 here, the plane is colored as the following:
..............................
..ABCDEFGHIJKLMABCDEFGHIJKLM..
..FGHIJKLMABCDEFGHIJKLMABCDE..
..KLMABCDEFGHIJKLMABCDEFGHIJ..
..CDEFGHIJKLMABCDEFGHIJKLMAB..
..HIJKLMABCDEFGHIJKLMABCDEFG..
..MABCDEFGHIJKLMABCDEFGHIJKL..
..EFGHIJKLMABCDEFGHIJKLMABCD..
..............................
You can easily check that in this case, every 1x5, 2x4, 3x3, 4x2, 5x1
rectangles satisfy that no two squares in the rectangle has same color.
We now prove that for every n, there exists such "shift" value satisfy the
required condition. We claim that for even n, s = n-1 will do, while for
odd n, s = n-2 will do.
We label the colors with number starting from 0 to C-1, where C is the number
of colors, in the order of the first line colored. Thus the first line is
colored in color ..., 0, 1, 2, ..., C-1, 0, 1, 2, ..., C-1, 0, 1, .... The
way the other row colored is that the color below color n is color (n+s) mod C, where mod means remainder in mathematial term (returns 0 to C-1.)
To check whether we met the requirement, we need to check for all the squares
in the diamond shape above. In mathematical term, this means we need to check
all squares that have offset x squares down and y squares right, where
|x|+|y| <= n-2. (negative x and y means the opposite direction, hence
-3 squares down is 3 squares up, and -2 squares right is 2 squares
left.) Assuming the center square has color 0, the color in the target square
is (s*x+y) mod C, and we need to make sure that this is not color 0.
Because C = ceiling((n-1)^2/2) >= (n-1)^2/2 >= s^2/2, the range of s*x+y
can only be between -2C and 2C in the range |x|+|y| <= n-2 <= s. Thus we
only need to check whether s*x+y can be C or -C.
For even n = 2k, C = 2k^2-2k+1, s = 2k-1. Because C = (k-1)(2k-1)+k = k(2k-1)-(k-1), (x,y) = (k-1,k) and (k,-(k-1)) makes s*x+y = C, but their
|x|+|y| = 2k-1 > 2k-2 = n-2, so they are outside the diamond. The case of
-C is similar.
For odd n = 2k+1, C = 2k^2, s = 2k-1. Now C = k(2k-1)+k = (k+1)(2k-1)-(k-1), (x,y) = (k,k) and (k+1,-(k-1)) makes s*x+y = C, and
still |x|+|y| = 2k > 2k-1 = n-2, so they are also outside the diamond. The
case of -C is once again similar.
Now s*x+y can never be C or -C inside diamond, the color of these
squares (s*x+y) mod C can never be 0. So for any diamond, no second
square can have the same color as the center, satisfying the condition.
Therefore this arrangement with C colors and the specified "shift" value s
satisfies all condition, proved that C colors are sufficient. QED.