Solutions and Sources
It’s amazing how little we know about the simple, ordinary, axis-aligned rectangle. Last month
(p. 112) we posted a trio of brainteasers, including one as yet unsolved, concerning rectangles
galore. Here, we offer solutions to at least two of them. How did you do?
1. Partitioning a Rectangle. Solution. We were given a large
rectangle in the plane, partitioned into
a finite number of smaller rectangles,
each with either integer width or integer height. Our mission was to prove
the big rectangle also has integer width
The puzzle was the subject of a famous article “Fourteen Proofs of a
Result About Tiling a Rectangle” by
Stan Wagon of Macalester College, St.
Paul, MN, in The American Mathematical Monthly 94 (1987). Here, we provide one of several solutions not found
among Wagon’s 14. Letting epsilon be
less than the smallest tolerance in the
partition, color each small rectangle of
integral width green, except for a red
horizontal strip of width epsilon across
the top and another across the bottom. Next, color each remaining small
rectangle red, except for a green vertical strip of width epsilon along the left
side and another along the right side.
Now place the lower-left point of the
big rectangle at the origin.
There is either a green path from the
left side of the big rectangle to the right
side or a red path from the bottom to
the top. Suppose the former. Every time
the green path crosses a vertical border
of the partition, it is at an integral coordinate. The big rectangle thus has integral width. Similarly, a red path from
bottom to top forces integral height.
2.Blocking the Enemy. Solution. Recall we were in a
large rectangular room with mirrored
walls, while elsewhere in the same
room was our mortal enemy, armed
with a laser gun. Our only defense was
our ability to summon graduate students to stand at designated spots in
the room blocking all possible shots
by the enemy. How many students
would we need? We assume for the
purposes of the problem that we, our
enemy, and the students are all thin
enough to be considered points. So,
for example, if we had continuum
many students, we could place them
around us in a circle (with the enemy
outside). But we can do better.
But the shots (once folded into the
original room) intersect one another
frequently, and, conceivably, a well-placed student could block infinitely
many shots. Indeed, it takes only 16
students to block every possible shot at
exactly its halfway point. To see how it
works, “trace” a copy of the plane tiling
onto a piece of paper, pin it to the plane
at our position P, and shrink the paper
copy by a factor of two vertically and
horizontally. The many copies of Q on
the shrunk copy will be the students’
positions, serving our purpose because
each copy of Q on the original tiling appears halfway between it and us on the
shrunk copy. There are infinitely many
such points, but all are copies of a set
of 16 points in the original room.
3.Covering a Big Rectangle. Unsolved. The third problem
is open. No one can prove we can even
get the small rectangles to cover at
least 1% of the big rectangle. Another
mystery is its origin. I heard it 20 years
ago from Bill Pulleyblank (now professor of operations research at the
U.S. Military Academy, West Point,
NY), though he doesn’t recall where
he got it.
Peter Winkler ( firstname.lastname@example.org) is professor
of mathematics and of Computer Science and albert
bradley third Century professor in the Sciences at
dartmouth College, hanover, nh.
All readers are encouraged to submit prospective
puzzles for future columns to email@example.com.