An unexpectedly full weekend leaves me caught short without a full fledged blog post for today. I’ll make up for it tomorrow. In the meantime, here are two tidbits to hold you over:
- A useful recipe for salted water. Do not fail to read the reviews.
- A puzzle I got from the mathematician Alexander Merkurjev. If I recall right, he told me that it had appeared on a college entrance exam in the old Soviet Union:
A regular 400-gon is tiled by parallelograms. Prove that at least 100 of those parallelograms must be rectangles.
(A regular 400-gon is a 400-sided figure with all sides equal and all angles equal. The parallelograms can all be of different sizes and shapes—or not. “Tiled” means that the interior of the 400-gon is entirely covered, with no overlaps.)
Aw. The maths puzzle is one of those problems where the answer is obvious to me nearly at the second glance, but it would take me ages to put it down coherently.
I agree that it seems obvious, providing something I’d write down on a college entrance exam to be more than “it’s obvious, QED” took longer. Each of the steps below is still a bit weak.
Because only parallelograms are used, there must be a path (composed of adjacent parallelograms, maybe a couple wide*) through the 400-gon between opposite sides. Furthermore, this path has a cross section of width the same as the sides when measured parallel to opposite sides of the n-gon that it connects (even if no interior edge in the path is of that length)
Numbering the sides around the 400-gon, sides 50, 150, 250, 350 have a path between 50 and 250 and a path between 150 and 350. These intersect somewhere inside the parallelogram and all sides inside this region must be at right angles to each other. Since no side can be longer than the sides of the 400-gon, there must be at least one parallelogram completely inside this region, hence the region contains at least 1 rectangle.
This also generalizes to a 4n-gon having n rectangles.
* I think it’d be possible to prove than any tiling must be equivalent to a tiling where all parallelogram edges are the same length as the n-gon edges, with internal decomposition into smaller parallelograms, which simplifies the path argument a lot. I’d try to prove this if it was an untimed exam as it is much more elegant this way, but blog comments are more like a timed exam.
Dan, very elegant.
So I think this proves that those 100 parallelograms are not just rectangles, but squares, right? Because every parallelogram in the path leading from the north edge to the south edge, has a width equal to the edge lengths of the 400-gon, and every parallelogram in the path from the east edge to the west edge similarly has the same height, so the rectangle in their intersection has the same width and same height.
See, but couldn’t paths split? Like so (for an octagon):
—-
/| |\
/ | | \
/ |–| \
| / /\ \ |
| / / \ \ |
|/ / \ \|
|– –|
\ \ / /
\ \ / /
\ \/ /
—-
This can get hairy.
Aw, Steven’s blog doesn’t like my <pre> tags :(
Let’s try this:
Well I guess I’ll have to link to it.
hehe. interesting that the recipe was at 3.5 forks with a 78% ‘would make this again’. i was sorely tempted to leave my own review but thought it better to leave it here at the origin.
the puzzle is as usual far to difficult for me. it needs a dash of salt.
your optical illusionesque picture didnt help at all either, lukas.
Lukas is right, as I was driving to work, I realized that the could split. The sum of the widths (in a direction parallel to the original edge) of the split paths is at least as long as the original edge.
Each crossing is a parallelogram or a decomposition into multiple and hence has at least one rectangle. Pushing the conclusion a bit further, a 4n-gon has rectangles/2 + squares >= n, so each of the 100 rectangles is either “special” and is also square or there’s an additional rectangle somewhere in the figure.
@Bennett Haselton, I’m not clear on why “… every parallelogram in the path leading from the north edge to the south edge, has a width equal to the edge lengths of the 400-gon…” I would think that parallelogram sides of 1/2 edge length would work equally well.
As a test, I tiled an octogon with 1/2 edge length parallelograms, and found it easy to tile the octogon, and wound up with 8 squares.
This is an interesting question. I’d like to know the answer! I found a math problem set on the web that asks the same question for an octagon instead of a 400-gon, and then it asks the students to generalize their answer to the octogon. So we should probably think about the octagon first. lukas’s octagon drawing shows three rectangles but we could easy eliminate one of them, leaving only two.
Here is that problem set I mentioned:
http://math.uci.edu/~krubin/oldcourses/08.194/ps8.pdf
While I’m thinking about this problem, I am going to assume that there are a finite number of parallelograms, but hopefully I’ll discover later that this assumption is not necessary!
Actually we DO need to assume there are a finite number of paraellelograms. Otherwise, any tiling that has a rectangle can be modified by replacing the rectangle with an infinite number of non-rectangle parallelograms, to yield a tiling without rectangles that contradicts the problem statement.