96 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS
is odd. Now we can recover the parity of the original aj. We see that six of them,are even, while the remaining five,are all odd. This is a contradiction, because the aj are a permutation of 1,2,3, ... , 11,
and this set contains five even and six odd elements. Clearly this argument extends to
the general case, for the only special property of 11 that we used was the fact that it
was odd. _Solution 2: The crux move: consider the sum of the terms. We have
(a )-I) +(a 2 - 2)+"'+(an- n)
= (a ) +a 2 + ... +an) -(1 +2+··· +n)
=(1+2+···+n)-(1+2+···+n)
=0,
so the sum is an invariant: it is equal to zero no matter what the arrangement. A sum
of an odd number of integers that equals zero (an even number) must contain at least
one even number! _Both solutions were nice, but the second was especially clever. Try to incorporate
the new idea here in future problems.Be on the lookout/or "easy" invariants. Check to see if you can rear
range your problem to get simple numbers such as zero or one.
Example 3.4.9 Let p) , P 2 , ... , P) 997 be distinct points in the plane. Connect the points
with the line segments P)P 2 ,P 2 P 3 ,P 3 P 4 " " ,P) 99 6 P) 997 ,P) 99 7 P). Can one draw a line
that passes through the interior of everyone of these segments?
Solution: It is not obvious that parity is an issue here, but one should always keep
parity in mind.
Whenever a problem involves integers, ask yourself if there are any
parity restrictions. Experiment with different values than the given if
necessary.
This problem involves 1997 points. A few experiments with much smaller num
bers of points will convince you easily (do it!) that it is possible to draw the line if
and only if the number of points is even. So parity seems to be important. Let us find
a rigorous argument for a specific case, say seven points. Once again, we will argue
by contradiction because assuming that we can draw the line gives us lots of specific
information that we can work with. So, assume there is a line L that passes through
the interior of each segment. This line cuts the plane into two regions, which we will
call the "left" and "right" sides of L. Without loss of generality, p) lies on the left side
of L. This forces P 2 to lie on the right side of L, which in tum forces P 3 to lie in the