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:
- the upper left corner of $a \times b$ has color $1$ because $C$ divides $m-a$ and $n-b$;
- $a,b \lt C$;
- $x+C \le a+b-1 \iff x \le a+b-1-C$;
- $a+b-1-C \lt \min(a,b)$;
- $x+C \gt \max(a,b)$;
- $x+2C > a+b-1$;
- $x + [a+b-(x+C)] = a+b-C$.
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$.
What you did wrong:
Q can't be identical to P is correct but R can be identical since it is not adjacent to P
P,R can be identical
Q,S can be identical
Solution:
Case-I
P,R are identical
->P can take any of the four colors but R doesn't have a choice since it has to
take what P takes to be identical
->Q on the other hand can take 3 colors and so can R
So, 4.3.1.3 ( S either takes what Q takes or the any one of two remaining)
Case- II
P,R are different
-> 4.3.2.2
here S has two choices ( either take what q takes or take the remaining color)
Total no. of ways = 84
Best Answer
The maximum is 52, as shown in OEIS A072567. Here's a coloring that achieves that maximum:
I used integer linear programming, as follows. Let binary decision variable $x_{i,j}$ indicate whether square $(i,j)$ is colored. The problem is to maximize $\sum_{i,j} x_{i,j}$ subject to $$\sum_{i\in\{i_1,i_2\}} \sum_{j\in\{j_1,j_2\}} x_{i,j} \le 3$$ for all $1\le i_1<i_2 \le 13$ and $1\le j_1<j_2 \le 13$. This "no-good" constraint prevents all four squares in a rectangle from being colored.