The Art and Craft of Problem Solving

3.4 INVARIANTS 97

left, P 4 in the right, etc. The important thing about this sequence is that P 7 ends up on
the left side, along with PI. Therefore L cannot pass through the interior of segment
PIP 7. a contradiction.

L

This argument certainly generalizes. As long as n is odd, then PI and Pn lie on the

same side of L. •

The following is a rather sophisticated problem, one that requires a parity analysis
combined with very resourceful and repeated use of the pigeonhole principle.

Example 3.4.10 (lMO^1 985) Consider a set of 1,985 positive integers, not necessarily
distinct, and none with prime factors bigger than 23. Prove that there must exist four
integers in this set whose product is equal to the fourth power of an integer.

Solution: We shall present the solution in a terse, sketchy form. It will be up to

you to fill in the details.

Every number in this set can be written in the form

2 f^1312 5 h 71411 f^513 f6 1^7 h I 9iR^23 f^9 ,

where the exponents 11 ,12, ... ,/9 are non-negative integers. The product of two such
numbers. 2 fl ... 2319 and 211 1 ... 23119 • will be a perfect square (square of an integer) if
and only if the corresponding exponents have the same parity (evenness or oddness).
In other words,

(2fl - -. 2319 ) -(2111 - - - 23119 )
will be a perfect square if and only if II and gl have the same parity. 12 and g 2 have
the same parity •...• 19 and g 9 have the same parity. (Recall that zero is even.) To each
number in this set there corresponds an ordered 9-tuple of the parities of the exponents.
For example. the number 2103517123111 has the 9-tuple (even, odd, even. even, even.
even. odd, even, odd).
There are 512 different 9-tuples possible. By repeated use of the pigeonhole prin­
ciple, we conclude that 1472 of the integers in our set can be arranged into 736 pairs