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

Question

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.

Answer 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.

Answer 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.

Answer 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.

Answer 4

I discovered an idea that allows us to find the lower bound in more cases.

The basic idea is to assume we have an optimal coloring using $k$ or less colors for a certain rectangle $R$. We then transform this coloring into a new coloring that is the optimimal coloring for a different rectangle $R'$, using $k'$ colors. But if we already know (from Gregory's answer) that for $R'$ we actually need $\ell > k'$ colors, we have a contradiction, and therefor we know that we need more than $k$ colors for $R$.

I have not worked out exactly when we can use this technique. I will illustrate it with an example.

Suppose we could color $R(3, 5)$ with $k = 17$ or less colors, which we will denote with integer $0, \cdots, 16$. Now make a new coloring as follows:

Let $C_1(i, j)$ be the color of cell $(i, j)$, and let $C_2(i, j) = C_1((i + j)/2, (i - j)/2)$ for $i + j$ even, and $C_2(i, j) = C_2(i - 1, j) + k$ otherwise. The new coloring uses $2k$ colors.

It is much easier to see what is going on in images:

Here is an example coloring $C_1$ using 6 colors.

Here is the new coloring $C_2$ with just the colors for $i + j$ even shown:

And here is the $C_2$ with all colors, where I used a darker shade of a color $c$ to denote the color $c + k$.

Now we show that if $C_1$ is an optimal coloring for $R(3, 5)$, $C_2$ is an optimal coloring for $R(6, 5)$.

This can be done by showing that if we put $R(6, 5)$ somewhere on $C_2$, all the colors are different. If two colors are not different, then it implies there are two colors in $C_1$ that are the same in some $3 \times 5$ rectangle (we need to check a few cases for this, in this example it is easy to see). But this cannot be since $C_1$ is optimal for $R(3, 5)$. So if a coloring with 17 or less colors exist for $R(3, 5)$, we have a coloring using $34$ or less colors for $R(6, 5)$. But we already know that $R(6, 5)$ requires $35$ colors; therefor, the coloring $C_1$ cannot exist.

Edit: This example initially was for $R(2, 5)$, which turns out is a case where it does not in fact work. It does work for $R(3, 5)$ though, and in fact for any $R(k, 2k - 1)$. It seems to never work for anything else.

I also looked into other transformations. We can find a stretched coloring for any integer that can be written as the sum of two squares. (This is necessary so that the new coloring is stretched by the same amounts vertically and horizontally; otherwise both orientations of rectangles cannot work, or there is a coloring that using less colors that does work.)

Unfortunately, it seems none of the other scaling factors work, except for squares (which is not useful because we already have a lemma from Peter's answer for that case).

So the only scaling factor that gives us new cases is 2, and that only works for rectangles of the form $R(k, 2k - 1)$, so it does not give us a lot more. (We can also not use the trick twice; for example, we can find the lower bound for $R(4, 9)$ from $R(8, 9)$, but we cannot find the lower bound for $R(2, 9)$ from $R(4, 9)$.

However, we can find a way to get a rational scaling factor by first contracting and then stretching a coloring. The contraction is basically doing a stretch in reverse. For example, we can contract by a factor of 4, and then scale by a factor of 5, which gives us a combined factor of $5/4$. This seems to work in a lot more cases (and we can do factors $r/s$ for any integers $r$ and $s$ that is the sum of two squares).

Here is an example of how these operations affect colorings:

This is the original coloring (only colors that will end up in the final coloring are shown, the rest are left blank):

This is the coloring contracted by a factor of 4:

And this is the coloring after stretching it by a factor of 5:

This can be used, for example, to find a lower bound for $R(8, 11)$ from $R(10, 11)$.

A lot of work needs to be done to see exactly when this will work, and how many cases can be covered, and I also left out a lot of details here. Since the full details may be too much for an answer I will post on my blog once I have more information and update with a link.

---

So in general, to find a lower bound for some rectangle, we have to find a transformation that gives us a new coloring for some rectangle $R(m, m + 1)$. The next step would be to find when this is possible.

---

I also discovered a new way to see the upperbounds. So far, it looks like there are two ways to get an upperbound.

• A rectangle $R(m, n)$ fits into a rectangle of the form $R(m', m'k)$, which $m' \geq m$ and $m'k \geq n$, so the smallest $(m')^2k$ is an upperbound.
• The smallest L-shape that fits both orientation of the rectangle tiles the plane, and this shape uses $2mn - m^2$ colors. So this is another upperbound. Here is an example for $R(3, 4)$:

I have to recheck all my calculations, but it looks like when we put all this together, the best bound is either $mn - m^2$ if $m < \sqrt{2}n$, or $m^2\lceil n/m \rceil$ otherwise. I also need to check how these square with the bound found by Peter. (They should be the same, but the forms do not suggest it on first glance.)

Answer 5

I thought about this question a long time ago, when I was thinking about the coloring problem for polynomios on grids. Basically following the same reasoning in this post, I decided to try to tackle the problem specifically for rectangular polynomios (or equivalently, the $L$-shaped polynomios).

To be consistent with my own notation, I am calling the number of colors needed for an $a$ by $b$ rectangle $c_R(a,b)$, and also $c_R'(a,b)$ for the number of colors necessary if we only consider periodic colorings.

In this notation, @GregoryJ.Puleo's post says that if $a\leq b$, then $c_R(a,b)=ab$ if and only if $a$ divides $b$. @PeterTaylor's post says that $$c_R(a,ka+r)\leq c_R'(a,ka+r)\leq \min((k+1)a^2,(ka+2r)a)$$ if $0\leq r<a$ and $k\geq 1$ (note that the coloring considered there is indeed periodic). Then @GregoryJ.Puleo's second post says that $c_R(a,a+1)=a^2+2a$ if $a>1$, where as @HermanTulleken's last post says that $c_R(a,2a-1)=2a^2$ if $a>1$.

Here is what I can add: I proved the formula for $c_R(a,a+1), c_R(a,2a-1)$ in a slightly different way (but I guess not too different), and I also had the exact formula for $c_R'(a,ka+r)$. Determining $c_R(a,b)$ seems extremely difficult, and I still have no idea if determining $c_R'(a,b)$ helps at all.

The proof for $c_R(a,a+1)=a^2+2a$ and the one for $c_R(a,2a-1)=2a^2$ are actually really similar. The proof starts with picking a large clique of size $c_R(a,b)-1$, which we can use to show that the hypothetical coloring should be periodic and reach a contradiction. One observation is that with a more careful analysis of the clique number of the underlying graph, we see that the chromatic number and the clique number are not always the same.

For $a$-by-$(a+1)$ rectangles, consider an $(a+1)$ by $(a+1)$ grid without the two top corners. Any two squares can be covered by an $a$-by-$(a+1)$ rectangle at the same time, so we need at least $(a+1)^2-1=a^2+2a-1$ colors. If $a^2+2a-1$ suffices, then by rotating this figure by $90^{\circ}$, we see that the two corners on the same diagonal must have the same color. In other words, the square $(x,y)$ must have the same color with $(x\pm a, y\pm a)$. By flipping this figure upside-down, we see that $(x,y)$ must also have the same color as one of $(x,y-a), (x+1,y-a),\ldots, (x+a-1,y-a)$. However, those squares and $(x+a,y-a)$ can be covered by an $a$-by-$(a+1)$ rectangle at the same time, which is a contradiction.

Similarly, for $a$-by-$(2a-1)$ rectangles, we first find a large clique. In this case, we will consider the grid with $a$ rows and $(2a-1)$ columns, where the $a$-th column (so the middle column) has $(a-1)$ squares sticking out, say, pointing to the top. Clearly any two squares can be covered by such a rectangle, and so $c_R(a,2a-1)\geq a(2a-1)+(a-1)=2a^2-1$. Now if there is a coloring using this many colors, then we may move the top most square that sticks out to the bottom. This is still a clique, which shows that the top square must have the same color with the bottom square. By rotating this figure, we see that $(x,y)$ must have the same color with $(x\pm (2a-1), y)$ and $(x,y\pm (2a-1))$, showing that the coloring on each row is $(2a-1)$-periodic using precisely $2a-1$ different colors. The clique argument shows that any $a$ consecutive rows do not share any colors, and as long as $a>1$, it also shows that for the $(a+1)$-th row, there is one square that does not use any of the colors appearing in the previous $a$ rows. However, as the coloring is periodic on each row, this shows that the $(a+1)$-th row also does not share any color with the first $a$ rows, and so we need at least $(a+1)(2a-1)=2a^2+a-1>2a^2-1$ colors. This is a contradiction.

The proof that $c_R'(a,ka+r)=\min((k+1)a^2, ka+2r)$ is much more complicated. Roughly speaking, for any periodic coloring, we can first change it into its "normal form" (much like the Smith's normal form), and then it becomes analyzing whether it is possible for some $i\mod n$ to have small multiples $i\mod n,\, 2i\mod n,\,\ldots,\, ai\mod n$. This could be handled using properties of Farey sequence, and then the rest is to get our hands dirty and manipulate the inequalities.

These were done when I was trying to submit something to the science fair in high school. Taiwan International Science Fair in 2017 still maintains a copy of what I turned in, though it is in Chinese. I translated that into English for fun when applying to college. If you want to check the full proof for $c_R'(a,ka+r)=\min((k+1)a^2,ka+2r)$, check out Section 5 (I was not fluent in Latex so you would need to put up with something ugly).

Again, deciding $c_R(a,b)$ seems extremely difficult. I even had a really hard time determining $c_R(2,5)$. So far I have not discovered any pair of $(a,b)$ where $c_R(a,b)\neq c_R'(a,b)$.