How many colors are necessary for a rectangle to never cover a color more than once?

If we have an infinite grid, and we color each cell, how many colors do we need so that a $m \times n$ rectangle always covers at most 1 of each color no matter how it is placed? (Rotation of the rectangle is allowed.)

It must be at least $mn$, but it seems $mn$ is not always enough.

Know results:

1. For $m \times 1$, the answer is $m$.
2. For $m \times m$ it is $m^2$.

Here is data from a computer program. Note that my program only considers periodic colorings with fundamental region the same area as the number of colors. So it is possible that colorings with less colors are possible if they are not arranged in this way.

The table below shows $k - mn$, where $k$ is the number of colors needed. The pattern seems obvious now (although a proof is still needed).

A few conjectures:

• For all cases in the table, if $mn$ is not enough, then it looks like $mn + m$ is for $m < n$. (False. turns out this is not true; $6 \times 4$ seems to require 32 colors. I updated the table above.)
• From my constructions it looks like $mn$ may be sufficient once $m$ is large enough for fixed $n$ (and vice versa). This is consistent with how rectangular tilings work. (Seems False.)
• From Gregory J. Puleo's comment: If $m$ divides $n$, it is plausible that $mn$ is enough. (If $m$ divides $n$, we can consider the rectangle a bar of larger squares, so by combining 1. and 2. from above we may be able to prove this.) (True. See his answer.)
• For $m \times (m + 1)$, the program finds colorings using $m(m + 2)$ colors. The fundemental region can be described by a parallelogram with two adjacent sides $(m(m + 2), 0)$ and $(m + 1, 1)$. These squares are marked yellow in the first table. Edit: In fact, for rectangles represented by a white cell it seems that for $m \times (m + k)$ we need $m(m + 2k)$ colors.
• It looks like for $m \times n$ where $n = jm, jm - 1, jm - 2, \cdots, \lfloor\frac{m + 2}{2}\rfloor$ and all $j$, we need $jm^2$ colors. These squares are marked green in the first table.

Does anyone know in general how many colors we need?

Background While trying to find all the fault-free tilings of the P-pentomino, I noticed that we can prove that the P-pentomino does not tile any $5 \times n$ rectangle for odd $n$, because such a rectangle does not fit $n$ $2 \times 2$ squares, and therefor can also not fit $n$ P-pentominoes. This made me wonder how close we can generally come to tiling a rectangle with an arbitrary given rectangle.

In general, rectangles pack and tile in complicated ways, so a direct analysis seems too hard. (For example, we can fit 4 $2 \times 3$ rectangles in a $5 \times 5$ rectangle in a pinwheel tiling construction.) Then I though of extending this technique to find how many rectangles will fit. But that only works if we need $mn$ colors for a $m \times n$ rectangle... and when I discovered this is not always the case, I wondered what is the general rule.

Solution 1:

I haven't quite fleshed out exactly how to use this, but I think the following idea should probably enough to at least prove that $mn$ colors suffice if and only if $m$ divides $n$: if two squares lie in the same row or the same column and are exactly $n$ squares apart on that row or column, then they must both have the same color. Note that since no intervening squares on that row or column can also have the same color, this means that every row and every column is basically colored periodically, with period $n$. So I think a coloring with $mn$ colors is fully specified by its values on an $n \times n$ square.

Proof: Assume that $m < n$ and suppose we have a coloring using $mn$ colors, and consider an $(m+1)$ by $(n+1)$ rectangle, as shown below:

Let's say the color in the top-left corner is purple. All the colors the leftmost $n$ columns of the top row will be called "shades of red", and all the colors in the top $m$ columns of the left column will be called "shades of blue", indicated by the light shading in the diagram. Purple is both a shade of red and a shade of blue.

When we move down to row $m+1$, the only colors available for the leftmost $n$ columns are shades of red. Furthermore, as $m < n$, the leftmost square in row $m+1$ cannot be purple, as this would cause a vertical rectangle with the same upper-left corner to have two purple squares. With only the shades of red available for that row, purple must appear somewhere else among the leftmost $n$ columns in row $m+1$.

On the other hand, in column $n+1$ we can only use shades of blue, among which there must be a purple square. If the circled square does not use the color purple, then the lower-right $(m \times n)$ rectangle has two purple squares. Hence the circled square must be purple. Thus two squares at distance $n$ along the same row must have the same color. Repeating the argument with rows and columns interchanged shows that two square at distance $n$ along a column have the same color.

Edit: I think I now see how this implies that if $mn$ colors suffice, then $m$ divides $n$. Suppose that $m$ does not divide $n$, but we have an $mn$-coloring. This $mn$-coloring is determined by its values on an $n \times n$ square. Let $C_i$ be the set of colors used on the $i$th row of this square. We see that $C_1, \ldots, C_m$ are pairwise disjoint (these rows all being contained within an $m \times n$ rectangle), and that $C_i = C_{m+i}$ for all $i < n-m$, since $C_{m+i}$ must be disjoint from $C_{i+1}, \ldots, C_{m+i-1}$, leaving only the $n$ colors in $C_i$ available. (Row $m+i$ and row $i$ might have these colors in a different order, but they will be the same set of colors.)

