Drawing Blanks

Premature Optimization is a Prerequisite for Success

Cutting things into triangles; Monsky’s Theorem.

with one comment

First, a couple of puzzles, almost but not entirely unrelated to the subject of this post, just to warm you up.

Cut an obtuse triangle into acute triangles. *Prove that 7 is the smallest number of pieces.

Cut a square into acute triangles. *Prove that 8 is the smallest number of pieces.

And now, the real problem.

A square can not be cut into an odd number of equal area triangles. (Note that this problem deals with area, unlike the warm-up puzzles that I offered).

I decided to write about this problem because I see it pop up more and more often in internet forums. It looks like people don’t lose hope that somebody may discover an elementary solution. Well I am very skeptical about this. So I want to offer a sketch of the proof that was published in 1970 by Monsky. The proof is not elementary, but it is beautiful. To me, it is like a game of chess (I don’t play chess) – I would never be able to come up with anything like this, I can not learn from this, but can appreciate all the strategy and tactics employed.

Let us begin with defining the 2-adic norm on rational numbers. Don’t be scared, I’m not going to lecture you on p-adic numbers, I am not well familiar with them myself. But the 2-adic norm is easy. It measures how odd the number is. Let x is rational. Then it can be written as

x = (2^t)(p/q) where both p and q are odd.

We define the 2-adic norm of x as

|x|=(1/2)^t (or zero if x=0)

I’m going to use |x| for 2-adic norm of x in this post. (In order to get more comfortable with this definition you may want to read this http://mathworld.wolfram.com/p-adicNumber.html)

Anyway, what Monsky suggests to do next, is to extend this norm to all real numbers. Although this construction must be well-known and described in all textbooks, it is by no means elementary. I have no idea how the 2-adic norm can be extended to R. And I feel this cannot be critical to solving our problem. Being restricted to just rational points on the plane should not affect our considerations regarding the areas.

What we do next is divide the plane into 3 sets that satisfy

S1: |x|<1 and |y|<1        (RED points)

S2: |x|>=1 and |x|>|y|   (BLUE points)

S3: |y|>=1 and |y|>|x|   (GREEN points)

Let C(x) be the color of the point x. Next, we are going to need a few lemmas. (I’m only sketching, not giving proofs).

Lemma 1 (the red property):

If r is a red point, then for any point x, C(x) = C(x+r).

Lemma 2 (the straight line property):

Any straight line has points of at most 2 colors.

(The proof is based on the red property: if the line contains 3 points of different colors, one of them is red (r), we can translate it by -r so that it passes through 0. Then consider the ratio of the two other points and come to a contradiction).

Now imagine we have some dissection of the square (0, 0), (0, 1), (1, 0), (1, 1) into triangles. Let’s call edges of the dissection “purple” if they connect red vertices to blue vertices.

Lemma 3 (the purple property)

The boundary of the square contains an odd number of purple segments.

(Notice that purple segments can only belong to the side (0,0)-(1,0) and the end points of this side are of different colors)

Lemma 4

If a triangle has vertices of at most 2 colors, then it has an even number of purple edges. This is trivial.

And now, the key argument

We can determine if the number of purple segments on the boundary is even or odd by summing over all the
purple edges of all triangles, because any internal (non-boundary) edge will be counted twice. So by the purple property, the total number of purple edges is odd. It immediately follows (by Lemma 4) that

There must be a triangle with vertices of each color.

And it is easy to prove that the 2-adic norm of the area of such triangle must be greater than 1.

So if we have n triangles of the equal area 1/n then n can’t be odd.

Advertisements

Written by bbzippo

06/20/2010 at 9:55 pm

Posted in math

One Response

Subscribe to comments with RSS.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: