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.
We exhibit a 3-touching collection of squares in Figure 2.
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.
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.
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.
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.
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.
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?