You are currently browsing the daily archive for July 3, 2008.

Okay, folks, time for another Problem of the Week! I hope it generates more response than last week’s problem:

Let C be a simple closed curve in the plane, and let P be any point strictly in the region interior to C. Show there are two points on C whose midpoint is P.

Please submit solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, July 9, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response.

Dang! No solutions were received for last week’s problem; a couple of people made a decent start but didn’t send in a complete solution before time was up. So, alas, we’ll just have to post our own solution this time!

Of course we welcome comments as always. I actually found this problem in an old American Mathematical Monthly (February 1998, problem 10641, proposed by Jerrold R. Griggs), where the problem editors certainly give much more than a week’s worth of time to submit solutions! But this one I managed to solve it after mulling it over for a couple of days, so I thought it would be quite manageable (although not quite trivial; more on this below). Plus, I thought it was a cute little problem. Oh well.

Solution by Todd and Vishal: An m \times n rectangle is tileable by triominoes (“L-shaped” unions of 3 of the 4 unit squares in a 2 \times 2 rectangle) if and only if three conditions hold:

  1. Both m, n > 1;
  2. 3|mn;
  3. Whenever mn is odd, we also have m, n > 3.

Proof: (Necessity) The condition m, n > 1 is clear since each tile has two rows and two columns, and the condition 3|mn is clear since the rectangle has mn squares and each tile consists of 3 squares.

Lemma 1: For n > 2, if the 3 \times n rectangle is tileable, then the 3 \times (n-2) rectangle is tileable.

Proof: Given a tiling of the 3 \times n rectangle, consider the tiles placed along an edge of length 3. By inspection, the tile containing the middle square along that edge must contain one of the corners along that edge, and must not contain the non-corner square adjacent to the middle square. So there is only one way to cover that middle and corner with a tile. This in turn fixes the placement of the tile containing the other corner along that edge, and the two tiles together form a 3 \times 2 rectangle. Removing that 3 \times 2 rectangle, we see the rest of the triominoes tile the 3 \times (n-2) rectangle that remains. \Box.

This lemma shows that no tiling exists for a 3 \times n rectangle if n is odd; otherwise we could tile the 3 \times 1 rectangle. So the third condition is also necessary.

Now we prove sufficiency. First consider the case where mn is even. One of m, n is even (say m), and also either 3|n or 3|m. Say 3|n, so that m = 2i and n = 3j; then it is clear that we can tile the m \times n rectangle with ij (2 \times 3) rectangles, each tiled by two triominoes. If on the other hand (2|m and) 3|m, say m = 6i, then either n is even (and a tiling exists by the case we just considered, switching the roles of m and n); or, n is odd. In that case, n = 3 + 2j; we have already proven that the 6i \times 3 rectangle can be tiled, and also that the 6i \times 2j rectangle can be tiled, and then we just put these two tilings together to tile the m \times n rectangle.

Now consider the case where mn is odd. Here we assume that both m, n > 3 and 3|mn. So both m, n are at least 5, and if (say) 3|m, then m is at least 9.

Lemma 2: The 9 \times 5 rectangle can be tiled by triominoes.

Proof:

Corollary: Any (3 \cdot (3 + 2i)) \times (5 + 2j) rectangle can be tiled, if i, j are nonnegative integers. (This completes the proof of sufficiency.)

Proof: It suffices to tile a (3 \cdot (3 + 2i)) \times 5 rectangle and a (3 \cdot (3 + 2i)) \times 2j rectangle. The second case we’ve already treated. For the first case, simply put together tilings of the 9 \times 5 rectangle and the 6i \times 5 rectangle (which we have already treated). We are done. \Box

Remarks: The case where mn is even is relatively “easy”; I expect most people thinking about this problem got that far in the analysis. The case where mn is odd is harder; one has to observe the crucial lemma 2 or something like it. In my own case, I at first thought maybe there weren’t any solutions in the odd case (and I think the people who submitted a partial solution may have thought the same), first because it’s not at all obvious, and second because lemma 1 already rules out the 3 \times \mbox{odd} case (so that one may be tempted to extrapolate from there).

Here, something very typical happened: after failing to find an obvious proof of impossibility for the odd case, I tried to get at this alleged impossibility by pushing in the opposite direction: seeking a way to construct such a tiling and feeling for obstructions. [It's that funny kind of dialectic one sometimes experiences in mathematical problem-solving, very reminiscent of Lakatos's Proofs and Refutations.] It wasn’t long before I bumped up against a 9 \times 7 tiling after all, and at that point thought a 9 \times 5 should also be possible, which I then got after a few minutes. Then it was just a matter of mopping up.

For tiling problems in general, there’s another approach which one could try to establish the impossibility of tiling a region, if one is good at combinatorial group theory. The idea is that a tile like a triomino defines a word (up to conjugacy) in the free group on two generators x, y: you just read off the word by following along the perimeter. For example, for a triomino in the “L” position (remove the northeast corner in a 2 \times 2 square), if you start at the southwest corner and move counterclockwise around the triomino, you read off the directions x x y x^{-1} y x^{-1} y^{-1} y^{-1} where x = “one unit right” and y = “one unit up”. (Starting at other positions, one gets a conjugate of that word.) Similarly one gets words for the triominoes in the other three positions, and the relator subgroup for our tiling problem is the smallest normal subgroup containing these words.

The observation is this: if a planar region interior to a simple closed rectangular curve is tileable, then the curve describes a word belonging to the relator subgroup. For example, the word for a 2 \times 3 rectangle might be w = y^3 x^{-2} y^{-3} x^2, and from one of the tilings of the rectangle we can read off

y^{-1} w y = (y^2 x^{-2} y^{-1} x y^{-1} x)(x^{-1} y x^{-1} y^{-2} x^2 y)

where the words in parentheses are (conjugate to) words for triominoes. By the same token, if the word corresponding to a curve is not in the relator subgroup (is not the identity in the quotient group defined by the presentation), then the region is not tileable. For example, one can imagine a proof that certain tilings are impossible, by exhibiting a suitable representation of the group being presented.

Our other blog

Visitors to this blog

Blog Stats

  • 257,899 hits

Wikio Ranking

Wikio - Top Blogs - Sciences

Current Online Readers

Archives

July 2008
M T W T F S S
« Jun   Aug »
 123456
78910111213
14151617181920
21222324252627
28293031  
Follow

Get every new post delivered to your Inbox.

Join 68 other followers