The Art and Craft of Problem Solving

84 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS 3.3 The Pigeonhole Principle Basic Pigeonhole The pigeonhole principle,^3 in its simpl ...

3.3 THE PIGEONHOLE PRINCIPLE 85 After applying the pigeonhole principle, there is often more work to be done. Sometimes the pig ...

86 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS Intermediate Pigeonhole Here is a more elaborate version of the pigeonhole principle, ...

3.3 THE PIGEONHOLE PRINCIPLE 87 picking the rook in the row that has at least one rook. Then go to the row with at least two roo ...

88 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS ... + a j. So our pigeons have the right behavior, but unfortunately, there are only n ...

3.3 THE PIGEONHOLE PRINCIPLE 89 This set of pigeonholes does the trick. If we choose any six numbers from {1,2, ... , 1O}, then ...

90 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS The above problem was mathematically very sophisticated, and not just because it used ...

3.3 THE PIGEONHOLE PRINCIPLE 91 Next, "lift" each region up, with its lattice square. Think of each region as a picture drawn o ...

92 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS containing n distinct integers. If N ;::: 2 n, show that there is a consecutive block ...

is an invariant, always equal to zero. 3.4 INVARIANTS 93 Example 3.4.2 The Power of a Point Theorem. Given a fixed point P and a ...

94 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS Example 3.4.5 Divisibility by Nine. Let s(n) be the sum of the digits of the base-ten ...

3.4 INVARIANTS 95 Example 3.4.7 If 127 people play in a singles tennis tournament, prove that at the end of tournament, the numb ...

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 ...

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, alo ...

98 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS such that each pair contains two numbers with identical 9-tuples of exponent parity. T ...

3.4 INVARIANTS 99 The first insight is to discover an appropriate penultimate step. Let us call the property of having at least ...

100 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS Modular Arithmetic and Coloring Parity works amazingly well, but it is rather crude. ...

3.4 INVARIANTS 101 We conclude the solution by noting that the initial population was (10, II, Ill). The X-Y population gap is 1 ...

102 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS 1 2 3 4 5 6 12 1 2 3 4 5 Consequently, the entire large rectangle is not homogeneous, ...

3.4 INVARIANTS^103 If there are only finitely many states as something evolves, either a state will repeat, or the evolution wil ...