Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

textareatextarea

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.

alt text

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.

share|improve this question
1  
Sorry for the stupid remark but I have also made the same mistake many times - plural is polyominoes. –  domotorp Jan 2 '13 at 14:16
1  
Also, I think on the left side above I think there should be two more lightly colored squares, second right from solid blue and second left from solid red. Of course your argument remains correct. –  domotorp Jan 2 '13 at 14:22
    
This question is equivalent to this: mathoverflow.net/questions/117841/… –  domotorp Jan 2 '13 at 17:47
    
Thanks for all the comments. I have incorporated your suggestions. I swapped leftmost and rightmost to save the illustration and make the second picture work. –  Aaron Meyerowitz Jan 3 '13 at 6:38
2  
If you allow infinite polyominoes, you could have a 2x2 square and an infinite two sided comb as a counterexample. If you hope to prove the result true, the finiteness will be crucial. I suggest a proof by weak induction on the size of one of the pieces. Gerhard "Ask Me About Weak Thinking" Paseman, 2013.01.03 –  Gerhard Paseman Jan 3 '13 at 8:55

1 Answer 1

up vote 9 down vote accepted

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.

alt text

share|improve this answer
    
I would change the word "position" near the end of the proof sketch to "position (including an appropriate rotation and or reflection)". This makes it clear precisely when something other than a translation is needed. I do like the solution. Gerhard "Almost Ready For Hexagonal Polyominoes" Paseman, 2013.01.03 –  Gerhard Paseman Jan 3 '13 at 22:17
    
It might be worth generalizing to d dimensions. If the suitable generalization of K is analyzed, one can readily get somewhere from two up to d faces, depending on the nature of the concavity. Perhaps the contact number of a configuration of polyominoes appears in the literature? Gerhard "Place Oneself Outside The Boxes" Paseman, 2013.01.03 –  Gerhard Paseman Jan 3 '13 at 22:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.