most recent 30 from http://mathoverflow.net 2013-05-24T13:23:52Z http://mathoverflow.net/feeds/question/109376 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109376/overlaying-two-domino-like-constructions-such-that-all-individual-pairs-of-domino Perpetuum 2012-10-11T12:34:58Z 2012-10-12T18:36:17Z

<p>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)}$ &amp; $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$.</p> <p>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.</p> <p>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$ &amp; $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$?</p> <p>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."</p>

http://mathoverflow.net/questions/109376/overlaying-two-domino-like-constructions-such-that-all-individual-pairs-of-domino/109445#109445 Ben Barber 2012-10-12T09:34:37Z 2012-10-12T18:36:17Z

<p>EDIT: The original answer, included above the image, only considers cases E and F. A more complete answer follows the image.</p> <p>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.)</p> <p>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 &lt; n$ then $s > m$ (so that it can't be rotated if the big rectangle is not a square).</p> <p><br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://www.freeimagehosting.net/newuploads/5pgcn.png" /></p> <p>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.</p> <p>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$.</p> <p>Now assume $m &lt; n$. If we have $k=mx$ for some $x \leq m$ then C and either G or H provide distinct configurations with overlap $k$.</p> <p>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. </p>