We claim the best we can do is two, achievable by putting them all end-to-end in either of the two obvious ways. We prove by induction on the number of dominoes that there will always be at least two sides of even length. For $ n=1$, the result is obvious. Now assume it for $ n=k-1$. Consider any polygon created by $ k$ of these dominoes; we claim it has at least two even-length sides. This is because if we remove a domino, the resulting figure will have at least two, and to "get rid" of an even-length side, we would have to position the domino either so that it extended the side or interrupted the middle of the side. In either case, the "exposed" 2-unit side would give another even face - unless one of the existing dominoes covers or adjoins part of it. However, then we would in turn need another domino to cover that domino's exposed side, and in turn another, etc. Hence either the dominoes form a loop, contradicting the definition of a polygon, or there are infinitely many dominoes, which is of course impossible. We therefore have a contradiction, and the minimum is 2, as desired.

This is probably clearer: Every angle of the polygon is $ 90$ or $ 270$ and the sum of its angles is $ 0 \pmod{180}$. This means the polygon has an even number of sides. It also must have even perimeter; suppose we start at an arbitrary vertex and travel along the whole perimeter. If we travelled $ u$ units up, $ d$ units down, $ l$ units left and $ r$ units right, then $ u = d$, $ l = r$, and the perimeter is $ u + d + l + r = 2u + 2l$ which is even. Then the polygon having one side of even length means it has an odd number of sides of odd length and an odd perimeter, which is a contradiction. So at least two sides of even length are needed.

MellowMelon, that argument doesn't rule out the possibility that all sides are odd, does it?

You're right; somehow I thought that was the easier case. First solution still seems a bit imprecise to me though. I think you can show a polygon made of unit squares on a checkboard, all side lengths odd, has a different number of black and white squares. Haven't managed to prove it though.

Hmm, let's clear this up a bit. The only hole I could see here is if the loop's interior was actually stacked with dominoes, but by the inductive step, I don't actually see this is a problem, because if this were the case, then the side of even length we're considering wouldn't have even length in the first place. As for your colouring approach - which is pretty ingenious - I couldn't find a proof in the five minutes I thought about it, but I just realized something: does the problem stipulate that the vertices of the dominoes must fall on lattice points? Even without that restriction, I don't believe it's possible to get less than two.

fwolth: the vertices must be on lattice points or else we wouldn't get integral side lengths. MellowMelon, I agree (from empirical evidence) that if a simply-connected polygonal region made of dominoes has all odd sides then it has different numbers of black and white squares, but it's not true for non-simply-connected regions (look at a $ 3 \times 3$ square with its center square removed, for example). On the other hand, I've only been able to find such regions using an even number of dominoes (actually, a number divisible by 4, I think), and I imagine that non-simply-connected regions probably do not qualify as "polygons," but it does mean that any proof has to exclude this case in some fairly obvious way. fwolth's proof attempted to do so, but I admit I don't find it incredibly convincing as written. (Basically, the argument that there are only two cases, the one in which induction works and the one in which it's not simply connected, seems awfully much like intuition-driven handwaving.)

Yes, there would be nonintegral sidelengths - however, there would also still have to exist integral ones; and in particular, at least two even-sided ones.

JBL: Agreed that regions with stuff missing in the middle causes bad things to happen. Here's the idea I have been trying to use to tackle this: consider the smallest rectangle of unit squares enclosing the entire polygon. You want to use an algorithm to modify the polygon and "fill" this rectangle, all while keeping careful count of the number of black squares and white squares added. The main thing you can do in this algorithm is something to this effect: XXXX Xabc Xdef Xghi Given two odd sides $ a \times b$ joined by a 270 degree angle, you can extend them and fill the rectangle they leave out, so you would add all of squares abcdefghi in. This would do two things though: create even sidelengths and change the difference of the black and white squares. One option to fix both is to leave out square i, but I think it's too hard to get the algorithm to terminate, and to fill the rectangle you have to make even sides eventually. I posted a conjecture (mostly empirical) in my blog which shows that the number of 270 degree angles (aka the number of sidelengths) is critical, so having the algorithm target those would seem to be on the right track. The main reason (among a few) I can't carry this through to completion is because I cannot figure out how to specify what to do in situations like this. XXXXX.X XX....X XX....X XX,XXXX XX,XXXX XX,XXXX XXXXXXX Most of the rectangles that we might "fill in" as described above are blocked somehow. I don't know how to identify the spaces labeled with commas in the general case, as filling these is the obvious first step here.

MellowMelon wrote: I think you can show a polygon made of unit squares on a checkboard, all side lengths odd, has a different number of black and white squares. Haven't managed to prove it though. Just for the sake of completeness, since I believe the blog post is no longer there... Suppose the polygon $P$ has all odd sides and let $V$ be the set of its vertices. Color the unit lattice in a chessboard fashion, and for every point $p\in\mathbb{Z}^2$ define $f(p)$ to be the difference between the number of black and white squares (in the chessboard coloring) incident to $p$. Then $f(p)=0$ for all $p\in\mathbb{Z}^2\setminus V$, whence \[4B-4W=\sum_{p\in\mathbb{Z}^2}f(p)=\sum_{p\in V}f(p).\]But $P$ has all odd sides, so considering 90 and 270 degree turns separately, we see that $f(p)\in\{-1,1\}$ is constant for all $p\in V$. In particular, $B\ne W$. Alternatively, we can use Green's theorem to get something equivalent---in the notation of the article, $L=-e^{i\pi(x+y)}$ and $M=e^{i\pi(x+y)}$ works. Intuitively, $e^{i\pi t}$ "extends" $(-1)^t$ to non-integer $t$. See pythag011's Mock USAMO Problem 1 here for another application of the above ideas. To prove the weaker statement that no domino tiling exists, height functions suffice. (For any cycle enclosing a region tiled by dominoes, the sum of the height function over the points/vertices of the cycle must vanish, but if we take the cycle to be the perimeter of $P$, the odd-side condition makes this impossible. Conway and Lagarias give a reasonably detailed proof of this in Section 2, Theorem 2.1.)