Is there an arrangement of finitely many axes-parallel squares in the plane, of $k$ different colors, such that:

  • The squares of each color are pairwise-disjoint;
  • Each square overlaps at least $4$ squares of some other color (e.g. each red square overlaps $4$ green or $4$ blue squares; each blue square overlaps $4$ red or $4$ green squares; etc.)?

For $k=2$ colors, Barry Cipra proved that the answer is no. Can his argument (or another one) be extended to $k>2$?


The beautiful constructions by Manfred Weis show that, for $k\geq 4$, there exists an arrangement in which each square overlaps at least 4 other squares that may be of different colors (e.g. a red square may overlap two green and two blue squares). But my intention (which was probably not clear enough) was that each square should overlap at least 4 other squares of the same color (e.g. a red square should overlap 4 green squares, or 4 blue squares).

  • 1
    $\begingroup$ as I have demonstrated, that a solution exists for k>3, the question boils down to as to whether a solution with k=3 is possible. $\endgroup$ May 25 '20 at 14:24
  • $\begingroup$ I assume you are asking whether there is a $k$ for which such arrangement exists. If yes, this is equivalent to the following uncolored version: Does there exist an arrangement of finitely many squares where each square overlaps with four pairwise disjoint squares? $\endgroup$ May 31 '20 at 22:41

There is such arrangement, for some large $k$. In the text below, I did not try to optimize $k$.

1. First, we reduce the problem to the following uncolored version:

There is an arrangement $\mathcal A$ of finitely many squares such that each $a\in\mathcal A$ overlaps with four pairwise disjoint squares in $\mathcal A$.

Indeed, given such arangement $\mathcal A$, for each square $a\in \mathcal A$ we introduce a color $C_a$, find four pairwise disjoint squares overlapping with $a$, and put into an arrangement $\mathcal B$ their copies having color $C_a$. Then $\mathcal B$ satisfies the requirements: each square in it is a copy of some $a\in\mathcal A$, and hence the color $C_a$ fits for it.

2. Now we construct a required $\mathcal A$. We introduce the colors to distinguish the squares; those colors have a few in common with the colors in the initial problem.

On each step of the process, we say that a square is good if it satisfies the required property, and bad otherwise. The degree of a square is the maximal number of its pairwise disjoint overlappers.

Start with a $10\times 10$ grid of just-non-overlapping red squares, and put into any interior vertex of the grid a blue square. All squares are good, except for the boundary red ones (see left figure).

A convenend property is that for any point $x$ in the upper-eft quarter of the figure (within the grid), we may take a large square with $x$ as an either upper-left, or upper-right, or lower-left corner; this square will be automatically good, as it overlaps with many red squares. We attach such squares (not shown in the figure) to each side of the grid. Now, still boundary red squares are bad, but each of them already has degree 3. [In fact, this is not needed, so it is made just for visibility reasons.]

Now take any two adjacent boundary red squares in the upper-left quarter; the right figure shows them magnified. We do the following chain of operations:

Two steps of the construction

$\bullet$ add a green square; to two its dark-green vertices attach large non-overlapping squares, as described above. The red squares become good, the green one has degree 3 (due to the upper red square and two large oens);

$\bullet$ add a magenta square, and attach two large squares to its dark-magenta vertices --- its degree is 3 (due to the green square and two large ones), the green one becomes good;

$\bullet$ add a yellow square, attach three large squares. All squares in this small area are good (the yellow --- due to the upper red square and three large ones).

Applying such operations to every pair of adjacent boundary red squares (or even splitting them in pairs), we reach the goal.

(The construction is superfluous, but, as I told, I did not try to optimize.)

  • $\begingroup$ I do not understand the reduction: "for each square $a\in A$ we introduce a color $C_a$, find four pairwise disjoint squares overlapping with $a$, and put into an arrangement $B$ their copies having color $C_a$". But do you copy the square $a$ itself to $B$? If not, then how will $B$ satisfy the requirements? $\endgroup$ Jun 2 '20 at 6:26
  • 1
    $\begingroup$ I do not copy $a$ at this stage. But, when $a$ participates in some disjoint 4-tuple for some other square, a copy of $a$ appears in $\mathbb B$. And for any such copy, color $C_a$ serves. $\endgroup$ Jun 2 '20 at 6:37
  • $\begingroup$ This is the construction in the upper-left quarter; for the other quarters you will need a slightly different construction, right? $\endgroup$ Jun 2 '20 at 7:25
  • $\begingroup$ Sure; just reflect this construction accordingly. $\endgroup$ Jun 2 '20 at 9:17
  • $\begingroup$ Beautiful construction. Thanks! $\endgroup$ Jun 3 '20 at 10:19

A solution for $k=4$ colors can be constructed from the arrangements of squares that square the square in the followig way: if an square has a corner in common with the bounding square and is neighbor to only 3 inner squares, then split the neighboring square whose corners are strictly inside the bounding square into four equal parts.

That is illustrated with A. J. W. Duijvestijn's smallest squared square.
the squares with sidelengths 33 and 27 are only neighbors to 3 other squares; splitting inner squares with sidelengths 4 and 8 makes all squares neighbors of at least 4 other squares; increasing the size of each square by $\epsilon$ while preserving the location of their centers makes each square overlap with at least four others. If we take as vertices of a planar graph the squares and as edges pairs of overlapping squares, then a vertex coloring of that graph yields a coloring of the squares such that no overlapping pair has the same color.

enter image description here

one of the possible 4-colorings of the squares that remains valid after a slight center-preserving enlarging of the squares

enter image description here

The smallest satisfying arrangement of squares from which a satisfying example can be obtain by slightly enlarging the squares of the arrangment:

enter image description here

  • $\begingroup$ Consider the "42" at the bottom-right. It overlaps 24, 18, 16, 37, but these cannot be of the same color - they must be of at least two different colors. So it does not overlap 4 squares of the same color. $\endgroup$ May 25 '20 at 14:49

It is possible for infinitely many squares:
enter image description here

tile the plane with a shape made up of 5 squares with centers at $(-1,0),(0,0),(+1,0),(0,-1),(0,+1)$ each of a different color and sidelengths equal to e.g. $0.6$.

The centers of squares of the same color are the corners of a rotated square grid of knight moves.

The depicted arrangement is also utilized in the printing business, however with different colors.

  • $\begingroup$ Looks interesting, but is this an arrangement of finitely many squares? $\endgroup$ May 24 '20 at 16:21
  • $\begingroup$ @ErelSegal-Halevi sorry, I missed the restriction to finitely many squares; Iwilledit my answer accordingly. $\endgroup$ May 24 '20 at 16:34
  • $\begingroup$ Also, the squares in the picture do not overlap $\endgroup$ May 24 '20 at 16:40
  • 2
    $\begingroup$ @ErelSegal-Halevi yes, but that is easily fixed by increasing the sidelengths of the squares; I just found is easier for illustrating the pattern. $\endgroup$ May 24 '20 at 16:46

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.