Problem-Solving Methods in Combinatorics PDF

Problem-Solving Methods in Combinatorics Pablo Soberón Problem-Solving Methods in Combinatorics An Approach to Olympiad Problems Pablo Soberón Department of Mathematics University College London London, UK ISBN 978-3-0348-0596-4 ISBN 978-3-0348-0597-1 (eBook) DOI 10.1007/978...

Problem-Solving Methods in Combinatorics Pablo Soberón Problem-Solving Methods in Combinatorics An Approach to Olympiad Problems Pablo Soberón Department of Mathematics University College London London, UK ISBN 978-3-0348-0596-4 ISBN 978-3-0348-0597-1 (eBook) DOI 10.1007/978-3-0348-0597-1 Springer Basel Heidelberg New York Dordrecht London Library of Congress Control Number: 2013934547 Mathematics Subject Classification: 05-01, 97K20 © Springer Basel 2013 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be true and accurate at the date of pub- lication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Printed on acid-free paper Springer Basel is part of Springer Science+Business Media (www.birkhauser-science.com) Contents 1 First Concepts............................... 1 1.1 Sets and First Countings....................... 1 1.2 Induction............................... 5 1.3 Paths in Boards........................... 9 1.4 A Couple of Tricks.......................... 12 1.5 Problems............................... 15 2 The Pigeonhole Principle......................... 17 2.1 The Pigeonhole Principle...................... 17 2.2 Ramsey Numbers.......................... 20 2.3 The Erdős-Szekeres Theorem.................... 22 2.4 An Application in Number Theory................. 23 2.5 Problems............................... 24 3 Invariants................................. 27 3.1 Definition and First Examples.................... 27 3.2 Colorings............................... 31 3.3 Problems Involving Games..................... 33 3.4 Problems............................... 37 4 Graph Theory............................... 43 4.1 Basic Concepts............................ 43 4.2 Connectedness and Trees...................... 47 4.3 Bipartite Graphs........................... 51 4.4 Matchings.............................. 53 4.5 Problems............................... 55 5 Functions................................. 59 5.1 Functions in Combinatorics..................... 59 5.2 Permutations............................. 63 5.3 Counting Twice........................... 69 5.4 The Erdős-Ko-Rado Theorem.................... 72 5.5 Problems............................... 74 6 Generating Functions.......................... 77 6.1 Basic Properties........................... 77 v vi Contents 6.2 Fibonacci Numbers......................... 80 6.3 Catalan Numbers........................... 82 6.4 The Derivative............................ 85 6.5 Evaluating Generating Functions.................. 87 6.6 Problems............................... 90 7 Partitions................................. 93 7.1 Partitions............................... 93 7.2 Stirling Numbers of the First Kind................. 94 7.3 Stirling Numbers of the Second Kind................ 96 7.4 Problems............................... 98 8 Hints for the Problems.......................... 101 8.1 Hints for Chap. 1........................... 101 8.2 Hints for Chap. 2........................... 102 8.3 Hints for Chap. 3........................... 104 8.4 Hints for Chap. 4........................... 106 8.5 Hints for Chap. 5........................... 108 8.6 Hints for Chap. 6........................... 109 8.7 Hints for Chap. 7........................... 111 9 Solutions to the Problems........................ 113 9.1 Solutions for Chap. 1........................ 113 9.2 Solutions for Chap. 2........................ 120 9.3 Solutions for Chap. 3........................ 128 9.4 Solutions for Chap. 4........................ 138 9.5 Solutions for Chap. 5........................ 146 9.6 Solutions for Chap. 6........................ 156 9.7 Solutions for Chap. 7........................ 164 Notation..................................... 169 References................................... 171 Index...................................... 173 Introduction Every year there is at least one combinatorics problem in each of the major math- ematical olympiads of international level. These problems have the common trait of needing a very high level of wit and creativity to find a solution. Even in the most recent competitions there are difficult problems that can be solved almost completely by a single brilliant idea. However, to be able to attack these problems with comfort it is necessary to have faced problems of similar difficulty previously and to have a good knowledge of the techniques that are commonly used to solve them. I write this book with two purposes in mind. The first is to explain the tools and tricks necessary to solve almost any combinatorics problems in international olympiads, with clear examples of how they are used. The second way to offer to the olympic students (and other interested readers) an ample list of problems with hints and solutions. This book may be used for training purposes in mathematical olympiads or as part of a course in combinatorics. Despite the fact that this book is self-contained, previous contact with combina- torics is advisable in order to grasp the concepts with ease. In the section “Further reading” we suggest material for this purpose. Reading this would be especially use- ful for familiarizing with the notation and basic ideas. It is also required to have a basic understanding of congruences in number theory. The book is divided into 7 chapters of theory, a chapter of hints and a chapter of solutions. The theory chapters provide examples and exercises along the text and end with a problems section. In total there are 127 problems in the book. The purpose of the exercises is for the reader to start using the ideas of the chapter. There are no hints nor solutions for the exercises, as they are (almost always) easier than the problems. All examples and problems have solutions. Although the text is intended to be read in the order it is presented, it is possible to read it following the diagram below. vii viii Introduction Many of the problems and examples of this book have appeared in mathematical contests, so I have tried to provide references to their first appearance. I apologize if any are missing or just plain wrong. At the end of the book, where the notation is explained, there is a list of abbreviations that were used to make these references. I would like to thank Radmila Bulajich for both teaching me the necessary LATEX to write this book and to motivating me to do so. Without her support this project would have never been brought to completion. I would also like to thank the exten- sive corrections and comments by Leonardo Martínez Sandoval as well as the ob- servations by Adrián González-Casanova Soberón and Carla Márquez Luna. Their help shaped this book to its present form. Pablo Soberón For the Student Even though a large number of problems in combinatorics have a quick and/or easy solution, that does not mean the problem one has to solve is not hard. Many times the difficulty of a problem in combinatorics lies in the fact that the idea that works is very well “hidden”. Due to this the only way to really learn combinatorics is solving many problems, rather than reading a lot of theory. This practice is precisely what teaches you how to look for these creative or hidden ideas. As you read the theory you will find exercises and examples. It is important to do them as they come along, since many of them are an important part of the theory and will be used repeatedly later on. When you find an example, try to solve it by your- self before reading the solution. This is the only way to see the complications that particular problem brings. By doing this you will have an easier time understanding why the ideas in the solution work and why they should be natural. Introduction ix At the end of each chapter there is a section with problems. These problems are meant to be harder than the exercises and they have hints and solutions at the end of the book. Many problems are of an international competition level, so you should not become discouraged if you find a particularly difficult one. Some problems have more than one solution. This does not mean that these solu- tions are the only ones. Chase your own ideas and you will probably find solutions that differ from the ones presented in this book (and perhaps are even better). Thus, when you reach a problems section, do not restrict yourself to the tools shown in that chapter. Finally, my main objective when writing this book was not simply to teach com- binatorics, but for the book to be enjoyed by its readers. Take it easy. Remember that solving problems is a discipline that is learned with constant practice and leads to a great sense of satisfaction. First Concepts 1 1.1 Sets and First Countings A set is defined to be a “collection of elements contained within a whole”. That is, a set is defined only by its elements, which can also be sets. When we write {a, b, c} = S, we mean that S is the set that has the elements a, b, c. Two sets are equal if (and only if) they have the same elements. To indicate that a is an element of S, we write a ∈ S. In a set we never repeat elements, they can just be in the set or not be there. Given a set A and a property ψ, we denote by {a ∈ A | ψ(a)} the set of all elements of A that satisfy property ψ. For example, {a ∈ R | a > 2} is the set of all real numbers that are greater than 2. By convention, there is an empty set. That is, a set with no elements. One usually denotes that set with the symbol ∅. When we say that a set has to be contained within a whole, we mean that it should not be “too big”. This is a very technical detail, but there are collections (such as the collection of all sets) that bring difficulties if we consider them as sets. Throughout this book we will never face this kind of difficulties, even when we talk about infinite sets. However, it is important to know that there are collections that are not sets.1 Given two sets A and B, we say that A is a subset of B, or that A is contained in B, if every element of A is an element of B. We denote this by A ⊂ B. For example {1, 2} ⊂ {1, {1, 3}, 2} since 1 and 2 are elements of the second set. However, {1, 3} ⊂ {1, {1, 3}, 2} since 3 is not an element in the second set. Given two sets A and B, we can use them to generate other sets. A ∩ B, called the intersection of A and B. This is the set that consists of all the elements that are in both A and B. A ∪ B, called the union of A and B. This is the set that consists all the elements that are in at least one of A or B. 1 Ifyou want an example of this, consider Russell’s paradox. Let S be the collection of all sets that do not contain themselves as elements, i.e., all sets A such that A ∈ / A. If S is considered as a set, then S ∈ S if and only if S ∈ / S, a contradiction! P. Soberón, Problem-Solving Methods in Combinatorics, 1 DOI 10.1007/978-3-0348-0597-1_1, © Springer Basel 2013 2 1 First Concepts P(A), called the power set of A. This is the set made by all subsets of A. Using the notation above, we would write P(A) = {B | B ⊂ A}. In general we have that A ⊂ A and ∅ ⊂ A for any set A, so they are elements of P(A). Notice that P(∅) is not ∅, but rather {∅}. We say that two sets A and B are disjoint if A ∩ B = ∅. In other words, they are disjoint if they have no elements in common. Given a set A, |A| denotes the number of elements of A. This number is called the cardinality of A. Example 1.1.1 Prove that A ∩ B is the largest set that is contained in A and in B. Solution Note that by the definition of A ∩ B, it is contained in both A and B. Consider any set C that is contained both in A and B. Given any x ∈ C, we know that x ∈ A since C is contained in A and x ∈ B since C is contained in B. Thus, x ∈ A ∩ B. Since this works for every x ∈ C, we have that C ⊂ A ∩ B, as we wanted.  Exercise 1.1.2 Prove that A ∪ B is the smallest set that contains both A and B. Exercise 1.1.3 Prove that if A ⊂ B, then P(A) ⊂ P(B). Exercise 1.1.4 Prove that if P(A) = P(B), then A = B. The concepts  of union and intersection can be extended a bit more. If C is a set of sets,  then C is the set made by all the elements that are in at least one set of C, and C  is the set that consists of all the elements that are in every set of C. For example, {A, B} = A ∩ B. These are the concepts that we are going to work with. We are going to be inter- ested in how they behave. Combinatorics is the branch of mathematics that studies finite or discrete sets and structures (such a graphs). For example, counting or enu- merating sets or events are part of combinatorics. Every time that a question of the type “In how many ways can this happen?” arises, the arguments that are going to be used for the solution are part of combinatorics. Sets are the basic objects we are go- ing to be counting. This will be done either by their properties or by the events that they represent. To do these countings, there are two basic laws we have to follow. Law of the sum If an event A can happen in m different ways and an event B can happen in n different ways, then the number of ways in which A or B can happen is m + n. Law of the product If an event A can happen in m different ways and an event B can happen in n different ways, then the number of ways in which A and then B can happen is mn. Example 1.1.5 Given non-negative integers k ≤ n, how many ordered lists of k different elements can be made if there are n different elements available? 1.1 Sets and First Countings 3 Solution Notice that to choose the first element, there are n options. Then, to choose the second element, there are n − 1 options. By the law of the product, to choose the first two elements there are n(n − 1) options. To choose the third element there are n − 2 options, so to choose the first three elements there are n(n − 1)(n − 2) possible ways. If we continue this way, to choose the first k elements (in order) there are n(n − 1)(n − 2) · · · (n − k + 1) different ways.  If in the previous example n = k, then we see that the number of ways to order the n elements is n · (n − 1) · (n − 2) · · · 2 · 1. This is the number of ways to order all the elements of the original set. This number is denoted by n!, which is read as “n factorial”. We define 0! as 1. An ordering of a list is also called a permutation of the list. In the following chapters we will study permutations from another point of view. Example 1.1.6 If A is a set with n elements, how many subsets does it have? Solution To solve this example the event we want to count is that of forming a subset of A. We can form it by choosing one element at a time. That is, for each element of A we choose whether it is going to be in the subset or not. For every element there are 2 options (to be included in the subset or not), so using the law of the product n − 1 times we obtain that the number of subsets of A is 2n.  In other words, if |A| = n, then |P(A)| = 2n. Proposition 1.1.7 The number of subsets of k elements of a set with n elements is n! k!(n−k)!. Proof To see this, notice that when we count the number of lists of k elements, every subset of size k is counted once for every way of ordering its elements. The number of lists of k elements is n(n − 1) · · · (n − k + 1) and the number of ways to order k elements in a list is k!. Thus the number we are looking for is n(n−1)(n−2)···(n−k+1) k! = n! k!(n−k)!.    These numbers are also denoted by nk , Ckn or Cnk and are known as the bino- n mial coefficients. k is usually read as “n choose k”. They are given this name because, when we expand (a + b)n , these numbers appear in the coefficients. In a more explicit way: Theorem 1.1.8 (Newton) Let n be a positive integer. Then         n   n n n n−1 n n−2 2 n n  n n−k k (a + b) = n a + a b+ a b + ··· + b = a b. 0 1 2 n k k=0 4 1 First Concepts Proof First we have to notice that (a + b)n = (a + b)(a + b) · · · (a + b). n times That is, in each factor (a + b) of the product we have to choose either a or b. Since there are n factors, every term in the result is of the form a r bs with r + s = n. The term a n−k b kappears once for every way to choose k times the term b in the product. There are nk ways to do this, which is the number we were looking for.   We are going to set nk = 0 if k is greater than n or is negative.  Example 1.1.9 In a set there are n red objects and m blue objects. How many pairs of elements of the same color can be made? Solution There are two cases: that n the pair of objects is red or the pair of objects is blue. In the first case there are 2 ways to choose the pair and in the second there m n m are 2 ways to choose the pair. By the law of the sum there are in total 2 + 2 possible pairs.  n  n  Exercise 1.1.10 Prove that k = n−k. n  n  n+1 Exercise 1.1.11 (Pascal’s formula) Prove that k + k+1 = k+1. n n n Exercise 1.1.12 Prove that 2n = 0 + 1 + ··· + n. Exercise 1.1.13 Prove that if n ≥ 1, then           n n n n n n 0= − + − + · · · + (−1). 0 1 2 3 n n+1   n+1 n Exercise 1.1.14 Prove that k+1 = k+1 k.     n−1 Exercise 1.1.15 Prove that (n − 2k) nk = n n−1 k − k−1. Exercise 1.1.16 Using Exercise 1.1.15 prove that2         n n n n < < < ··· < n. 0 1 2 2 n+1 n−1 Exercise 1.1.17 Prove that 3 − 3 = (n − 1)2. 2 x denotes the greatest integer that is smaller than or equal to x. 1.2 Induction 5 n2  n  n  Exercise 1.1.18 Prove that if n > r > 0, then r > r+1 r−1. a  b  a+1 b−1 Exercise 1.1.19 Prove that if a < b, then 2 + 2 ≥ 2 + 2. p  Exercise 1.1.20 Prove that if p is prime and 0 < k < p, then k is divisible by p. 1.2 Induction Mathematical induction is a technique used to prove statements. The idea is similar to making several domino pieces fall. If every piece is close enough to the previous one and we make the first one fall, then they are all going to fall. When we want to prove a statement about natural numbers, the idea is the same. Here statements are going to involve a variable n which is a positive integer. We say that P (n) is the statement for a certain n. To prove that P (n) is true for all n, it is enough to prove the following: Basis of induction: Prove that P (1) is true. (Verifying that the first piece of domino falls.) Induction hypothesis: Suppose that P (n) is true (here we are thinking that n is a fixed integer). Inductive step: Prove that P (n + 1) is true. (Showing the if the n-th piece of domino falls, then so does the (n + 1)-th.) If these steps hold, then P is true for every positive integer n. If we want to prove the statement starting on some n0 that is not necessarily 1, we only have to change the induction basis to: Prove that P (n0 ) is true. Whenever we use induction, we want to reduce the proof of P (n + 1) to P (n). Since we supposed that P (n) was true (by the induction hypothesis), we are able to finish. This method usually makes proofs much easier. Let us see some examples: Example 1.2.1 (Gauss formula) Prove that if n is a positive integer, then 1 + 2 + 3 + · · · + n = n(n+1) 2. n(n+1) Solution Take for P (n) the assertion “1 + 2 + 3 + · · · + n = 2 ”. Basis of induction: If n = 1, then 1 = 1(1+1) 2 , thus P (1) is true. Induction hypothesis: Suppose that P (n) is true. Inductive step: We want to prove that P (n + 1) is true. To show that, notice that 1 + 2 + 3 + · · · + (n + 1) = (1 + 2 + · · · + n) + (n + 1). 6 1 First Concepts By the induction hypothesis, this is equal to n(n + 1) n(n + 1) + 2(n + 1) (n + 2)(n + 1) + (n + 1) = = , 2 2 2 which is what we wanted to prove.  n+1 Example 1.2.2 Let k and n be non-negative integers, with n ≥ k. Prove that = k  k+1 n k+1 k + k + ··· + k. n+1 k  k+1 n Solution Consider P (n) as “ k+1 = k + k + ··· + k ”. Basis of induction: Since we want to prove the statement for n ≥ k, the basis of induction should be when n = k. That is, to prove that     k k+1 =. k k+1 Since both parts are equal to 1, this is true. Induction Hypothesis: Suppose that P (n) is true. Inductive step: We want to prove that P (n + 1) is true. That is, that         n+2 k k+1 n+1 = + + ··· +. k+1 k k k Notice that               k k+1 n+1 k k+1 n n+1 + + ··· + = + + ··· + +. k k k k k k k   The first part is equal to n+1 k+1 by the induction hypothesis. So we want to prove that       n+2 n+1 n+1 = +. k+1 k+1 k This is true by Pascal’s formula (Exercise 1.1.11).  Here the induction was made on n. The statement really depends on k and n, so one might try using induction on k as well. However, in this case it would be much harder to reduce the problem to the previous case, so it is not a very good idea. Whenever the statement depends on more than one variable it is important to identify on which one it is easier to use induction. 1.2 Induction 7 Exercise 1.2.3 Prove that 1 + 3 + 5 + · · · + (2n − 1) = n2 for every positive inte- ger n. n(n+1)(2n+1) Exercise 1.2.4 Prove that 12 + 22 + · · · + n2 = 6 for every positive inte- ger n. Exercise 1.2.5 Prove that if q is a real number, q = 1 and n is a positive integer, then 1 + q + q 2 + · · · + q n = q q−1−1. n+1 Exercise 1.2.6 Prove that if q is a real number, q = 1 and n is a positive integer, n+1 n 1−q 2 then (1 + q)(1 + q 2 )(1 + q 4 ) · · · (1 + q 2 ) = 1−q. Exercise 1.2.7 Prove that if q is a real number, q = 1 and n is a positive integer, n +nq n+1 then 1 + 2q + 3q 2 + · · · + nq n−1 = 1−(n+1)q (1−q)2. √ Exercise 1.2.8 Prove that √1 + √1 + ··· + √1 n ≥ n for every positive integer n. 1 2 Exercise 1.2.9 Prove Theorem 1.1.8 by induction. Exercise n n 1.2.10 n Prove that ifm m, n  integers such that 0 ≤ m ≤ n, then n are positive m n−1. 0 − 1 + 2 − · · · + (−1) m = (−1) m Note that this exercise implies Exercise 1.1.13. The following exercises deal with Fibonacci’s numbers; these are defined by Eqs. (6.3) and (6.4). Exercise 1.2.11 Prove that F1 + F2 + · · · + Fn = Fn+2 − 1 for every positive inte- ger n. Exercise 1.2.12 Prove that F1 +F3 +· · ·+F2n−1 = F2n for every positive integer n. Exercise 1.2.13 Prove that F2n = Fn+1 2 − F2 n−1 for every integer n ≥ 2. Exercise 1.2.14 Prove that F2n+1 = Fn+1 2 + F 2 for every integer n ≥ 2. n Exercise 1.2.15 Prove that F12 + F22 + F32 + · · · + Fn2 = Fn Fn+1 for every positive integer n. In every proof by induction, we have to suppose that the previous case is valid. However, it may happen that the validity of the previous case is not enough. For such situations we can use strong induction. In this type of induction, instead of using that the previous case is valid, we are going to use that all previous cases are valid. That is, the induction hypothesis is that for every k ≤ n, P (k) is true. It can be 8 1 First Concepts proven that induction and strong induction are equivalent, but this will not be done in this book. So far we have only seen how to use induction to prove formulas; now let us examine an example that is a bit more difficult (the first problem of international olympiad level we face!). Example 1.2.16 (IMO 2002) Let n be a positive integer and S the set of points (x, y) in the plane, where x and y are non-negative integers such that x + y < n. The points of S are colored in red and blue so that if (x, y) is red, then (x , y ) is red as long as x ≤ x and y ≤ y. Let A be the number of ways to choose n blue points such that all their x-coordinates are different and let B be the number of ways to choose n blue points such that all their y-coordinates are different. Prove that A = B. Proof Let ak be the number of blue points with x-coordinate equal to k and bk the number of blue points with y-coordinate equal to k. Using n − 1 times the law of the product, we have that A = a0 a1 a2 · · · an−1. In the same way we have that B = b0 b1 b2 · · · bn−1. We are going to prove that the numbers a0 , a1 ,... , an−1 are a permutation of the numbers b0 , b1 ,... , bn−1 using strong induction. By proving this, we will establish that their product is the same. If n = 1, S consists of only one point. Then, a0 and b0 are both 1 or 0 depending on whether the point is painted blue or red, so a0 = b0. Suppose the assertion holds for every k ≤ n and we want to prove it for n + 1. There are two cases: 1. every point (x, y) with x + y = n is blue, or 2. at least one of them is red. In case 1, let S be the set of points (x, y) such that x + y < n and let ak be the number of blue points in S with k in the x-coordinate and bk the number of blue points in S with k in the y-coordinate. Then a0 , a1 ,... , an−1 is a permutation of b0 , b1 ,... , bn−1 (by the induction hypothesis). We also know that an = bn = 1 and ak = ak + 1, bk = bk + 1 for every k < n. So b0 , b1 ,... , bn is a permutation of a0 , a1 ,... , an. In case 2, let us suppose (k, n − k) is red. Let S1 be the set of points (x, y) with x + y < n + 1, x < k and y > n − k. Notice that a0 , a1 ,... , ak−1 and bn−k+1 , bn−k+2 ,... , bn are the ai and bi that would be associated with S1. Thus, 1.3 Paths in Boards 9 by the induction hypothesis, one is a permutation of the other. In the same way, ak+1 , ak+2 ,... , an is also a permutation of b0 , b1 ,... , bn−k−1. Since ak = bn−k = 0, we have that a0 , a1 ,... , an is a permutation of b0 , b1 ,... , bn.  The next example is significantly harder than the previous one, even though the solution seems simpler. This problem was the hardest one in the 2009 IMO and, if we consider the average number of points the students obtained, it is the second hardest problem to appear in an IMO (up to 2011). It is surprising that a problem with this level of difficulty can be solved using only the theory we have seen so far. Example 1.2.17 (IMO 2009) Let a1 , a2 ,... , an be different positive integers and M a set of n − 1 positive integers not containing the number s = a1 + a2 + · · · + an. A grasshopper is going to jump along the real axis. It starts at the point 0 and makes n jumps to the right of lengths a1 , a2 ,... , an in some order. Prove that the grasshop- per can organize its jumps in such a way that it never falls in any point of M. Solution We proceed by strong induction on n. For this we order the steps as a1 < a2 < · · · < an and the elements of M as b1 < b2 < · · · < bn−1. Let s = a1 + a2 + · · · + an−1. If we remove an and bn−1 , there are two cases. s is not among the first n − 2 elements of M. In this case, by induction, we can order the first n − 1 jumps until we reach s. If at any moment we fell on bn−1 , we change that last step for an and then we continue in any way to reach s. By induction we know that we have never fallen on b1 , b2 ,... , bn−2. Also, if we had to use the change, since there are no elements of M after bn−1 , we do not have to worry about falling on a bk in the rest of the jumps. s is one of the first n − 2 elements of M. If this happens, then since s = s − an is in M, among the 2(n − 1) numbers of the form s − ai , s − ai − an with 1 ≤ i ≤ n − 1 there are at most n − 2 elements of M. If we look at the pairs of numbers (s − ai , s − ai − an ), since we have n − 1 of these pair and they contain at most n − 2 elements of M, there is a number ai such that neither s − ai , nor s − ai − an are in M. Notice that after s − ai − an we have s and bn−1 , which are two elements of M. Therefore, there are at most n − 2 elements of M before s − ai − an. Then, by the induction hypothesis, we can use the other n − 2 jumps to reach s − ai − an , then use an and then use ai to get to s without falling on a point of M.  1.3 Paths in Boards Suppose we have a board of size m × n (m rows and n columns) divided into unit squares. How many paths are there on the sides of the squares that move only up or to the right and go from the bottom left corner to the top right one? (See Fig. 1.1.) Solution Every path must go up m times and to the right n times. In total there must be m + n steps. Consider an alphabet made only of the letters U and R. It is clear that for every path there is one and only one word of m + n letters of this alphabet, 10 1 First Concepts Fig. 1.1 Example of path if n=m=5 Fig. 1.2 Example with the same path where U means to go up and R means to go to the right. For example, in the path of the figure the word would be (U, U, R, R, U, U, R, R, R, U ). To form a word with these properties, we only have to choose which are the m places of the m+ n possible ones in which we are going to write the letter U. This can be done in m+nm ways.  Proposition 1.3.1 If n is a positive integer, then    2  2  2  2 2n n n n n = + + + ··· +. n 0 1 2 n   First Proof Consider an n × n board divided into unit squares. Then 2n n is the number of paths that move on the sides of the squares, move always up or to the right and go from the bottom left corner to the top right one. Let P0 , P1 ,... , Pn be the points in the diagonal of the board that goes through the top left corner. (See Fig. 1.2.) If we want to go from the bottom left corner to the point Pk we have to move k n  times to the right and n − k times up. There are n−k ways to reach this point. To go from Pk to the top right corner of the board, we have to move n − k times to the 1.3 Paths in Boards 11   right and k times up. There are nk ways of doing this. Thus the number of paths  n n n2 that go through Pk is n−k k = k (by Exercise 1.1.10). Since every path must go through exactly one point of that diagonal, using the law of the sum n times we obtain the desired result.  Second Proof We prove the proposition by counting certain sets. Suppose we have a set of n blue balls and n red balls (all balls can be distinguished from each  other).  We want to count the number of subsets of n balls. We know there are 2n n such subsets. Let us count how many sets there are such that k of the balls are red. For   n  n2 this we have to choose k red balls and n − k blue ones, which gives nk n−k = k such sets. Since the number of red balls can vary from 0 to n, we get the desired result.  2p Exercise 1.3.2 Let p be a prime integer. Prove that p − 2 is divisible by p 2 (recall Exercise 1.1.20). Exercise 1.3.3 (Vandermonde’s formula) Let n, m be non-negative integers such that n ≥ m. Prove that               n+m n m n m n m n m = + + + ··· +. m 0 m 1 m−1 2 m−2 m 0 In some combinatorics problems it is very helpful to think in terms of paths in boards. Let us see an example where we can use the proposition we just proved. Example 1.3.4 (OIM 2005) Let n be a positive integer. On a line there are 2n marked points A1 , A2 ,... , A2n. We are going to color the points blue or red in the follow- ing way: n disjoint circles are drawn with diameters of extremities Ai and Aj for some i, j. Every point Ak with 1 ≤ k ≤ n belongs to exactly one of these circles. The points are colored in such a way that the two points of a circle have the same color. Find the number of different colorings of the 2n points that can be obtained by changing the circles and the distribution of colors. Solution Let a1 , a2 ,... , a2n be the points on the line, in that order. Notice that if two points are in the same circle, between them there must be an even number of points, and thus the circles join points with even index with points with odd index. Thus there is the same number of odd red points and even red points. We are going to prove by induction on n that any coloring that has the same number of even red points and odd red points can be obtained by drawing circles. If n = 1, both points must have the same color, thus by drawing the circle that has their segment as diameter we are done. If there are two consecutive points with the same color, we can draw a circle that has them as diameter, and we are left with 2(n − 1) points as indicated. These 2(n − 1) points can be colored using circles (by the induction hypothesis). If there are no two consecutive points of the same color, 12 1 First Concepts Fig. 1.3 List of balls and delimiters that generates (2, 2, 0, 3, 1, 1, 0, 0, 0) then all even points have one color and all odd points have another, which contra- dicts our hypothesis. Notice that the arrangement of the circles that gives a coloring does not need to be unique. For example, if all points are red, any arrangement of circles can give that coloring.     If we want to have k odd red points, we have nk ways to choose them, and nk n2 ways to choose the even red points. Thus the total number of colorings is 0 + n2 n2 n2 2n 1 + 2 + ··· + n = n.  1.4 A Couple of Tricks In this section we mention two classic tricks that are used frequently in counting problems. The first one is to introduce delimiters to solve a problem. The second one is known as the inclusion-exclusion principle, and allows us to know the size of the union of some sets if we know the size of their intersections. Example 1.4.1 Suppose that we have 9 identical balls and 9 distinguishable bins. We want to count the number of ways to distribute the balls in the bins (there may be several or no balls in the same bin). (See Fig. 1.3.) Solution To count the different distributions, we are only interested in how many balls there are in the first bin, how many balls there are in the second bin, etc. In other words, the number of arrangements is the same as the number of ordered lists of integers (n1 , n2 ,... , n9 ) such that ni ≥ 0 for all i and n1 + n2 + · · · + n9 = 9. This is called a Diophantine equation (with coefficients 1). Now consider 17 objects in a line. We are going to choose 8 of them to be the “delimiters”. The other objects are going to represent the balls. We say that n1 is the number of balls before the first delimiter, n2 is the number of balls between the first delimiter and the second one,... , n9 is the number of balls after the eighth delimiter. It is clear that we obtain a list of the kind we were looking for, and also that any of such lists corresponds to an arrangement   of 9 balls and 8 delimiters in a line. Thus the number we are looking for is 17 8.  In the general problem  when we want to distribute n identical object in m places, we can do it in n+m−1 m−1 ways, and that is equal to the number of lists (n1 , n2 ,... , nm ) of non-negative integers such that n1 + n2 + · · · + nm = n. Exercise 1.4.2 There are 10 boxes and 30 balls, of which 10 are green, 10 are blue and 10 are red. The balls of the same color are identical. In how many different ways can we distribute the 30 balls in the 10 boxes? 1.4 A Couple of Tricks 13 Exercise 1.4.3 Show that the number of lists  n (b1 , b2 ,... , bm+1 ) of positive integers such that b1 + b2 + · · · + bm+1 = n + 1 is m. Example 1.4.4 Let m, k be positive integers. How many lists (n1 , n2 ,... , nk ) of k numbers are there such that 0 ≤ n1 ≤ n2 ≤ · · · ≤ nk ≤ m? First Solution (with delimiters) Consider an arrangement of m balls and k delim- iters. If we label the delimiters from left to right, we can define ni as the number of balls to the left of the i-th delimiter. It is now clear that the number of lists we are looking for is the same as the number of arrangements of m balls and k delimiters, which is m+k k.  Second Solution (without delimiters) Consider the list (m1 , m2 ,... , mk ) defined by mi = ni + i. Then we have that 1 ≤ m1 < m2 < · · · < mk ≤ m + k. For every list (m1 , m2 ,... , mk ) that satisfies that condition we can construct (n1 , n2 ,... , nk ). However, the mi are k different numbers, and for every choice of k different num- bers, they generate only one of such lists. Thuswe only  have to choose k numbers between 1 and m + k, for which there are only m+k k possible ways.  Third Solution (using the previous example) Consider b1 = n1 , b2 = n2 − n1 ,... , bk = nk − nk−1 , bk+1 = m − nk. We know that bi ≥ 0 for all i and that b1 + b2 + · · · + bk+1 = m. The number of lists (b1 , b2 ,... , bk+1 ) with those prop- erties is the same as the number of lists (n1 , n2 ,... , nk ) we were  looking for. By the previous example, we know there are m+(k+1)−1 (k+1)−1 = m+kk such lists. In this solution,  if we only define b1 , b2 ,... , bk and fix nk = j , we know there are in total j +k−1 possible lists. Since j can go from 0 to m, we have that in total there are k−1 k−1   k  m+k−1 k−1 + k−1 + · · · + k−1 lists. Using this and one of the previous solutions, we have a non-inductive solution to Example 1.2.2.  Now let us introduce the inclusion-exclusion principle. For this, suppose we have three sets A, B, C and we want to find |A ∪ B ∪ C|. If we count the elements of each set, there are |A|+|B|+|C|. However, we have counted twice every element that is in two of them, so we must subtract |A ∩ B| + |B ∩ C| + |C ∩ A|. However, by doing this we are no longer counting the elements that are in all three of them, so we must add |A ∩ B ∩ C|. In the end we have   |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| + |B ∩ C| + |C ∩ A| + |A ∩ B ∩ C|. This line of reasoning can be extended to any finite number of sets. Proposition 1.4.5 (Inclusion-exclusion principle) Let A1 , A2 ,... , An be sets. Then  n          Ai  = |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − · · ·   i=1 1≤i≤n 1≤i cj , we can add cj to the largest decreasing subsequence that ends in ci , so we have a decreasing subsequence of length bi + 1 that ends in cj. This gives bj ≥ bi + 1. If there were no subsequences of the lengths we were looking for, then for each 1 ≤ j ≤ ab + 1 we would have aj ≤ a and bj ≤ b. This would give us at most ab different pairs. Since we have ab + 1 pairs, by the pigeonhole principle at least two must be equal, which is a contradiction.  Exercise 2.3.2 Given any two positive integers a and b, find a sequence of ab dif- ferent real numbers with no increasing subsequences of length a + 1 or more and no decreasing subsequences of length b + 1 or more. 2.4 An Application in Number Theory 23 2.4 An Application in Number Theory Besides its importance in combinatorics, the pigeonhole principle has various strong applications in number theory. One of the most known ones is in showing that the decimal representation of any rational number2 is periodic after some point. In other words, after some point is begins to repeat itself. In this section we show a different application, establishing that every prime number of the form 4k + 1 can be written as the sum of two squares. To see this we need the following proposition: Proposition√2.4.1 For√any integers √ n and √ u, there are integers x and y not both 0 such that − n ≤ x ≤ n, − n ≤ y ≤ n and x − uy is divisible by n. √ √ Proof Let k √+ 1 =  n be the largest integer that is smaller than or equal to n, that is, k ≤ n < k + 1. Consider the numbers of the form x − uy with x and y in {0, 1, 2,... , k}. Each has k + 1 options, so there are (k + 1)2 > n possible numbers. Thus (by the pigeonhole principle!), there are two that leave the same remainder when divided by n. If they are x1 − uy1 and x2 − uy2 , their difference (x1 − x2 ) − u(y1 − y2 ) is divisible by n. If we take x = x1 − x2 and y = y1 − y2 , we have that they are not both 0, since the pairs (x1 , y1 ) and (x2 , y2 ) were different. Also, x and y are in the desired intervals.  With this we are ready to prove that every prime number of the form 4k + 1 is the sum of two squares. The only thing we need to know about these numbers is that for every prime p of the form 4k + 1 there is a u such that u2 + 1 is divisible by p. This last result can also be proven in a combinatorial way, counting how many pairs of numbers a, b in {0, 1, 2,... , p − 1} satisfy ab ≡ −1 (mod p) and how many pairs of different numbers a, b satisfy ab ≡ 1 (mod p). However, we will not do it in this book. Theorem 2.4.2 (Fermat) Every prime p of the form 4k + 1 can be written as the sum of two squares. Proof Let u be an integer such that u2 + 1 is divisible by p. Using Proposition 2.4.1 we know that there are integers x, y not both 0 such that x − uy is divisible by p √ √ √ √ and − p ≤ x ≤ p, − p ≤ y ≤ p. The condition can be translated to x 2 ≤ p and y 2 ≤ p. Since p is prime, it is not a perfect square, so the inequalities are strict. Since x ≡ uy (mod p), we have that x 2 ≡ u2 y 2 ≡ −y 2 (mod p), so x 2 + y 2 is divisible by p. However, 0 < x 2 + y 2 < 2p. With this we have that x 2 + y 2 = p.  2A rational number is one that can be written as the quotient of two integers. 24 2 The Pigeonhole Principle It is also known that a prime p of the form 4k + 1 can be written as the sum of two squares in a unique way, so this application of the pigeonhole principle finds the only pair that satisfies this. This shows that even though the technique seems elementary, it gives very precise results. 2.5 Problems Problem 2.1 Show that given 13 points in the plane with integer coordinates, there are three of them whose center of gravity has integer coordinates. Problem 2.2 Show that in a party there are always two persons who have shaken hands with the same number of persons. Problem 2.3 (OIM 1998) In a meeting there are representatives of n countries (n ≥ 2) sitting at a round table. It is known that for any two representatives of the same country their neighbors to their right cannot belong to the same country. Find the largest possible number of representatives in the meeting. Problem 2.4 (OMM 2003) There are n boys and n girls in a party. Each boy likes a girls and each girl likes b boys. Find all pairs (a, b) such that there must always be a boy and a girl that like each other. Problem 2.5 For each n show that there is a Fibonacci3 number that ends in at least n zeros. Problem 2.6 Show that given a subset of n + 1 elements of {1, 2, 3,... , 2n}, there are two elements in that subset such that one is divisible by the other. Problem 2.7 (Vietnam 2007) Given a regular 2007-gon, find the smallest positive integer k such that among any k vertices of the polygon there are 4 with the property that the convex quadrilateral they form shares 3 sides with the polygon. Problem 2.8 (Cono Sur Olympiad 2007) Consider a 2007 × 2007 board. Some squares of the board are painted. The board is called “charrúa” if no row is com- pletely painted and no column is completely painted. What is the maximum number k of painted squares in a charrúa board? For such k, find the number of different charrúa boards. Problem 2.9 Show that if 6 points are placed in the plane and they are joined with blue or green segments, then at least two monochromatic triangles are formed with vertices in the 6 points. 3 Fibonacci numbers are defined by the formulas (6.3) and (6.4). 2.5 Problems 25 Problem 2.10 (OMM 1998) The sides and diagonals of a regular octagon are col- ored black or red. Show that there are at least 7 monochromatic triangles with ver- tices in the vertices of the octagon. Problem 2.11 (IMO 1964) 17 people communicate by mail with each other. In all their letters they only discuss one of three possible topics. Each pair of persons discusses only one topic. Show that there are at least three persons that discussed only one topic. Problem 2.12 Show that if l, s are positive integers, then   l+s −2 r(l, s) ≤. l−1 Problem 2.13 Show that r(3, 4) = 9. Problem 2.14 Show that if an infinite number of points in the plane are joined with blue or green segments, there is always an infinite number of those points such that all the segments joining them are of only one color. Problem 2.15 (Peru 2009) In the congress, three disjoint committees of 100 con- gressmen each are formed. Every pair of congressmen may know each other or not. Show that there are two congressmen from different committees such that in the third committee there are 17 congressmen that know both of them or there are 17 congressmen that know neither of them. Problem 2.16 (IMO 1985) We are given 1985 positive integers such that none has a prime divisor greater than 23. Show that there are 4 of them whose product is the fourth power of an integer. Problem 2.17 (Russia 1972) Show that if we are given 50 segments in a line, then there are 8 of them which are pairwise disjoint or 8 of them with a common point. Problem 2.18 (IMO 1972) Show that given 10 positive integers of two digits each, there are two disjoint subsets A and B with the same sum of elements. Problem 2.19 There are two circles of length 420. On one 420 points are marked and on the other some arcs of circumference are painted red such that their total length adds up less than 1. Show that there is a way to place one of the circles on top of the other so that no marked point is on a colored arc. Problem 2.20 (Romania 2004) Let n ≥ 2 be an integer and X a set of n elements. Let A1 , A2 ,... , A101 be subsets of X such that the union of any 50 of them has more than 50n 51 elements. Show that there are three of the Aj ’s such that the intersection of any two is not empty. 26 2 The Pigeonhole Principle Problem 2.21 (Tournament of towns 1985) A class of 32 students is organized in 33 teams. Every team consists of three students and there are no identical teams. Show that there are two teams with exactly one common student. Problem 2.22 (Great Britain 2011) Let G be the set of points (x, y) in the plane such that x and y are integers in the range 1 ≤ x, y ≤ 2011. A subset S of G is said to be parallelogram-free if there is no proper parallelogram with all its vertices in S. Determine the largest possible size of a parallelogram-free subset of G. Note: A proper parallelogram is one whose vertices do not all lie on the same line. Problem 2.23 (Italy 2009) Let n be a positive integer. We say that k is n-square if for every coloring of the squares of a 2n × k board with n colors there are two rows and two columns such that the 4 intersections they make are of the same color. Find the minimum k that is n-square. Problem 2.24 (Romania 2009) Let n be a positive integer. A board of size N = n2 + 1 is divided into unit squares with N rows and N columns. The N 2 squares are colored with one of N colors in such a way that each color was used N times. Show that, regardless of the coloring, there is a row or a column with at least n + 1 different colors. Invariants 3 3.1 Definition and First Examples Example 3.1.1 There are three piles with n tokens each. In every step we are allowed to choose two piles, take one token from each of those two piles and add a token to the third pile. Using these moves, is it possible to end up having only one token? Solution To the tokens in the first pile we can assign the pair (0, 1), to the tokens in the second pile the pair (1, 0) and to the tokens in the third pile the pair (1, 1). Notice that the sum modulo 2 of any two of these pairs give us the third one. Thus, in every step the sum modulo 2 of all the assigned pairs is the same. However, the sum of all the assigned pairs in the beginning is (2n, 2n), which is equal to (0, 0) modulo 2. Since this pair was not assigned to any pile, it is not possible to end up with only one token.  In the previous example the strategy was to find a property that did not change in every step of the problem, and proving it could not be preserved in the end. When one deals with problems involving a transformation (such as taking off tokens in a certain way), a property that does not change under that transformation is called an invariant. Invariants can be extremely diverse, and there are numerous problems of international mathematical olympiads that can be solved by finding some very special invariant. When one is trying to solve olympiad problems (or any problem in mathematics), looking for invariants is a fundamental strategy. Example 3.1.2 Let n be a positive integer and consider the ordered list (1, 2, 3,... , n). In each step we are allowed to take two different numbers in the list and swap them. Is it possible to obtain the original list after exactly 2009 steps? Solution Suppose at some moment number 1 is in place a1 , number 2 is in place a2 , and so on. We are going to count the number T of pairs (x, y) such that x < y but ax > ay. In other words, we are counting the pairs of numbers that are not ordered. Suppose that in a step we swapped numbers a and b, and there were k numbers P. Soberón, Problem-Solving Methods in Combinatorics, 27 DOI 10.1007/978-3-0348-0597-1_3, © Springer Basel 2013 28 3 Invariants between them. If the pair (a, b) was counted in T , now it is not and vice-versa. The same happens to the k pairs formed by a and any of the numbers between a and b and the k pairs of b with any of those numbers. So there are exactly 2k + 1 pairs changing from being counted in T or not being counted in T. This means that T changes by an odd number. Thus, after 2009 steps T must be odd. Since T cannot be 0 after 2009 steps, we cannot get the original order.  These ideas are useful even in combinatorial geometry problems. Example 3.1.3 (IMO 2011) Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. A windmill is a process that starts with a line l going through a single point P ∈ S. The line rotates clockwise about the pivot P until the first time that the line meets some other point belonging to S. This point, Q, takes over as the new pivot, and the line now rotates clockwise about Q, until it meets a point of S. This process continues indefinitely. Show that we can choose a point P in S and a line l going through P such that the resulting windmill uses each point of S infinitely many times. Solution Consider the set of all lines that go through two points of S. Choose a direction l that is not parallel to any of those lines. Then, we can find a line l0 parallel to l that goes through a point P ∈ S and such that the absolute difference of the number of points on the two sides of l0 is at most 1. That is, the closest we can get to dividing the points of S in half subject to passing through a point of S. Consider one of the half-planes determined by a line as the red half-plane and the other as the blue half-plane. Start the windmill with l0 until it makes half of a complete turn. At this point consider its position l1. l1 is parallel to l0 , and the positions of the red and blue half-planes have changed. Note that the absolute difference between the number of points on the two sides of l1 is also at most 1. Thus there are no points of S between l0 and l1. This means that, other than the pivots of l0 and l1 , every point that was on the red half-plane is now on the blue half-plane and vice versa. Thus, the windmill used each point of S at least once. Since it will continue to use each point at least once per half turn, we are done. Figure showing l0 and l1 for a set of 16 points. If S has an odd number of points, then l0 = l1.  3.1 Definition and First Examples 29 In the previous example the invariant was the absolute difference of the number of points on the two sides of the line (when it is not passing through 2 points of S). Sometimes it is not easy to find a property that does not change, but finding one that always changes the same way can be equally useful. Example 3.1.4 23 friends want to play soccer. For this they choose a referee and the others split into two teams of 11 persons each. They want to do this so that the total weight of each team is the same. We know that they all have integer weights and that, regardless of who is the referee, it is possible to make the two teams. Prove that they all have the same weight. Solution Let a1 , a2 ,... , a23 denote the weights of the persons. Let S = a1 + a2 + · · · + a23. The condition tells us that if we remove the person with weight ai , the rest can be split into two teams of weight X. Thus S − ai = 2X. This tells us that ai and S have the same parity. Since this can be done for any ai , they are all even or all odd. We are going to generate another list b1 , b2 ,... , b23 of new weights that still satisfies the conditions of the problem. If the ai are even, we replace each one by bi = a2i. If they are odd, we replace each one by bi = ai − 1. It is clear that the new list of weights satisfies the conditions of the original prob- lem, and that bi ≥ 0 for all i. If the ai were not all 0, then the sum of the weights bi is strictly smaller. If we keep repeating this step we are always reducing the sum of the weights, so eventually we reach a list of only zeros. Since we are able to do this, we conclude the numbers in the original list were all equal.  In the previous example we exhibited a way to modify the problem so that the sum S was always decreasing. The reason why we can finish is because there is no infinite sequence of non-negative integers that is strictly decreasing. This technique is known as infinite descent. The question of what happens if the weights are not integers is also interesting. If all the friends have rational weights, multiplying all by some appropriate integer reduces the problem to the case with integer weights. If the weights are positive real numbers, then one needs to use linear algebra to reduce the problem to the rational case (simple approximation arguments do not work). Since this technique is beyond the purpose of this book, we will not show the details. However, the reader familiar with linear algebra should be able to deduce a solution with the previous comments. Let us see how we can apply infinite descent to a much more difficult problem. Example 3.1.5 (IMO 1986) We assign an integer to each vertex of a regular pen- tagon, so that the sum of all is positive. If three consecutive vertices have assigned numbers x, y, z, respectively, and y < 0, we are allowed to change the numbers (x, y, z) to (x + y, −y, z + y). This transformation is made as long as one of the numbers is negative. Decide if this process always comes to an end. 30 3 Invariants Solution Let the numbers in the pentagon be a, b, c, d, e, as shown in the figure. When one does the transformation, the sum of all numbers remains the same. Con- sider S(a, b, c, d, e) = (a − c)2 + (c − e)2 + (e − b)2 + (b − d)2 + (d − a)2. It is clear that S(a, b, c, d, e) ≥ 0. Suppose that c is negative and we do the change with c as the middle number. We have that S(a, b + c, −c, d + c, e) = (a + c)2 + (−c − e)2 + (e − b − c)2 + (b − d)2 + (d + c − a)2       = (a − c)2 + 4ac + (c − e)2 + 4ce + (e − b)2 − 2ec + 2bc + c2   + (b − d)2 + (d − a)2 − 2ac + 2cd + c2 = S(a, b, c, d, e) + 2c(a + b + c + d + e). Since c < 0 and we assumed that a + b + c + d + e > 0, we have that 2c(a + b + c + d + e) < 0. Therefore, S(a, b, c, d, e) is reduced after every transformation. By infi- nite descent, there must be a moment when we can no longer do the transformation, which is what we wanted to prove.  It should be noted that this problem was solved completely by a very small num- ber of students (as it should be expected for a Problem 3 at the IMO). The invariant S here might seem at first quite unnatural, but that is not the case. The first thing a student has to note is that the sum of all the numbers is constant and positive, and thus so is their average. This means that if every number was as close as possible to the average, then none would be negative. This makes it natural to search for func- tions that increase as the numbers are different from their average, or different from each other. Given two numbers x and y, (x − y)2 or |x − y| are good ways to see how different they are. If we start with (x − y)2 and try to apply it to 5 numbers, then the function S (or one of the same kind) arises naturally. Using absolute values it is also possible to obtain a function that behaves like S. It should be noted that this type of ideas are very useful even outside olympiad problems. n Given a set of number a1 , a2 ,... , an with average λ, the number μ2 = i=1 i(a − λ)2 is called the second moment of those numbers. This number and 3.2 Colorings 31 its generalizations are widely used in probability theory and its applications, but we leave further investigations to the interested reader. 3.2 Colorings Example 3.2.1 Is it possible to cover a 10 × 10 board with the following pieces without them overlapping? Note: The pieces can be flipped and turned. Solution Color the columns white and black alternatingly. There are 50 white squares and 50 black squares. We can see that, regardless of how we place a piece, it always covers three squares of one color and one of the other. Let us call the piece black if it covers three black squares and white if it covers three white squares. Then the number of black pieces is equal to the number of white pieces. This tells us that the total number of pieces must be even. This would mean that the number of squares should be divisible by 8. Since there are 100 squares, there is no possible cover.  In the previous example the key to see that we needed an even number of pieces was to color the columns. Coloring is a very neat technique in problems involving boards since it allows us to simplify the problem a great deal. The important part is focusing on an adequate subset of the squares (in the above example the subset consisted of the squares in even columns), however doing it with colors is a lot easier. The kinds of colorings can be very different. In the previous problem we used only two colors, but sometimes more are needed. There is no general rule for de- termining which one is going to solve the problem. There are some colorings (such as a chessboard coloring) that are frequently used, but the only way to learn how to use this technique is by solving several problems of this style. The problems in international contests that can be solved by coloring usually have the property that commonly used colorings do not give much information. They involve specific col- orings for that problem. When the problem is related to pieces covering a certain figure, the “good col- orings” are those that yield an invariant associated with the pieces. This can be the number of squares of one color they cover, the number of colors they may use, some parity argument, etc. Coloring is basically an illustrative way to describe in- variants. 32 3 Invariants Example 3.2.2 On a 9 × 9 board 65 insects are placed in the centers of some of the squares. The insects start moving at the same time and speed to a square that shares a side with the one they were in. When they reach the center of that square, they make a 90 degrees turn and keep walking (without leaving the board). Prove that at some moment of time there are two insects in the same square. Note: When they turn it can be either to the right or to the left. Solution Let us color the board using 4 colors A, B, C and D the following way: There are 25 A squares, 20 C squares, 20 B squares and 16 D squares. By the pigeonhole principle, there are at least 33 insect in colors A and D or 33 insects in colors B and C. In the second case, after one step there are at least 33 insect in squares A and D. Since the insects have to turn after every step, we know that every insect that was in an A square goes to a D square after two steps and vice-versa. By the pigeonhole principle there must be at least 17 insects in A squares or at least 17 insect in D squares. This tells us that at some moment there are at least 17 insects in D squares. Again, by the pigeonhole principle, there are two insects in the same square.  Example 3.2.3 (IMO shortlist 2002) A (2n − 1) × (2n − 1) board is going to be tiled with pieces of the type as shown in Fig. 3.1. Prove that at least 4n − 1 of the first type will be used. Solution Number the rows and columns from 1 to 2n − 1. Color in black the squares that are in an odd row and an odd column and color white the rest of the squares. There are n2 black squares and 3n2 − 4n + 1 white squares. The pieces of the first type can cover two white squares and one black square or three white squares. The rest of the pieces cover always three white squares and one black square. Let A be the number of pieces of the first kind that cover one black square, B the number of pieces of the first kind that cover no black squares and C the number of pieces of the other kinds. Fig. 3.1 Pieces for Example 3.2.3 3.3 Problems Involving Games 33 Counting the number of black squares we have that A + C = n2 and counting the white squares we have that 3n2 − 4n + 1 = 2A + 3B + 3C. So 4n − 1 = 3n2 − (3n2 − 4n + 1) = 3(A + C) − (2A + 3B + 3C) = A − B ≤ A + B. Thus there are at least 4n − 1 pieces of the first kind.  In the previous example a very special coloring was used. It is interesting to note that a chessboard coloring provides almost no information, and the coloring of the first example of the section only shows that at least 2n − 1 pieces of the first kind are necessary. Another difficulty of this problem is that finding a cover of an odd square board with this pieces is not easy. In fact, for n = 1, 2, 3 the number of squares needed by the pieces of the first kind is greater than the number of squares in the board, so no tiling is possible. In the following figure we show how to tile a 7 × 7 board (when n = 4). 3.3 Problems Involving Games Example 3.3.1 (OMCC 2001) A and B are going to play a game by turns. Before they start, they form a circle with 2001 other persons. At every turn they can remove one of their neighbors from the circle. The winner is the one who gets the other person out of the circle. If A starts, decide who has a winning strategy. Note: The other 2001 persons do not have turns. Solution When the game starts there are 2001 other persons. This means that A and B divide the circle in two arcs, one of which has an odd number of persons and the other an even number. The strategy for A is to remove always a person on the even side. This leaves B with an odd number of persons on each side. When B plays, A has again a side with an odd number of persons and an even number on the other, so he can continue with his strategy. B can never hope to win if A plays this way, since he always has at least one person between himself and A on both sides. Since the game must end after at most 2001 turns, A wins.  In problems involving games, finding a winning strategy means finding a way to play so that, regardless of how the other person plays, one is going to win. The key 34 3 Invariants to solve this kind of problems is to find an invariant in the game and exploit it. The invariant has to be a certain state of the game. We are looking for a state with the following properties: A person in that state cannot win the game. If the other person played in that state, we can force him back to that state. This kind of state is called a losing position. The positions that can send the other player to a losing position are called winning positions. In the previous example the losing position was having an odd number of persons on each side. In this type of problems, to find the losing positions it is convenient to look at the positions near the end of the game when one cannot win and work backwards in the game. It is also a good strategy to try a few games to look for the invariant. Example 3.3.2 On a chessboard A and B play by turns to place black and white knights, respectively. One loses if he places a knight on a square attacked by a knight of the other color or there are no free squares to place the knight on. If A starts, who has a winning strategy? A knight attacks the 8 squares shown in the following figure. Solution We will prove that B has a winning strategy. The strategy is to do the same thing as A but symmetrically to the center of the board. If B plays this way, A always plays on a board that is symmetric with respect to its the center. If A could place a knight without being attacked by B’s knights, this means that on the square symmetric with respect to the center B can place a knight without being attacked by A’s knights. Given the way knights attack, A can never place a knight that attacks the square where B would play. Thus A loses in the end.  Exercise 3.3.3 Solve the previous problem on a 9 × 9 chessboard. 3.3 Problems Involving Games 35 Example 3.3.4 There are 2010 matches on a table. A and B play by turns to remove matches from the table. At each turn, they must remove 1, 3, 4, 5 or 7 matches. Whoever removes the last match wins. If A plays first, who has a winning strategy? Solution Notice that the multiples of 8 are losing positions. If a player is in a multi- ple of 8, he cannot take all the matches. If he takes a matches, the other player can take 8 − a and bring him back to a multiple of 8. Since 2010 leaves remainder 2 when divided by 8, if the first player does not remove 4 matches, the other player can leave him in a multiple of 8. The same happens for the second player. If they both play only removing 4 matches each, B leaves 2 matches in his last turn, so B has the winning strategy.  Example 3.3.5 (Bulgaria 2001) A and B play by turns to write ones and zeros in a list, from left to right. The game ends when each has written 2001 numbers. When the game ends the sequence of numbers is seen as the expansion of a number in base 2. A wins if that number can be written as the sum of two perfect squares and B wins otherwise. Prove that B has a winning strategy. Solution We consider the following strategy for B: If at any moment A writes a 1, then B only copies A’s moves. The reason for this is that by following this strategy, we end up with a number with an even number of zeros at the end. We know that 4m can be written as the sum of two squares if and only if m can be written as the sum of two squares. Thus we can ignore the zeros at the end and suppose that the number finishes with 11, which means that the number is congruent to 3 modulo 4. From this, we infer that the number cannot be written as the sum of two squares. If A only writes 0, then B writes 1998 times 0 and then 3 times 1. This gives at the end the binary expansion of the number 21, which cannot be written as the sum of two squares.  The crucial step in this problem was to find a property with which a number could not be written as the sum of two squares. This was precisely being 3 modulo 4. Seeing how this property translates to the game gives the winning strategy if A plays a 1. In the other case, since we know how A is going to play it suffices to try a few cases. This kind of problems belong to of a branch of mathematics called game theory. In that branch you work with situations where one or more persons have to make some kind of decision to maximize a profit. This kind of situations are called games. In the games we have seen the profit was absolute, namely, it was “winning” the game. The objective of game theory is to find strategies to maximize such profit, and analyzing the situation when everyone plays with an optimal strategy (these situations are called equilibriums). Let us see another (very simple) example where the objective is no longer simply “winning” the game. Example 3.3.6 A pirate ship has 2009 treasure chests (all chests are closed). Each chest contains some amount of gold. To distribute the gold the pirates are going to 36 3 Invariants do the following. The captain is going to decide first how many chests he wants to keep and tell that number to the rest of the pirates. Then he is going to open all the chests and decide which ones he wants to keep (he can only choose as many as he said before opening them). The captain wants to make sure he can keep at least half of the total gold. However, he wants to say the smallest possible number to keep the rest of the pirates as happy as he can. What number should the captain say? Note: The chests may be empty. Solution Note that the chests could all contain the same amount of gold, so to keep at least of half of the gold the captain should keep at least half of the chests. With this in mind, the number he must say is at least 1005. Let us see that regardless of the gold distribution, 1005 of the chests are enough to keep half of the gold. To do this it is enough to open the chests and order them according to the amount of gold they have a1 ≥ a2 ≥ a3 ≥ · · · ≥ a2009. If the captain keeps the chests a1 , a2 ,... , a1005 then he has at least half of the gold.  The previous example becomes interesting if further complications are added. Example 3.3.7 A pirate ship has 2009 treasure chests (all chests are closed). Each chest contains some amount of gold and some amount of silver. To distribute the gold and silver the pirates are going to do the following. The captain is going to decide first how many chests he wants to keep and tell that number to the rest of the pirates. Then he is going to open all the chests and decide which ones he wants to keep. The captain wants to make sure he can keep at least half of the total gold and half of the total silver. However, he wants to say the smallest possible number to keep the rest of the pirates as happy as he can. What number should the captain say? Note: The amount of gold and silver in each chest may be different. Solution Since the captain wants to keep at least half of the gold, he needs again at least 1005 chests. It turns out that 1005 is also enough in this case. To see this, let us order again the chests according to their amount of gold a1 ≥ a2 ≥ · · · ≥ a2009. The choice of the captain is as follows. First he splits the chests into the following groups: {a1 }, {a2 , a3 }, {a4 , a5 },... , {a2008 , a2009 }. From each group he picks the one that has more silver. By doing this he guarantees he keeps half of the total amount of silver. However, in each group the chest he did not choose has at most the same amount of gold as the chest he chose from the previous group. Thus he also has at least half of the total amount of gold.  Game theory was created to abstract and solve problems in economics. However, due to the nature of the objects it studies, it has a wide number of applications. It is closely related to other fields of mathematics, such as probability. However, it also has applications to other subjects like political sciences, biology, philosophy and even military strategies. 3.4 Problems 37 3.4 Problems Problem 3.1 On an m × n board a path is a sequence of squares such that any two consecutive squares share one side. Show that on an m × n board there is a path that starts and ends in the same square and goes through every other square exactly once if and only if at least one of m, n is even and both are greater than or equal to two. Note: In this problem, if m = n = 1, we do not consider the single square as a valid path. Problem 3.2 On a table there are 2009 tokens which are red on one side and black on the other. A and B play by turns. In each turn it is permitted to remove any number of tokens from one color or flip any number of tokens of the same color. The one that removes the last token wins. If A plays first, who has a winning strategy? Problem 3.3 (OMCC 2003) A and B play with a set of 2003 coins by turns. In each turn it is permitted to remove a number of coins that is a divisor of the number of coins remaining. The one that removes the last coin loses. If A plays first, who has a winning strategy? Problem 3.4 (OIM shortlist 2009) On an 8×8 board there is a lamp in every square. Initially every lamp is turned off. In a move we choose a lamp and a direction (it can be the vertical direction or the horizontal one) and change the state of that lamp and all its neighbors in that direction. After a certain number of moves, there is exactly one lamp turned on. Find all the possible positions of that lamp. Problem 3.5 (OIM 2004) We are given a 1001 × 1001 board. We want to color some squares so that the following two conditions are met: If two squares share a side, at least one of them is colored. If 6 squares are consecutive (horizontally or vertically), then among them at least two consecutive squares are colored. Find the minimum number of squares that must be colored under these two rules. Problem 3.6 (Germany 2009) On a table there are 100 coins. A and B are going to remove coins from the table by turns. In each turn they can remove 2, 5 or 6 coins. The first one that cannot make a move loses. Determine who has a winning strategy if A plays first. Problem 3.7 (Middle European Mathematical Olympiad 2010) All positive divi- sors of a positive integer N are written on a blackboard. Two players A and B play the following game, taking alternate moves. In the first move, the player A erases N. If the last erased number is d, then the next player erases either a divisor of d or a multiple of d. The player who cannot make a move loses. Determine all numbers N for which A has a winning strategy. 38 3 Invariants Problem 3.8 In a 4×4 board the numbers from 1 to 15 are arranged in the following way: In a move we can move some number that is in a square sharing a side with the empty square to that square. Is it possible to reach the following position using these moves? Problem 3.9 (OIM 2000) On a table there are 2000 coins. A and B are going to play by turns to remove coins from the table. In each turn they may remove 1, 2, 3, 4 or 5 coins from the table but they cannot remove the same number as the other person removed in the previous turn. The one that removes the last coin wins. If A plays first, who has a winning strategy? Problem 3.10 (OMM 2003) In a box we have cards with all the pairs (a, b) with 1 ≤ a < b ≤ 2003 (no cards are repeated and all cards have only one pair). A and B are going to play by turns to remove cards from the box. At each turn, when they remove a card with the pair (a, b), they write on a blackboard the product ab of the numbers in the card. The first one to make the greatest common divisor of the numbers on the blackboard to be 1 loses. If A plays first, who has a winning strategy? Problem 3.11 (APMO 2007) In each square of a 5 × 5 board there is a lamp turned off. If we touch a lamp then that lamp and the ones in neighboring squares change their states. After a certain number of moves there is exactly one lamp turned on. Find all squares in which that lamp can be. Note: Neighboring squares are squares that share a side. 3.4 Problems 39 Problem 3.12 (Italy 2007) On a table there are cards with the numbers 0, 1, 2,... , 1024. A and B play by turns to remove cards from the table. First B removes 29 cards. Then A removes 28 cards. Then B removes 27 cards and so on until there are exactly 2 cards left with numbers a and b. A has to pay |a − b| dollars to B. What is the largest amount of money that B can guarantee he will win? Problem 3.13 (Japan 2011) Let N be a positive integer. N squares are lined up contiguously from left to right. Students A and B play a game according to the following rules: To start off, A will write one non-negative integer into each of the N squares. The game ends when the following condition is achieved: for every i satisfying 1 ≤ i ≤ N − 1, the number in the i-th square from the left is less than or equal to the number in the (i + 1)-th square from the left. The game continues as long as this condition is not achieved by repeating the fol- lowing procedure: (a) A designates one non-negative integer. (b) B chooses one of the N squares and replaces the number in that square by the number designated by A in (a). Is it possible for B to force the game to end regardless of how A plays? Problem 3.14 (USAMO 1994) We are given a regular 99-gon with sides painted in red, blue or yellow. Initially they are painted in the following way: red, blue, red, blue,... , red, blue, yellow. In a step we can change the color of any side as long as we do not generate two adjacent sides of the same color. Is it possible to reach a coloring red, blue, red, blue,... , red, yellow, blue after some finite number of steps? Note: The two colorings are considered in clockwise order. Problem 3.15 (Romania 2007) In an n × n board the squares are painted black or white. Three of the squares in the corners are white and one is black. Show that there is a 2 × 2 square with an odd number of white unit squares. Problem 3.16 (Argentina 2009) Consider an a × b board, with a and b integers greater than or equal to two. Initially all the squares are painted white and black as a chessboard. The allowed operation is to choose two unit squares that share one side and recolor them in the following way: Any white square is painted black, any black square is painted green and any green square is painted white. Determine for which values of a and b it is possible, using this operation several times, to get all the original black squares to be painted white and all the original white squares to be painted black. Note: Initially there are no green squares, but these appear after the first time we use the operation. 40 3 Invariants Problem 3.17 (Italy 2008) A and B are going to play by turns with piles of coins on a table (there are no piles with 0 coins). In each turn they can do one of the following moves: Choose a pile with an even number of coins and split it into two piles with the same number of coins each. Remove from the table all the piles with an odd number of coins. There has to be at least one odd pile to do this. In each turn, if one of these two moves is impossible, they have to perform the other. The first one that cannot make a valid move loses. If A plays first and initially there is only one pile with 20082008 coins, who has a winning strategy? What are the initial conditions under which A has a winning strategy? Problem 3.18 (Vietnam 1993) With the following shapes we tile a 1993 × 2000 board. Let s be the number of shapes used of the first two types. Find the largest possible value of s. Problem 3.19 We are given a 5 × 5 board with a chessboard coloring where the corners are black. In each black square there is a black token and in each white square there is a white token. The tokens can move to neighbor squares (squares that share a side with the one they are on). A and B are going to play by turns in the following way: First A chooses a black token and removes it from the board. Then, A moves a white token to the empty space. Then B moves a black token to the empty space. At each of his following turns, A moves a white token to the empty space and B moves a black token to the empty space. The game ends when one of them cannot make a valid move, and that person loses. Is there a winning strategy? If so, who has it? Problem 3.20 (OMM 1999) We say a polygon is orthogonal if all its angles are of 90 or 270 degrees. Show that an orthogonal polygon whose sides are all of odd integer length cannot be tiled with 2 × 1 domino tiles. Note: The polygons cannot have holes. (See Fig. 3.2.) Fig. 3.2 Example of an orthogonal polygon 3.4 Problems 41 Problem 3.21 (USAMO 1999) On a 1 × 2000 board, A and B play by turns to write S or O in each square. The first one to write the word SOS in three consecutive squares wins. If A plays first, show that B has a winning strategy. Problem 3.22 (IMO 2004) Find all pairs (m, n) such that an m × n board can be tiled with the following tile: Note: The tile can be rotated and flipped upside down. Problem 3.23 (IMO shortlist 1999) Show that if a 5 × n board can be tiled with pieces as in the following figure, then n is even. Show that the number of ways to tile a 5 × 2k board with these tiles is at least 2 · 3k−1. Graph Theory 4 4.1 Basic Concepts Graph theory is one of the most useful tools when solving combinatorics problems. It helps us reduce problems and handle concepts in a much simpler way. The main tricks and ideas were presented in the previous chapters. Even though our main purpose in this book is to solve olympiad problems, we need to emphasize that graph theory is a very large and beautiful field by itself. Graph theory is said to have started in 1736, with Euler. However, the first book on graph theory was published by König in the twentieth century (1936). Even though graph theory had an accelerated growth in that century, it is still possible find open problems1 that do not required a lot of theory to understand (and, in some cases, solve). This does not mean in any way that such problems are easy. A graph G is a pair (V , E), where V is a non-empty set and E is a multiset2 of unordered pairs of elements of V. The elements of V are called the vertices and the elements of E are called the edges of G. The reason why E is a multiset is to allow G to have an edge more than once; however, we will not deal with this kind of graphs. A subgraph G of G = (V , E) is a pair (V  , E  ), where V  is a subset of V , E  is a subset of E and (V  , E  ) is also a graph. Given a graph G, the set of vertices is usually denoted by v(G) and the (multi) set of edges is denoted by e(G).3 Each graph has a geometric representation. One places one point in the plane for each vertex, and a pair of points are joined with a line segment whenever the 1 An open problem is one that has not been solved yet. 2A multiset is a set than can have the same element more than once, for example {1, 1, 2, 3} is a multiset. 3 Ifthe set of vertices and the set of edges are empty, this still fits the definition of a graph, com- monly referred to as the empty graph. It is a technical detail and can normally be ignored, but it is a good thing to keep in the back of our minds when strange inductions or proofs are needed. P. Soberón, Problem-Solving Methods in Combinatorics, 43 DOI 10.1007/978-3-0348-0597-1_4, © Springer Basel 2013 44 4 Graph Theory corresponding vertices form an edge. Sometimes in the geometric representation edges have a common point, this does not mean that there is a new vertex there.4 The figure shows a graph with vertices v1 , v2 , v3 , v4 , v5 and edges {v1 , v2 }, {v1 , v4 }, {v1 , v5 }, {v1 , v5 }, {v2 , v2 }. Given a graph G, we say G is simple if there are no edges of only one vertex and there are no multiple edges. From now on, all graphs are simple unless specified otherwise. The term multigraph usually refers to graphs that are not simple. Given a graph G and its vertex v0 , we say that an edge A is incident in v0 if v0 is one of its vertices. We also say that two vertices v0 and v1 are adjacent if they form an edge. We say that v0 has degree k if it is adjacent to exactly k vertices, and then we write d(v0 ) = k. In the graph above d(A) = 2, d(B) = 3, d(C) = 2, d(D) = 1, d(E) = 0. Example n 4.1.1 Let G be a graph with vertex set V = {v1 , v2 ,... , vn }. Then k=1 d(vk ) = 2|E|. Solution Consider the pairs (v, e) such that e is an edge of G and v is a vertex of e. The vertex vi is in d(vi ) pairs, so the total number of pairs is nk=1 d(vk ). However, every edge is in 2 pairs, one for each of its vertices. So the total number of pairs is 2|E|, as claimed.  4 Ingraphs with an infinite number of vertices it may happen that the number of vertices is larger than the number of points in the plane. However, in these cases the geometric representation is clearly not important. 4.1 Basic Concepts 45 Exercise 4.1.2 Let G be a graph with an odd number of vertices. Show that there is at least one vertex with even degree. In a graph, a walk is a sequence of vertices (v0 , v1 , v2 ,... , vk ) such that vi is adjacent to vi+1 for all 1 ≤ i ≤ k − 1. In a walk, vertices may be re- peated. A path is a walk where no vertices are repeated. In the previous graph, (x1 , x2 , x3 , x5 , x6 , x7 , x5 , x4 ) is a walk, but not a path. However, (x1 , x2 , x3 , x5 , x4 ) is a path. We say that a walk is closed if the first and last vertices are the same. A cycle is a closed walk where the only two vertices that coincide are the first and the last. When we write (v0 , v1 ,... , vk = v0 ) we mean the closed walk (or cycle) that goes through the vertices v0 , v1 ,... , vk−1 and then returns to the vertex v0. In the previous graph, (x4 , x2 , x3 , x5 , x7 , x6 , x5 , x4 ) is a closed walk but not a cycle. However, (x4 , x2 , x3 , x4 ) is a cycle. Two cycles (walks, closed walks, paths) are said to be disjoint if they share no vertices. The length of a path is equal to the number of edges it has or, equivalently, the number of vertices it has minus one. The length of a cycle is equal to the number of edges it has or, equivalently, the number of vertices it has. Exercise 4.1.3 Let G be a graph and u, v two of its vertices. Prove that if there is a walk that starts in u and ends in v there must be a path that starts in u and ends in v. Exercise 4.1.4 Let G be a graph such that all its vertices have degree 2. Prove that G is a union of pairwise disjoint cycles. Exercise 4.1.5 Consider a graph G and v1 , v2 two of its vertices. We know that there are two walks from v1 to v2 , one of odd length and one of even length. Show that in G there is at least one cycle of odd length. Note: The walks may not be disjoint. Example 4.1.6 In a graph G every vertex has degree at least k ?