If $m$ divided $n$, then we'd get each of the sets $C_1, \ldots, C_m$ appearing exactly $n/m$ times on the square. However, since $m$ doesn't divide $n$, this repeating pattern of sets gets "cut off" at the bottom, and $C_1$ appears on some row $C_{n-i}$ for $i < m$. Now a horizontal rectangle starting at row $n-i$ will contain two rows colored using colors from $C_1$ once the square repeats, contradicting the hypothesis that this is a proper coloring.

Solution 2:

Wlog assume $m \le n$.

I don't have a clear idea for how to prove general lower bounds other than the obvious one ($mn$), so this is only a partial answer. My goal is to provide a constructive upper bound for the optimal colouring, and I note that it matches your first table.

I shall let $F(m, n)$ denote the number of colours in an optimal colouring for $m \times n$.

Lemma: $F(1, n) = n$

As stated in the question, and easily shown by the colouring $A_{i,j} = (i + j) \bmod n$.

Lemma: $F(am, an) \le a^2 F(m, n)$

Proof: we can take any tiling for $m \times n$ and divide each square into $a \times a$ smaller squares, colouring according to a bijection from (large square colour, subrow, subcolumn) to small square colour. Note that it's important that the subdivision be square, so that transposition doesn't cause boundary-crossing.

Corollary: $F(m, m) = m^2$, as also stated in the question.

Lemma: $F(m, n) \le F(m, n+1)$

Proof: any rectangle of size $m \times n$ is contained in a rectangle with the same upper-left corner which is one wider.

Lemma: If $\gcd(m, n) = 1$ then $F(m, n) \le m(n + (n \bmod m))$

Suppose $n = am + b$ with $0 \le b < m$ and $\gcd(m, b) = 1$. By Bézout's identity there are integers $x, y$ such that $mx + by = 1$. Let $k = (ay - 2x)m + 1 = (n+b)y - 1$. Let $W = m(n+b)$. We take a periodic tiling with $A_{i,j} = (ki+j) \bmod W$.

If we consider the two rectangles with top-left cell $(r_0, c_0)$ we require the $mn$ cells $(r_0 + \delta_r, c_0 + \delta_c)$, $0 \le \delta_r < m$, $0 \le \delta_c < n$ to have distinct colours; and the $mn$ cells $(r_0 + \delta_r, c_0 + \delta_c)$, $0 \le \delta_r < n$, $0 \le \delta_c < m$ to have distinct colours. $(k(r_0 + \delta_r) + (c_0 + \delta_c)) = (kr_0 + c_0) + (k\delta_r + \delta_c)$, so this boils down to

1. $k \delta_r + \delta_c \not\equiv 0 \pmod W$ when $0 \le \delta_r < m, 0 \le \delta_c < n$ unless $\delta_r = \delta_c = 0$.
2. $k \delta_r + \delta_c \not\equiv 0 \pmod W$ when $0 \le \delta_r < n, 0 \le \delta_c < m$ unless $\delta_r = \delta_c = 0$.

So the question is for what $\delta_r, \delta_c$ do we have $k \delta_r + \delta_c = uW$? Expand: $((n+b)y-1)\delta_r + \delta_c = um(n+b)$, or $(n+b)(y\delta_r-um) = \delta_r - \delta_c$. Since the absolute value of the RHS is at most $n-1$, this can only be true when $\delta_r = \delta_c$ and $y \delta_r = um$. But $\gcd(m, y) = 1$, so if $m \mid y \delta_r$ then $\delta_r = \delta_c = m$, putting the cell outside both rectangles.

Theorem: $F(m, n) \le m\min\left(n + (n \bmod m), m\left\lceil\frac{n}{m}\right\rceil\right)$

This is just putting together the various lemmata above, and coincides with your first table.

Solution 3:

Posting this as a new answer because it addresses a different subproblem:

Herman Tulleken conjectured that $m(m+2)$ colors are needed for an $m \times (m+1)$ rectangle. Taking $n=m+1$, we see that this is conjecturing $mn + m$ colors are needed, that is, $m$ more than the trivial lower bound of $mn$. I think I can extend my earlier technique to show that $m-1$ extra colors are needed, and I suspect that there's some slack here that can be squeezed out to force $m$ extra colors, but I'm not quite sure where it is.

Suppose to the contrary that we have a coloring with fewer than $m-1$ extra colors. Consider an $(m+2) \times (m+2)$ square in the lattice, and draw an "orange rectangle" around the top $m$ rows and $m+1$ columns, as shown in the diagram:

As before, let's call the colors on the top row of the orange rectangle shades of red. Call the color on the upper-right corner crimson; crimson is a shade of red. The rectangle must use $mn$ different colors; call the colors not used on the rectangle shades of green. The number of shades of green is exactly equal to the number of "extra colors", so there are fewer than $m-1$ shades of green. (We can also define shades of blue like we did before, and get some analogous results as shown in the diagram, but I don't think the shades of blue end up being relevant in the most streamlined presentation of this claim -- although they could be useful in pushing it further.)

Shifting the orange rectangle one row down shows that the bottom row of the new resulting rectangle must have all its colors either shades of red or shades of green. However, the yellow rectangle (a vertical rectangle dropped from the upper-left corner of our square) shows that the only shade of red available for the leftmost $m$ columns of this row is crimson. Thus, the $m$ leftmost colors must all be either crimson or shades of green. With fewer than $m-1$ shades of green available, this is impossible.