Squares Touching a Constant Number of Other Squares

Erich Friedman
Stetson University, DeLand, FL 32723
efriedma@stetson.edu

Abstract

We consider collections of squares with the property that each one touches exactly n others along part of an edge. We also generalize this idea to other shapes, higher dimensions, and a more inclusive definition of "touching".

Squares

We call a finite, connected, non-overlapping collection of unit squares in the plane to be n-touching if each square touches exactly n other squares along some portion of an edge. It is clear that n-touching collections exist for n = 0, 1, and 2 (see Figure 1). It is also clear that 0-touching and 1-touching collections are limited in size to 1 and 2 squares respectively, whereas 2-touching collections can contain any number of squares that is at least 3.

Figure 1. 0-touching, 1-touching, and 2-touching collections of squares

We exhibit a 3-touching collection of squares in Figure 2.

Figure 2. A 3-touching collection of 14 squares

Theorem: 3-touching collections containing k squares can only exist when k is even, and do exist for even k 14.

proof: That k must be even follows from the fact that the squares form the vertices of a 3-regular graph (where vertices are adjacent if the corresponding squares touch) and 3-regular graphs only exist with an even number of vertices. We know there are 3-touching collections with 14, 16, and 18 squares (see Figures 2, 3, and 4 respectively). We can insert an arbitrary number of columns of 6 squares (like the middle 6 squares in Figure 2) to extend these configurations into larger 3-touching collections of any larger even size.

Conjecture: The 3-touching collection in Figure 2 is the smallest possible.

Figure 3. A 3-touching collection of 16 squares

Figure 4. A 3-touching collection of 18 squares

Theorem: There are no 4-touching collections of squares.

proof: Consider the leftmost square S in a 4-touching collection. If there is a tie for the leftmost square, we let S be the highest of these. There is no way for S to touch 4 other squares without another square being left or directly above S, a contradiction.

We mention in passing that there exist 4-touching collections of dominoes, as seen in Figure 5.

Figure 5. A 4-touching collection of 24 dominoes

We can also relax the definition of "touching" to include collections of squares that can touch at a single point (we call such collections weakly n-touching). There are weakly 4-touching collections of squares. The smallest known consists of 50 squares and is shown in Figure 6.

Conjecture: The weakly 4-touching collection in Figure 6 is the smallest possible.

Figure 6. A weakly 4-touching collection of 50 squares

Cubes

In 3 dimensions, we require each cube in an n-touching collection to touch exactly n other cubes along some portion of a face. It is relatively easy to find a 5-touching collection of 6 cubes (see Figure 7). The cubes are in two layers: a shaded layer on bottom and a slanted non-shaded layer on top.

Figure 7. A 5-touching collection of 6 cubes

We exhibit a 6-touching collection of 14 cubes in Figure 8. Again the shaded squares are in a layer below the slanted unshaded squares. The middle square in each case is moved slightly perpendicular to the paper to prevent more than 6 adjacencies.

Figure 8. A 6-touching collection of 14 cubes

Conjecture: There exists a 7-touching collection of cubes.

Theorem: If there is an n-touching collection of hypercubes in dimension d, there is an (n+1)-touching collection of hypercubes in dimension (d+1). If there is a weakly n-touching collection of hypercubes in dimension d, there is a weakly (2n+1)-touching collection of hypercubes in dimension (d+1).

proof: By stacking two copies of the (possibily weakly) n-touching collection on top of each other in the (d+1)st dimension, we get such a collection with the required adjacencies.

This means there is a weakly 9-touching collection of cubes by imitating Figure 6. It also means 3-touching collections with k cubes exist for all even k 4.

Open Questions

1. Is there a simple proof that there are no 3-touching collections of fewer than 14 squares?

2. For what k do there exist 4-touching, 5-touching, and 6-touching collections of cubes? Does a 6-touching collection exist with fewer than 14 cubes?

3. Do there exist 7-touching collections of cubes? How about weakly 10-touching collections of cubes?

4. What are the corresponding results for other polyominoes and other shapes?

5. What are the corresponding results for hypercubes in dimensions d 4?