Mathematics via Problems: Part 3: Combinatorics

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