The Art and Craft of Problem Solving

98 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

such that each pair contains two numbers with identical 9-tuples of exponent parity.

Thus the product of the numbers in each pair is a perfect square. In other words, if we

let Ci := aibi, then every number in the list

CI,C 2 "",C 736

is a perfect square. Thus each of

Fl,,,foi,···, JC 736

is an integer with no prime factor greater than 23. Employing the pigeonhole principle

once more, we conclude that at least two numbers in the above list share the same

9-tuple of exponent parity. Without loss of generality, call these .JCk and JCj. Then

.JCkVCJ is an perfect square; i.e., .JCkVCJ = n^2 , for some integer n. Thus CkCj = n^4.

But CjCk = ajbjakbb so we have found four numbers from our original set of 1, 985

integers whose product is the fourth power of an integer. _

We conclude our discussion of parity with a famous problem, originally due (in

a different form) to de Bruijn [7]. At least fourteen different solutions have been dis­

covered, several of which use invariants in different ways (see [46] for a very readable

account of these solutions). The solution we present, using parity, is perhaps the sim­

plest, and is due to Andrei Gnepp. It is a beautiful solution; we urge you to first think

about the problem before reading it. That way you will appreciate just how hard the

problem is and how clever Gnepp's solution was!

Example 3.4. 11 A rectangle is tiled with smaller rectangles, each of which has at

least one side of integral length. Prove that the tiled rectangle also must have at least

one side of integral length.

Solution: Here is an example. The large rectangle has been placed on the plane

with grid lines marked at each unit, so that its lower-left comer is a lattice point.

Notice that each of the small rectangles has at least one integer-length side, and the

large 4 x 2. 5 rectangle also has this property. (The circles in the diagram are used in

our argument; we will explain them below.)

...........· .............. ............ ............... ............ ...........

· ·........

· ·........

I I

.. __ J. ... __ �_-4 .......................

... -----............ ...-.... -+ ................

L

I