18
$\begingroup$

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.

enter image description here

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ Nice question! I suspect that you could push the $m \times m$ case a little further -- playing around with it a little bit, I think that $mn$ colors suffice whenever $m$ divides $n$. I would hazard a guess that $mn$ colors suffice if and only if $m$ divides $n$ (for $m \leq n$), but the $2 \times 7$ entry in your table refutes that, if it's correct. $\endgroup$ – Gregory J. Puleo Dec 11 '18 at 4:10
  • $\begingroup$ I think you may be right that $mn$ is enough when $m$ divides $n$. But I double checked $2 \times 7$, and also added another counter example ($10 \times 3$), so the converse is not true. In fact I think for fixed $n$, $mn$ is always enough for $m > k$ for some $k$. (See my edit.) $\endgroup$ – Herman Tulleken Dec 11 '18 at 4:47
  • 1
    $\begingroup$ @GregoryJ.Puleo Looks like you may be right after all; I updated the question with more data. I had a mistake in my construction, so some of the initial table entries were incorrect. $\endgroup$ – Herman Tulleken Dec 12 '18 at 16:54
  • 2
    $\begingroup$ The obvious generalisation of @GregoryJ.Puleo's observation would be that $$f(m,n) = \gcd(m,n)^2 f\left(\frac{m}{\gcd(m,n)}, \frac{n}{\gcd(m,n)}\right)$$I think it's quite easy to prove $\le$; I will try to prove $\ge$ when I'm properly awake. $\endgroup$ – Peter Taylor Dec 15 '18 at 0:30
6
$\begingroup$

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:

Colored rectangle

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.

$\endgroup$
  • $\begingroup$ This is a nice strategy. I tried to see if it can be modified to also deal with other cases, but so far have not found a way. The next easiest case may be $m \times (m + 1)$, which looks like it may need $m(m + 2)$ colors (I updated my question with some more information.) Unlike the $m, mk$ case, the pattern does not repeat with a rectanglular pattern, but a different parallelogram. $\endgroup$ – Herman Tulleken Dec 14 '18 at 20:39
  • $\begingroup$ @HermanTulleken your proposed bound is $m$ more than the trivial lower bound of $mn$. I can't quite get that, but I think I can extend this method to prove fairly easily that at least $m-1$ more colors than the bound are required -- and with some cleverness maybe it could be pushed to force $m$ colors instead. I'll write it up as an answer this morning. $\endgroup$ – Gregory J. Puleo Dec 20 '18 at 14:57
3
+50
$\begingroup$

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:

coloring of rectangle

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.

$\endgroup$
  • 1
    $\begingroup$ $m$ greens are required. By sliding the yellow rectangle right you can show that the only one of those $m$ cells which can be crimson is the left-most. So if there are fewer than $mn+m$ colours, every cell must be the same colour as the ones at offsets $(\pm m,\pm m)$. Therefore the tiling is periodic: every $m$th row consists of the $m+1$ reds and $m-1$ greens shifted by $m$ from the row $m$ before. But none of the rows in between can contain any red or green, so you end up requiring $m(2m)=2m^2$ colours. If $m > 1$ this contradicts the assumption that there were only $m(m+1)+m-1=m^2+2m-1$. $\endgroup$ – Peter Taylor Dec 22 '18 at 12:01
  • $\begingroup$ I was really conflicted about how to award the bounty, for I feel the answers of you and Peter Taylor together is how to approach the complete question; using your technique (extended even further for the full case) to prove the upper bounds of his answer is really also lower bounds. In the end I chose this as it provides the core seed I think of "seeing" why we need the number of colors that we need. $\endgroup$ – Herman Tulleken Dec 22 '18 at 17:28
  • 1
    $\begingroup$ @HermanTulleken, you really asked about lower bounds so I agree that Gregory's answers deserve the bounty. I'm trying to extend this to the general case, but at the moment it seems that at best it will require complicated bookkeeping. Without wishing to count chickens before they're hatched, if we manage it then it might be worth writing a paper and trying to get it published. $\endgroup$ – Peter Taylor Dec 22 '18 at 17:59
  • 1
    $\begingroup$ @PeterTaylor if we can get matching upper and lower bounds then I'd certainly be interested in seeing if we can publish it. $\endgroup$ – Gregory J. Puleo Dec 27 '18 at 21:44
  • 1
    $\begingroup$ also @HermanTulleken $\endgroup$ – Gregory J. Puleo Dec 27 '18 at 21:44
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Revised to correct. $\endgroup$ – Peter Taylor Dec 31 '18 at 0:32
0
$\begingroup$

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.

enter image description here

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

enter image description here

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

enter image description here

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):

enter image description here

This is the coloring contracted by a factor of 4:

enter image description here

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

enter image description here

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)$:

enter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.