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 [e-mail]. Peter Winkler ( [e-mail]) is professor of mathematics and of computer science and albert Bradley third century professor in the sciences at Dartmouth college, Hanover, nH.