Mathematics Via Problems: Part 3: Combinatorics

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 Title page Contents Foreword Problems, exercises, circles, and olympiads Why this book and how to use it English-language references Introduction What this book is about and whom it is for Learning by doing problems Parting words By A.Ya.Kanel–Belov Olympiads and mathematics Research problems for high school students How this book is organized Resources and literature Acknowledgements Numbering and notation Notation Bibliography Chapter 1. Counting 1. How many ways? (1) By A.A.Gavrilyuk and D.A.Permyakov Suggestions, solutions, and answers 2. Sets of subsets (2) By D.A.Permyakov Suggestions, solutions, and answers 3. The principle of inclusion-exclusion (2) By D.A.Permyakov Suggestions, solutions, and answers Chapter 2. Finite sets 1. The pigeonhole principle (1) By A.Ya.Kanel-Belov Part 1 Part 2 (2) Suggestions, solutions, and answers 2. The extremal principle (2) By A.Ya.Kanel-Belov Suggestions, solutions, and answers 3. Periodicity I (2) By A.Ya.Kanel-Belov Suggestions, solutions, and answers 4. Periodicity II (2) By P.A.Kozhevnikov Suggestions, solutions, and answers 5. Finite and countable sets (2) By P.A.Kozhevnikov Suggestions, solutions, and answers Comments about the solutions of problems 2.5.1 and 2.5.2 Chapter 3. Graphs By D.A.Permyakov and A.B.Skopenkov 1. Graphs (2) Suggestions, solutions, and answers 2. Counting in graphs (2) Suggestions, solutions, and answers 3. Paths in graphs (2) Suggestions, solutions, and answers Chapter 4. Constructions and invariants 1. Constructions (1) By A.V.Shapovalov Suggestions, solutions, and answers 2. Invariants I (1) By A.Ya.Kanel-Belov Suggestions, solutions, and answers 3. Invariants II (1) By A.V.Shapovalov Suggestions, solutions, and answers 4. Colorings 4.A. Tilings (1) By A.Ya.Kanel-Belov 4.B. Tables (2) By D.A.Permyakov Suggestions, solutions, and answers 5. Semi-invariants (1) By A.V.Shapovalov Suggestions, solutions, and answers Chapter 5. Algorithms 1. Games (1) By D. A.Permyakov, M. B.Skopenkov, and A.V.Shapovalov Symmetric strategy Game on outracing Accumulation of advantages Joke games Growing a tree of positions Passing the move Miscellany Suggestions, solutions, and answers 2. Information problems (2) By A.Ya.Kanel-Belov Suggestions, solutions, and answers 3. Error correction codes (2) By M.B.Skopenkov Suggestions, solutions, and answers 4. Boolean cube (2) By A.B.Skopenkov Hints Suggestions, solutions, and answers 5. Expressibility for functions of the algebra of logic By A.B.Skopenkov Examples and definitions (1) Post’s theorem (2*) Hints Suggestions, solutions, and answers 6. Complexity of summation By Yu.G.Kydryashov and A.B.Skopenkov Introductory problems (2) Definitions and examples (3*) Asymptotic estimates (4*) Suggestions, solutions, and answers Chapter 6. Probability By A.B.Skopenkov and A.A.Zaslavsky 1. Classical definition of probability (1) Suggestions, solutions, and answers 2. A more general definition of probability (1) Suggestions, solutions, and answers 3. Independence and conditional probability (1) Suggestions, solutions, and answers 4. Random variables (3) Suggestions, solutions, and answers 5. Bernoulli trials (3) Suggestions, solutions, and answers 6. Random walks and electrical circuits (3) By A.A.Zaslavsky, M.B.Skopenkov, and A.V.Ustinov Biased random walk* Physical interpretation Existence and uniqueness of voltage Conductance of circuits The variational principle Two-dimensional random walk Three-dimensional random walks Suggestions, solutions, and answers Chapter 7. Combinatorial geometry 1. Rug runners and napkins (2) By P.A.Kozhevnikov One-dimensional geometry, or \enquote{rug runners} Two-dimensional geometry, or \enquote{napkins on the table} Three dimensions Suggestions, solutions, and answers 2. Helly’s theorem (2) By A.V.Akopyan Suggestions, solutions, and answers 3. Lattice polygons (2) By V.V.Prasolov and M.B.Skopenkov 3.A. Area of a polygon on grid paper (2) 3.B. Dual lattice polygons (3*) Suggestions, solutions, and answers 4. Pigeonhole principle on a line (3) By A.Ya.Kanel-Belov Suggestions, solutions, and answers 5. The pigeonhole principle and its application to geometry (3) By I.V.Arzhantsev The area of a figure The pigeonhole principle for areas The theorems of Blichfeldt and Minkowski Dirichlet’s theorem on approximation of irrational numbers Suggestions, solutions, and answers 6. Phase spaces (3) By A.Ya.Kanel-Belov 7. Linear variation (3) By A.Ya.Kanel-Belov Suggestions, solutions, and answers 8. Compose a square (3*) By M.B.Skopenkov, O.A.Malinovskaya, S.A.Dorichenko, and F.A.Sharov Leading questions Rectangles from squares. From cutting to roots of polynomials What’s next Suggestions, solutions, and answers 9. Is it possible to make a cube from a tetrahedron? (3) By M.V.Prasolov and M.B.Skopenkov Reduction to a plane geometry problem Solution of the plane geometry problem Suggestions, solutions, and answers Bibliography Index Back Cover