7
$\begingroup$

There is a polygon whose edge lengths are all odd integers. Prove that this polygon's interior cannot be tiled by dominoes whose dimensions are $1\times 2$.

An example of such a polygon is a "mutilated chessboard," which is a chessboard with two opposite corners removed.

$\endgroup$
  • $\begingroup$ I think you need to add the rule, that the polygon is only allowed to have right angles. $\endgroup$ – The Dark Truth Jan 20 '16 at 7:50
  • $\begingroup$ @TheDarkTruth I'd say that's a fairly trivial assumption. $\endgroup$ – Tim Couwelier Jan 20 '16 at 10:15
  • 3
    $\begingroup$ I would say it's neither a rule nor assumption. For this question it's perfectly legal to have non right angles. But you will find out that no tiling is possible then fairly easy $\endgroup$ – Ivo Beckers Jan 20 '16 at 11:13
4
$\begingroup$

Let $P$ be the interior of some polygon in the coordinate plane with each side length odd, $\partial P$ its boundary (which we give the counter-clockwise orientation). We may assume that every edge in $\partial P$ is parallel to one of the coordinate axes, and that the vertices have integer coordinates.

Consider the function $U(x,y)=\frac{\pi i}{2}e^{\pi i (x+y)}$. Green's Theorem from calculus says that $$ \tag{$\star$} \int_P\frac{\partial U}{\partial x}dx\,dy=\int_{\partial P} U\,dy. $$ A direct computation shows that if $D$ is a domino with sides parallel to the coordinate axes, then $ \int_D \frac{\partial U}{\partial Y}dx\,dy = 0, $ so the left hand side of $(\star)$ is $0$ if $P$ can be tiled by dominos.

The right hand side of $(\star)$ vanishes on the horizontal edges, and on each vertical edge of odd length the value is $(-1)^{x+y}$, where $(x,y)$ are the coordinates of the final endpoint of that edge. Between any two consecutive vertical edges, there is a horizontal edge of odd length, so the $y$-coordinates of the ending points of two adjacent edges are of opposite parity, as are the $x$-coordinates. This means $(-1)^{x+y}$ has the same sign for each vertical edge, so the right hand side of $(\star)$ is non-zero.


In fact our argument shows the right hand side of $(\star)$ is $\pm\frac{E}{2}$, where $E$ is the number of edges of the polygon $P$. If we color the plane checkerboard fashion, one checks that $ \int_P \frac{\partial U}{\partial x}dx\,dy $ is twice the difference between the number of black squares and the number of white squares in $P$. The argument above then shows that if every side length of $P$ is odd, the difference between the number of black squares and the number of white squares in $P$ is always $\frac{E}{4}$. This gives a different proof of Theorem 3.1 in the paper linked by Ivo Beckers.

$\endgroup$
4
$\begingroup$

The proof can be found in this paper (Section 2).

The explanation is rather extensive so it would be hard to type it out here. But what they basically do is first color the polygon a chessboard pattern in such a way that at least one corner is black. Then they prove that in that case all corners are black. Then they prove that there are more black than white tiles making it impossible to tile the polygon.

$\endgroup$
  • $\begingroup$ That's surprisingly close to what I was getting at, nice! +1 $\endgroup$ – DrunkWolf Jan 20 '16 at 16:31
  • $\begingroup$ I didn't realize there were papers about this problem! There is a much quicker and more elementary proof of this theorem. $\endgroup$ – Mike Earnest Jan 21 '16 at 1:24
3
$\begingroup$

Tile the interior of this polygon with unit squares, then color these black and white in checkerboard fashion. We will prove that the number black squares differs from the number of white squares, which proves a domino tiling is impossible (since every domino covers one square of each color). To this end, let $B$ and $W$ be the number of black and white squares.

Let's place a positive ion on each edge of each internal black square, giving each black square a charge of +4. Similarly, place a negative ion on each edge of each white square.

enter image description here

The total electrical charge of the polygon's interior is equal to $4\times(B-W)$. However, the +/- ions on edges between neighboring squares cancel out. The only uncanceled charges are on the perimeter, so the net charge is also given by the black perimeter minus the white perimeter.

We now show the perimeter is white/black unbalanced. Imagine you walk around the perimeter, starting at a corner with, say, a black edge. As you walk along this side, you will alternate black and white, finishing with a black edge (since the side length is odd). You then make a 90${}^\circ$ or 270${}^\circ$ turn and start walking along the next side, again starting with black. Continuing this process, every side has one more black edge than white, so the perimeter is more black than white.

Putting this all together, we get that $$ B-W=\tfrac14(\text{black perimeter}-\text{white perimeter})\neq0 $$ so the number of white squares differs from that of black, so a tiling is impossible.

$\endgroup$
2
$\begingroup$

If the polygon is allowed to contain holes, then there are counter examples:

    XXX
    X X
    XXX

This polygon has only sides of length 3 (outer sides) and length 1 (sides of hole), and it is easy to tile it with four dominoes:

    AAB
    D B
    DCC
$\endgroup$
  • 3
    $\begingroup$ That's not a polygon though. $\endgroup$ – Deusovi Jan 20 '16 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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