Mathematics via Problems: Part 3: Combinatorics 29

This book is a translation from Russian of Part III of the book Mathematics via Problems: From Olympiads and Math Circles to Profession. Part I, Algebra, and Part II, Geometry, have been published in the same series. The main goal of this book is to develop important parts of mathematics through problems. The authors tried to put together sequences of problems that allow high school students (and some undergraduates) with strong interest in mathematics to discover such topics in combinatorics as counting, graphs, constructions and invariants in combinatorics, games and algorithms, probabilistic aspects of combinatorics, and combinatorial geometry. Definitions and/or references for material that is not standard in the school curriculum are included. To help students that might be unfamiliar with new material, problems are carefully arranged to provide gradual introduction into each subject. Problems are often accompanied by hints and/or complete solutions. The book is based on classes taught by the authors at different times at the Independent University of Moscow, at a number of Moscow schools and math circles, and at various summer schools. It can be used by high school students and undergraduates, their teachers, and organizers of summer camps and math circles. In the interest of fostering a greater awareness and appreciation of mathematics and its connections to other disciplines and everyday life, SLMath (formerly MSRI) and the AMS are publishing books in the Mathematical Circles Library series as a service to young people, their parents and teachers, and the mathematics profession. Cover 1 Title page 4 Contents 6 Foreword 10 Problems, exercises, circles, and olympiads 10 Why this book and how to use it 11 English-language references 12 Introduction 14 What this book is about and whom it is for 14 Learning by doing problems 15 Parting words By A.Ya.Kanel–Belov 16 Olympiads and mathematics 16 Research problems for high school students 17 How this book is organized 17 Resources and literature 18 Acknowledgements 18 Numbering and notation 19 Notation 19 Bibliography 22 Chapter 1. Counting 24 1. How many ways? (1) By A.A.Gavrilyuk and D.A.Permyakov 24 Suggestions, solutions, and answers 25 2. Sets of subsets (2) By D.A.Permyakov 26 Suggestions, solutions, and answers 27 3. The principle of inclusion-exclusion (2) By D.A.Permyakov 29 Suggestions, solutions, and answers 32 Chapter 2. Finite sets 36 1. The pigeonhole principle (1) By A.Ya.Kanel-Belov 36 Part 1 36 Part 2 (2) 37 Suggestions, solutions, and answers 38 2. The extremal principle (2) By A.Ya.Kanel-Belov 39 Suggestions, solutions, and answers 40 3. Periodicity I (2) By A.Ya.Kanel-Belov 41 Suggestions, solutions, and answers 43 4. Periodicity II (2) By P.A.Kozhevnikov 43 Suggestions, solutions, and answers 44 5. Finite and countable sets (2) By P.A.Kozhevnikov 45 Suggestions, solutions, and answers 46 Comments about the solutions of problems 2.5.1 and 2.5.2 49 Chapter 3. Graphs By D.A.Permyakov and A.B.Skopenkov 52 1. Graphs (2) 52 Suggestions, solutions, and answers 54 2. Counting in graphs (2) 57 Suggestions, solutions, and answers 58 3. Paths in graphs (2) 59 Suggestions, solutions, and answers 60 Chapter 4. Constructions and invariants 62 1. Constructions (1) By A.V.Shapovalov 62 Suggestions, solutions, and answers 66 2. Invariants I (1) By A.Ya.Kanel-Belov 73 Suggestions, solutions, and answers 75 3. Invariants II (1) By A.V.Shapovalov 76 Suggestions, solutions, and answers 80 4. Colorings 83 4.A. Tilings (1) By A.Ya.Kanel-Belov 83 4.B. Tables (2) By D.A.Permyakov 84 Suggestions, solutions, and answers 85 5. Semi-invariants (1) By A.V.Shapovalov 85 Suggestions, solutions, and answers 89 Chapter 5. Algorithms 94 1. Games (1) By D. A.Permyakov, M. B.Skopenkov, and A.V.Shapovalov 94 Symmetric strategy 94 Game on outracing 95 Accumulation of advantages 95 Joke games 96 Growing a tree of positions 97 Passing the move 97 Miscellany 98 Suggestions, solutions, and answers 99 2. Information problems (2) By A.Ya.Kanel-Belov 104 Suggestions, solutions, and answers 106 3. Error correction codes (2) By M.B.Skopenkov 107 Suggestions, solutions, and answers 108 4. Boolean cube (2) By A.B.Skopenkov 109 Hints 111 Suggestions, solutions, and answers 111 5. Expressibility for functions of the algebra of logic By A.B.Skopenkov 113 Examples and definitions (1) 113 Post’s theorem (2*) 114 Hints 117 Suggestions, solutions, and answers 117 6. Complexity of summation By Yu.G.Kydryashov and A.B.Skopenkov 117 Introductory problems (2) 117 Definitions and examples (3*) 118 Asymptotic estimates (4*) 120 Suggestions, solutions, and answers 120 Chapter 6. Probability By A.B.Skopenkov and A.A.Zaslavsky 126 1. Classical definition of probability (1) 126 Suggestions, solutions, and answers 128 2. A more general definition of probability (1) 128 Suggestions, solutions, and answers 130 3. Independence and conditional probability (1) 131 Suggestions, solutions, and answers 134 4. Random variables (3) 135 Suggestions, solutions, and answers 138 5. Bernoulli trials (3) 140 Suggestions, solutions, and answers 142 6. Random walks and electrical circuits (3) By A.A.Zaslavsky, M.B.Skopenkov, and A.V.Ustinov 142 Biased random walk* 144 Physical interpretation 144 Existence and uniqueness of voltage 147 Conductance of circuits 148 The variational principle 150 Two-dimensional random walk 150 Three-dimensional random walks 151 Suggestions, solutions, and answers 152 Chapter 7. Combinatorial geometry 162 1. Rug runners and napkins (2) By P.A.Kozhevnikov 162 One-dimensional geometry, or \enquote{rug runners} 162 Two-dimensional geometry, or \enquote{napkins on the table} 163 Three dimensions 164 Suggestions, solutions, and answers 164 2. Helly’s theorem (2) By A.V.Akopyan 167 Suggestions, solutions, and answers 169 3. Lattice polygons (2) By V.V.Prasolov and M.B.Skopenkov 169 3.A. Area of a polygon on grid paper (2) 170 3.B. Dual lattice polygons (3*) 172 Suggestions, solutions, and answers 174 4. Pigeonhole principle on a line (3) By A.Ya.Kanel-Belov 183 Suggestions, solutions, and answers 184 5. The pigeonhole principle and its application to geometry (3) By I.V.Arzhantsev 184 The area of a figure 184 The pigeonhole principle for areas 185 The theorems of Blichfeldt and Minkowski 186 Dirichlet’s theorem on approximation of irrational numbers 188 Suggestions, solutions, and answers 189 6. Phase spaces (3) By A.Ya.Kanel-Belov 190 7. Linear variation (3) By A.Ya.Kanel-Belov 191 Suggestions, solutions, and answers 193 8. Compose a square (3*) By M.B.Skopenkov, O.A.Malinovskaya, S.A.Dorichenko, and F.A.Sharov 193 Leading questions 194 Rectangles from squares. 196 From cutting to roots of polynomials 198 What’s next 198 Suggestions, solutions, and answers 199 9. Is it possible to make a cube from a tetrahedron? (3) By M.V.Prasolov and M.B.Skopenkov 206 Reduction to a plane geometry problem 206 Solution of the plane geometry problem 208 Suggestions, solutions, and answers 209 Bibliography 214 Index 218 Back Cover 222