The Art and Craft of Problem Solving

104 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS Now we define two sequences. For r = 2,3, ... , define Lr := max{Ji : i > tr-t} an ...

3.4 INVARIANTS 105 There are three crucial things about S'. First of all, it satisfies S'^2 +S' - 1 =0. Also, it is positive. An ...

106 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS That, in fact, is where S came from in the first place! It was cleverly designed to m ...

on page 94, discover and prove a similar statement for divisibility by II. 3.4.23 Start with a set of lattice points. Each secon ...

108 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS asks intelligent questions!). If you cannot explain it to his satisfaction, go back a ...

Chapter 4 Three Important Crossover Tactics A crossover (first mentioned on page 54) is an idea that connects two or more differ ...

110 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS are the "objects" and we join vertices with edges if the corresponding objects a ...

4.1 GRAPH TH EORY 111 the example above), there will be a gap between the end of B2 and the start of AI. However, £2 must stradd ...

112 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS In a tree, we call the vertices with degree 1 leaves.^3 It certainly seems plaus ...

4.1 GRAPH THEORY 113 leaf cannot disconnect it), and has no cycles (since T had no cycles, and plucking a leaf cannot create a c ...

114 CHAPTER^4 THREE IMPORTANT CROSSOVER TACTICS Therefore if a graph has an Eulerian path, it must have either zero or exactly t ...

4.1 GRAPH THEORY 115 1. Start at s, as before, and travel along edges A, E, C until we reach vertex u. Now travel along the sub ...

116 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS This statement is weak, because the hypothesis is so strong. For example, suppos ...

4.1 GRAPH THEORY 117 j s Then the black dot walks from a to c, while the white one goes from s to q. Next, the black dot walks b ...

118 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS If a vertex is of the form (peak, trough), it is isolated (has degree zero). Th ...

the following statements is always true: "They haven't met," "They are good friends," or "They hate each other." Prove that ther ...

120 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS 4.1.24 If you place the digits 0, I, I, 0 clockwise on a circle, it is possible ...

4.2 COMPLEX NUMBERS 121 which is, of course, the length of the vector from the origin to (a, b). Other terms for magnitude are m ...

122 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS 4.2.4 Multip lication. All algebraic manipulations of complex numbers follow the ...

4.2 COMPLEX NUMBERS 123 Clearly this argument generalizes to multiplication by any complex number. Multiplication by the complex ...