# Overlaying two domino-like constructions such that all individual pairs of domino-like cells in the overlay have matching symbols

Imagine I have two $n$ x $m$ assemblies of $P = (n*m)$ unit square cells on the plane, $(c_{(a,1)}, ..., c_{(a,P)}) \in A$ and $(c_{(b,1)}, ..., c_{(b,P)}) \in B$, where every cell, $c_k$, in a particular assembly must have a distinct color/value. Here, $c_{(a,i)} \neq c_{(a,j)}$ & $c_{(b,i)} \neq c_{(b,j)}$ for all possible pairs of $i \neq j$, though it is permitted that $c_{(a,i)} = c_{(b,j)}$ (i.e. it is permitted that $A \cap B \geq 0$). For example, if $N = M = 2$, both $A$ and $B$ would be squares consisting of four cells with distinct colors/values, where some colors/values may overlap between $A$ and $B$.

I can join the cell arrays $A$ and $B$ by partially or fully overlaying the two assemblies under the constraint that the individual cells overlaying one-another in the two assemblies must all have the same colors/values. This is a bit akin to a game of dominoes where no piece can have two copies of the same value or symbol, and instead of juxtaposing the edges of the domino symbols that match, one lays the matching cell(s) of one domino on top of the other under the requirement that no non-matching cells are overlayed.

If the number of cells in the overlay region between $A$ and $B$ is $k$, for what values of $n$ and $m$ (defining the size and geometry of $A$ & $B$) does this uniquely define the geometry of our domino-like construction where $A$ overlays $B$? If this is too broad, what if we set $n = m$?

Update: As per Ben Barber's comment, we can rephrase this question as asking when two rectangles composed of $n$ x $m$ cells can overlap by exactly $k$ cells in a unique way. The colors/values here are meant as a means of breaking rotational and reflection symmetries on the individual rectangular cell arrays. Instead of using colors we could instead require that the $k$-cell overlap "...is unique down to the reflection and rotational symmetries of the individual rectangular cell arrays."

• As far as I can tell, the colours aren't doing anything here, and you're asking "for what values of $k$ can two $m\times n$ rectangles overlap in $k$ unit squares in precisely one way?" Is this an accurate restatement of your question? And are you allowing the rectangles to be rotated if $m \neq n$? – Ben Barber Oct 11 '12 at 17:38
• @Ben Barber The colors are there to break rotational and reflectional symmetries for ${n, m} \geq 2$. Otherwise, yes, I agree with your restatement. All rotations, reflections, etc. can be considered. – Perpetuum Oct 11 '12 at 21:59

EDIT: The original answer, included above the image, only considers cases E and F. A more complete answer follows the image.

The question can be simplified a little further from my earlier comment: for which $k$, $m$ and $n$ can a rectangle made up of $k$ squares fit into an $m \times n$ rectangle in only way? (Here "way" means the shape of the small rectangle and relative orientation of the small and big rectangles.)

Write factorisations of $k$ as $k=rs$, where $r \leq s$, and assume $m \leq n$. The condition is then that there is a unique factorisation of $k$ with $r \leq m$ and $s \leq n$ (so that the small rectangle fits inside the big rectangle), and if $m < n$ then $s > m$ (so that it can't be rotated if the big rectangle is not a square).

The image shows a not quite complete (it does not include, for instance, the case $k=mn$) list of the ways in which two identical rectangles can overlap. I'll give a couple of examples to show how it goes.

Cases A and B are the possibilities for squares. For $n\times n$ squares, the intersection can take size $k$ if and only if $k$ has a unique factorisation with $r, s \leq n$.

Now assume $m < n$. If we have $k=mx$ for some $x \leq m$ then C and either G or H provide distinct configurations with overlap $k$.

The rest of the restrictions on $k$, $m$ and $n$ can be worked out by a rather tedious case check: I don't expect there's a particularly nice phrasing of the conditions you'll obtain.

• @Ben Barber I'm not sure I understand your simplification? If we take two 3x3 squares squares, and we set k = 2, there should only be one way to overlay the two 3x3 squares (not accounting for rotational and reflection symmetries). However, a k = 2 square should be able to fit into a 3x3 square in many different ways. – Perpetuum Oct 12 '12 at 10:22
• I was ignoring translations of the smaller square, assuming that when we came to overlap the larger rectangles then the small rectangle would have to be in the corner of each of the larger rectangles. I now see that this is incorrect, as, for example, two $1 \times n$ rectangles can be overlapped to form a $k=1$ rectangle in many ways. So the condition I've given is necessary, but not sufficient, and a complete answer needs to consider all of the (finitely many) different ways that two rectangles can overlap. – Ben Barber Oct 12 '12 at 11:15
• I can't get the image to display in the answer. If anyone with the power to do so can sort it out for me (and possibly explain how to do it properly) it would be much appreciated. – Ben Barber Oct 12 '12 at 12:12