Polyominoes with double contact

Question

Here is a problem which arose from an earlier question. I'll change the terminology but not the question: A polyomino is a region with a connected interior made by joining one or more unit squares edge to edge. We will allow translating, reflecting and rotating polyominos but always with corners at integer points (and sides horizontal and vertical.)

It seems obvious that any two polyominoes, neither a single square, can be positioned so that their interiors are disjoint but they share at least two edges. Find a proof, preferably an elegant one, or perhaps a counter-example.

If we only insisted on being connected at corners this would not be true.

Here is a partial argument which is perhaps not that elegant and perhaps not that easy to finish. Let us say that one is red and the other blue. Every polyomino has a minimal bounding rectangle. I won't illustrate, but clearly if each has two consecutive filled squares on the boundary of the bounnding rectangle then those can be put in contact. So assume that the blue one does not have two consecutive colored squares on the boundary. This means that all four corners of the bounding rectangle are unoccupied. If the same is true of the red one then we can position them as shown to the left below (only a small part of each polyomino is indicated). White squares are definitely empty. The solid colored squares are definitely filled and include the rightmost blue square of the top or of that polyomino and the leftmost red square at the bottom of the red polyomino. The lightly colored squares with question marks might be empty or full. The green lines are not crossed by either polyomino in their current positions. The red polyomino can be moved down by one and there are either two edges of contact or else we can move it down another one and definitely have two edges. To the right is a similar situation where the red poyomino has a square of the bounding rectangle filled.

It remains to consider the case where the blue polyomino does not have two consecutive filled squares on the boundry of the bounding rectangle but the red one does, but not at any corner.

Answer 1

Here is a formalization of your argument. Let $A$ and $B$ be two poliominoes in question. Construct the following figure $K$ made of unit square: a square with integer coordinates $(x,y)$ is included in $K$ if and only if the translate of $B$ by the vector $(x,y)$ overlaps with $A$. ($K$ is essentially the Minkowski difference of $A$ and $B$ regarded as subsets of the integer lattice rather than figures with interior.)

Since $A$ and $B$ are connected. so is $K$. First consider the case when $K$ is not convex (i.e. not a rectangle) and find a concave corner of $K$. The cell outside $K$ near this corner is adjacent to at least 2 cells of $K$. This means there is a translate $B'$ of $B$ which does not overlap with $A$ but there are two coordinate directions (such as "up" and "left") such that if one moves $B'$ one step in any of these directions, the resulting figure overlaps with $A$. If you cannot move $B'$ up, then there is a cell of $B'$ right below a cell of $A$, so they share a boundary segment. Two such "forbidden" directions give us two common boundary segments.

Now consider the case when $K$ is a rectangle. Clearly the upper side of $K$ corresponds to the position where the bounding box (=minimal enclosing rectangle) of $B$ touches the bounding box of $A$ from above. Similarly for the other three sides of $K$. This means that an integer cell $(x,y)$ belongs to $K$ if and only if the bounding box of $B$ translated by $(x,y)$ overlaps with the bounding box of $A$. By the definition of $K$ this means the following: translates of $A$ and $B$ overlap if and only if their bounding boxes overlap.

This implies that $A$ and $B$ contain the corners of their bounding boxes. Indeed, if e.g. $A$ does not contain the upper right corner of its bounding box, we can translate $B$ so that the intersection of the two bounding boxes is just the cell at that corner, contrary to the above.

Once we know that $A$ and $B$ contain the corners of their bounding boxes, we can find boundary segments of length 2 near these corners and position our poliominoes so that they contact by these segments (this is already pointed out in the question).

Remark. If we disallow rotations and reflections. There is a counter-example. Let $A$ be the $3\times 6$ rectangle with the following 6 cells removed: one in the middle of each short side and two in the middle of each long side. (Sorry I don't know how to make a picture here.) Let $B$ be the same figure rotated 90 degrees. Then $A$ and $B$ cannot have two common edges without rotation.