Densest way to place dominoes/duoplets in an infinite grid with some restrictions

120 Views Asked by At

Sorry in advance for being bad at explaining things.

Suppose you have a periodic pattern of dominoes and duoplets on an infinite grid that can't overlap. Each domino or duoplet has the ability to "block" one of the squares in its neighborhood (any square that's a king's move away, or equivalently any square that it shares a vertex with). If every square of an occupied square's neighborhood is either blocked or occupied, then that square is considered "crowded". A domino or duoplet cannot crowd one of its own squares. An example of crowding can be seen here, where "blocking" is represented with arrows and the square being crowded is marked with a bright red dot. Each square in the marked square's neighborhood either has an arrow pointing to it from another domino or is occupied by a domino. What is the maximum density infinite pattern of dominoes and duoplets where "crowding" is impossible?

Through trial and error the best pattern I was able to come up with was a pattern of $2\times2$ squares separated by a distance of one, where each square is cut into two dominoes. This pattern has a density of $\frac{4}{9}$ and it can be obtained by translating infinitely many copies of this 3 by 3 square.

Something else I discovered through trial and error to restrict the possible options was that any occupied square can have no more than 6 occupied neighbors. I won't prove it here for the sake of space but it's pretty easy to verify. Using the end of this paper on cellular automata I was able to use this restriction to get an upper bound of $\frac{4}{5}$ on the maximum density, and that's all I've been able to come up with. Any other lower or upper bounds would be appreciated.

Edit:

I managed to improve it to an upper bound of $\frac{2}{3}$. Basically, a necessary condition for crowding to be impossible is that each domino/duoplet has to be able to block a different square. This is because if a domino/duoplet is unable to block a square that isn't already blocked or occupied, that's basically the same thing as saying the squares in that domino/duoplet are crowded. That means there must be at least one unoccupied square for every domino/duoplet (one unoccupied square per two occupied squares), so the density can't be more than $\frac{2}{3}$.

Edit 2: problem variants + additional constraints

An interesting sub-problem is trying to find the densest pattern without crowding where there are a limited number of colors for the dominos/duoplets to be colored with, and no domino/duoplet can be the same color as a domino/duoplet in its neighborhood (this is pretty basic graph theory).

Another version of the problem you could consider is where individual squares are used instead of dominos/duoplets. This lowers the amount of possibilities but it also means the pattern can't be as dense, since each occupied square can block a square, as opposed to each pair of occupied squares.

Here's a summary of the best solutions so far to three different variants of this problem (colors are marked with letters).

Main Problem (3+ colors): density 1/2
. . A B . . A B
. . A C . . A C
. . B C . . B C
. . B A . . B A
. . C A . . C A
. . C B . . C B

2 colors: density 4/9
. A A . A A
. B B . B B
. . . . . .
. A A . A A
. B B . B B
. . . . . .

Single squares: density 1/3
. . A . . A 
. . B . . B 
. . A . . A
. . B . . B
1

There are 1 best solutions below

1
On

I'm not 100% sure I understand your problem setting, but how about this pattern?

. . A B . . G H
. . A B . . G H
. . C D . . J K
. . C D . . J K
. . E F . . L M
. . E F . . L M

Consider one of the squares of the C domino. It has $3$ spaces to its Northwest, West, Southwest. Since only dominoes A and E can block those spaces (C cannot block those spaces for the purpose of crowding a C-square), together they can only block $2$ of the $3$, meaning that C-square is not crowded.

This pattern obviously repeats with a density of $1/2$.

any occupied square can have no more than 6 occupied neighbors.

Can you elaborate on this? Clearly $7$ is not OK. But is $6$ actually OK? I haven't gone through all possibilities but so far I haven't come up with a case where an occupied square has $6$ occupied neighbors but cannot be crowded.