How many squares of each colour are in a generalized checkerboard $C$-coloured $m \times n$ rectangle?
Assume an $m\times n$ rectangle has been been divided into a grid of $mn$ unit squares, and the squares have been coloured with $C$ colours in such a way that the colours in any row or column cycle, i.e. if the colours are represented by the number $1,2,\dots, C$ then
$1 \rightarrow 2,\; 2 \rightarrow 3,\; \dots, C-1 \rightarrow C,\; C \rightarrow 1$, etc.
With this setup there are actually $C$ possible coloured variants, so we choose the variant that has a black square
in the $(1,1)$ position. Here is an example for $m = 10$, $n = 13$ and $C = 4$:
It has matrix representation
$$\begin{bmatrix}
1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 \\
2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 \\
3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 \\
4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 \\
1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 \\
2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 \\
3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 \\
4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 \\
1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 \\
2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2
\end{bmatrix}$$
Here we have number of squares of colour $1 = 33$,
number of squares of colour $2 = 33$,
number of squares of colour $3 = 32$,
and number of squares of colour $4 = 32$.
So what is the general formula? I'm hoping that this is a known problem and someone can point
me in the right direction (even if it is an open problem). Thank you.
Best Answer
Let $a = m \bmod C$ and $b = n \bmod C$ i.e. the remainders of $m,n$ divided by $C$.
As noted in the comments above, as long as we have a square or a rectangle with at least one side divisible by $C$, all the colors will be present in that square or rectangle and their occurrences will be all equal.
We note that we can decompose the $m \times n$ rectangle into four rectangles/squares: $(m-a) \times (n-b)$, $(m-a) \times b$, $a \times (n-b)$, $a \times b$.
The total occurrence of each color in the three regions $(m-a) \times (n-b)$, $(m-a) \times b$ and $a \times (n-b)$ will be exactly $(mn-ab)/C$.
We remain with the square or rectangle $a \times b$.
Let the color index be $x$, $1 \le x \le C$. We can note that:
Starting from the upper left corner of the region $a \times b$, we can start counting the occurrences of colors: if we look diagonally, we see that the first color $1$ appears $1$ time followed by color $2$ in two adjacent squares, followed by $3$ in three squares and so on till the minimum between $a$ and $b$ is hit. This takes place when reaching the lower left corner if $b<a$ or the upper right corner if $a<b$. After this, the occurrence of the following colors is constant and equal to $\min(a,b)$ till the maximum between $a$ and $b$ is hit. This takes place when reaching the upper right corner if $b<a$ or the lower left corner if $a<b$. After this, the occurrence of the following colors start to decrease till it reaches a minimum of $1$ at the lower right corner for color $a+b-1$ (the color index continued to increase while following half of the perimeter). Since for $\max(a,b) \le x \le a+b-1$ the function counting the occurrences in that interval is therefore $h(x) = k - x$ and $h(a+b-1) = 1$, then $k-(a+b-1)=1$ and thus $k=a+b$ and $h(x)=a+b-x$.
Up to now, we have four intervals where we know how to compute occurrences: they are $x \le \min(a,b)$, $\min(a,b) \lt x \lt \max(a,b)$, $\max(a,b) \le x \le a+b-1$ and $a+b-1 \lt x$ (this latter one is for missing colors, with occurrence equal to $0$).
We then need to examine if a color can belong to more than one interval, because given a color $x$, one of the above first three inequalities is satisfied with $x+jC$ ($j$ positive integer). For $j \ge 2$ this is not possible due to observations 2 and 6 above. We don't care about $a+b-1 \lt x+jC$ because there we already "exited" from the $a \times b$ region. We thus remain with the $x+C$ case: but due to observations 3 and 4 this can only occur in the first interval $x \le \min(a,b)$, and due to observation 4, more precisely only for $x \le a+b-1-C$. By the way, this does not take place always, but only when $a+b-1-C \ge 1$. Now, for colors $x \le a+b-1-C$ we have that the second contribute to count at $x+C$ is within the interval $\max(a,b) \le x+C \le a+b-1$ (observations 3 and 5), and therefore it contributes with a count of $a+b-(x+C)$ (see the above reasoning for that interval), which added to the contribute $x$ in the first interval gives a total of $a+b-C$ (observation 7).
Putting the above all together, we can then figure out a formula like this for the occurrence of color $x$ in $a \times b$, valid for $1 \le x \le C$:
$$g(x) = \begin{cases} a+b-C, & \text{if $x \le a+b-1-C$} \\ x, & \text{if $a+b-1-C \lt x \le \min(a,b)$} \\ \min(a,b), & \text{if $\min(a,b) \lt x \lt \max(a,b)$} \\ a+b-x, & \text{if $\max(a,b) \le x \le a+b-1$} \\ 0, & \text{if $a+b-1 \lt x$} \\ \end{cases} $$
And adding the first contribution above, the whole count formula, valid for $1 \le x \le C$, will be:
$$f(x) = \begin{cases} (mn-ab)/C + a+b-C, & \text{if $x \le a+b-1-C$} \\ (mn-ab)/C + x, & \text{if $a+b-1-C \lt x \le \min(a,b)$} \\ (mn-ab)/C + \min(a,b), & \text{if $\min(a,b) \lt x \lt \max(a,b)$} \\ (mn-ab)/C + a+b-x, & \text{if $\max(a,b) \le x \le a+b-1$} \\ (mn-ab)/C, & \text{if $a+b-1 \lt x$} \\ \end{cases} $$
Note that the third case can be stated as $\min(a,b) \le x \le max(a,b)$ as well (the evaluation on the extremes of adjacent intervals is always the same if done for one case or the other). Note also that the function returns correctly $(mn-ab)/C=mn/C$ if $a=0$ and/or $b=0$.