last byte
DOI: 10.1145/1839676.1839700
Peter;Winkler
Puzzled
Rectangles Galore
Welcome to three new puzzles. Solutions to the first two will be
published next month; the third is (as yet) unsolved. In each,
the issue is how your intuition matches up with the mathematics.
The hero of this column is the
simple, ordinary, axis-aligned
rectangle. Looking out the
window, how many do you
see? My view at the moment of
Cambridge, MA, easily takes in
more than one thousand,
mostly windows. Asking new
questions about an old figure
helps us see it in a new light.
1.A large rectangle in the plane is partitioned into
a finite number of smaller
rectangles, each with either
integer width or integer height;
that is, its width, height, or
both width and height are
whole numbers of units. Now
prove that the large rectangle,
likewise, has integer width or
height (or both).
2.You are in a large rectangular room with
mirrored walls. Your mortal
enemy, armed with a laser
gun, is elsewhere in the room.
As your only defense, you
may summon a number of
graduate students to stand
at designated spots in the
room, blocking all possible
shots by the enemy. How many
students do you need?
3.Before you (on the plane) is a large rectangle
containing a finite number of
distinct dots, one of which is
at the rectangle’s lower-left-hand corner. Your objective
is to pack smaller, disjoint
rectangles into the big one
(with sides parallel to those of
the big one) in such a way that
each small rectangle includes
one of the dots as its own
lower-left-hand corner; see the
figure for an example.
Packing rectangles with six given dots at
their lower-left-hand corners.
The conjecture is that there
is always a way to choose the
small rectangles so they cover
at least half the area of the big
rectangle. Be the first ever to
prove it. A far as I know, no
one has succeeded in even
showing you can cover any
fixed fraction (say, 1/100) of the
area of the original rectangle.
Alternatively, if you
reject the conjecture, find
a counterexample, a way to
distribute the dots (be sure
to include the lower-left-hand
corner of the big rectangle) so
there is, provably, no way to do
the packing so as to cover half
the area of the big rectangle.
All readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.
Peter Winkler ( puzzled@cacm.acm.org) is professor of mathematics and of computer science and albert Bradley
third century professor in the sciences at Dartmouth college, Hanover, nH.