Given a positive integer $n$, an $n$-gun is a $2n$-mino that is formed by putting a $1 \times n$ grid and an $n \times 1$ grid side by side so that one of the corner unit squares of the first grid is next to one of the corner unit squares of the second grid. Find the minimum possible $k$ such that it is possible to color the infinite planar grid with $k$ colors such that any $n$-gun cannot cover two different squares with the same color. Itf0501
Problem
Source: IMOC 2021 C7
Tags: combinatorics, Tiling
mathematics2004
17.08.2021 17:16
Is there a figure of $n$-gun? I'm not sure I understand correctly. @below: Thanks. Is the answer $k=2n^2$? I found this problem extremely hard. Edit: All right. There is actually huge gap between my bound and construction.
CrazyInMath
24.08.2021 06:05
@above I can give you an example of a 2-gun, each X represent a square. XX X X @above Since I don't want the answer spoiled, I asked someone to view it for me. It turns out that your answer is incorrect. However, I don't know the correct one cuz I don't want to get the answer before I work on this problem. @above2 It's ltf0501 not lft0501. @above2 You typed it incorrectly in C3 as well.
mathematics2004
26.08.2021 20:07
The answer is $k=n(n+2)$. Construction: First consider the figure below, it is a $(n+1) \times (n+1)$ square cutting off a corner, we color $n(n+2)$ squares with different colors.
Now let's assume that there are exactly $(n+1)^2-2$ colors. Consider the lower-right corner (which was cut off), it is friendly with all squares in the shield, except the upper-left corner. Hence it must be the same color with the upper-left corner because we only have $(n+1)^2-2$ colors. In the same manner, the lower-left corner (which was cut off) is the same color with the upper-right corner. Note that the above analysis doesn't actually relies on specific squares; in other word, we can prove in the same way that $(x,y)$ is the same color with $(x+n,y+n)$, $(x-n,y+n)$, $(x+n,y-n)$, $(x-n,y-n)$, moreover, if we construct a $(2n+1) \times (2n+1)$ squares centered at $(x,y)$, these four unit squares are the only ones in the square which have the same color with $(x,y)$. (*) Therefore, if we are given the coloring of a shield (which uses all $(n+1)^2-2$ colors exactly once), using (*) repeatedly, we can determine the color of any unit squares on the plane. However, it is not the case. Consider the unit square $C$ marked in the above figure, which is to the lower-right of the upper-right square of the shield. Observe that no matter how to apply $( \pm n, \pm n)$ to $C$, we will not landed in the shield; that is to say, its color isn't properly defined, a contradiction!
In fact, if (*) is true, then exactly $2n^2$ colors are used, because simple number theory gives that there are $2n^2$ equivalence classes. I thought it is the optimal construction (in #2), which is indeed not true.
Thus, there must be at least $(n+1)^2-1=n(n+2)$ colors.
Number1048576
10.09.2023 22:19
We claim that the answer is $(n+1)^2 - 1$ for $n>1$ and $2$ for $n=1$. For $n=1$, the construction is just the chessboard colouring - it is easy to see that this is best possible. For $n>1$, see the construction in the attachment (which easily generalises to all $n$).
Consider an $n+1 \times n+1$ grid with the top left and top right corners removed. Note that this structure must have all different colours, as it can be checked that for any pair of squares in this structure there is an $n$-gun covering both squares. However, consider the top right corner of this grid. This cannot have the same colour as any of the colours in the structure apart from the bottom left corner, so either there are more than $(n+1)^2-2$ colours needed or this colour is the same as the colour in the bottom left corner. However, then the square one square above and to the right of the top left square cannot be any of the used colours, as is spelled out in the attachment. Therefore, we are done.
https://imageshack.com/i/pnvyVdblj https://imageshack.com/i/pmBnETSXj