The Art and Craft of Problem Solving

184 CHAPTER 5 ALGEBRA for all positive x. Since x and the Uj are positive, we can define the real sequences ao = yfuO, al = JuI/ ...

5.5 INEQUALITIES^185 Thus (1 1) reduces to 2S(x+y+z);:::: (x+y+z)^2 , which in tum is equivalent to 2S ;:::: (x+y+z). But by AM- ...

186 CHAPTER 5 ALGEBRA which equals (a -b) (x -y) + (a -c) (x -z) + (b -c) (y -z), and this is positive. If you ponder this argum ...

5.5.35 If you have studied vector dot-product, you should be able to give a geometric interpretation of the Cauchy-Schwarz inequ ...

Chapter 6 Combinatorics 6.1 Introduction to Counting 188 Combinatorics is the study of counting. That sounds rather babyish, but ...

6.1 INTRODUCTION TO COUNTING 189 6.1.4 Let A and B be finite sets that are disjoint (A n B = 0). Then 6.1.2 is equivalent to the ...

190 CHAPTER 6 COMBINATORICS The Mississippi formula involves both multiplication and division. Let's examine the role of each op ...

6.1 INTRODUCTION TO COUNTING 191 In general, the number of ways you can select a subset of r distinct elements from a set of n d ...

192 CHAPTER 6 COMBINATORICS c�) P(IO,4) s·c:) c:) C 2 0 ) (7) + C;) G�) = (�) The number of ways of choosing a team of four peo­ ...

6.1 INTRODUCTION TO COUNTING 193 Let us count all II-member committees formed from a group of 18 people. Fix one of the 18 peopl ...

194 CHAPTER 6 COMBINATORICS 6.1.17 The Binomial Theorem. Formally, the binomial theorem states that, for all positive integers n ...

6.1 INTRODUCTION TO COUNTING 195 Strategies and Tactics of Counting When it comes to strategy, combinatorial problems are no dif ...

196 CHAPTER 6 COMBINATORICS the 20 children? Assume (the village is tradi­ tional) that all marriages are heterosexual (i.e., a ...

6.2 PARTITIONS AND BIJECTIONS 197 example, let us apply this method to Problem 6.1 .23, which asked us to prove that a set of n ...

198 CHAPTER 6 COMBINATORICS This method certainly generalizes to sets with n elements, so we have proven that the number of subs ...

6.2 PARTITIONS AND BIJECTIONS 199 The left-hand side of (2) is a sum, so we interpret it as a partitioning of a large set. Each ...

200 CHAPTER 6 COMBINATORICS "Joe, Sue, Jane" and "Jane, Joe, Sue." In other words, we need to correct for order by multiplying b ...

6.2 PARTITIONS AND BIJECTIONS 201 There are exactly two boys, and one girl chosen. Arguing as we did in 6.2.3 above, there are ...

202 CHAPTER 6 COMBINATORICS get "free" information and is just another example of monotonizing (see page 75). Since we are count ...

6.2 PARTITIONS AND BIJECTIONS 203 Example 6.2.6 Imagine a piece of graph paper. Starting at the origin draw a path to the point ...