An Exploration of Olympiad Combinatorics
"An Exploration of Olympiad Combinatorics" is a book authored by me and published by Bhaskaracharya Pratishthana with the purpose of helping readers prepare for national and international mathematical olympiads. The book covers a wide range of combinatorial topics, progressing from fundamentals like counting principles and induction to advanced fields including algorithms, graph theory, and the probabilistic method.
The book is written in a unique conversational style and breaks away from the traditional problem-solution format. This approach aims to engage the reader and encourage them to find solutions independently and develop problem-solving skills.
The book also includes a large collection of practice problems, over 600 hints for these problems to guide readers when they encounter difficulties, and illustrations to enhance comprehension of the text.
You can purchase the book by ordering it on the Amazon link shared above or by contacting Bhaskaracharya Pratisthana as described here.
Details about the Book
The primary target audience of the book is students from grades 8 to 12 who are interested in preparing for the mathematical olympiads. However, the book is a useful read to anyone wishing to understand and learn more about combinatorics. In particular, students preparing for informatics olympiads should also find some sections of the book useful.
The first three chapters of the book are to build the fundamentals of the reader.
An introduction to problem solving familiarises the reader with the structure of the book. It also provides you with some fun problems to challenge yourself with.
Introduction to counting serves to familiarise you with concepts of permutations and combinations and how they relate to each other as well as other useful counting techniques.
Induction and Recurrence Relations aims to help the reader learn the powerful method of Mathematical Induction and also understand how we can use recurrences to solve various olympiad problems.
The next seven chapters cover most of the important theory relevant to combinatorics in math olympiads.
Invariants and Monovariants serves to introduce the reader to a powerful method useful to understand processes associated with several combinatorics problems.
Combinatorial Games is a fun chapter that describes how we can show the existence of and find winning strategies in various games.
The pigeon-hole principle, also known as the Box Principle: this chapter revolves around how we can show the existence of certain events using a simple yet powerful technique.
Soft techniques is one of the key chapters of this book and is one that is often neglected. It uses examples to allow the reader to understand how they should approach problems and use techniques such as analysing base cases to get a firm hold on the problem conditions.
Algorithms: In this chapter, we work towards finding ways to use given tools to achieve a certain end goal. A brief introduction has also been given to the efficiency of an algorithm. It has been linked to the informatics olympiads as well.
Greedy Algorithms and the Extremal Principle: This chapter deals with a specific type of algorithms where we try to maximise short term outcomes while nignoring the overall impact. It has also been connected to the extremal principle and how both approaches can be used to solve problems.
Counting in two ways: This chapter deals with a way to find relations in certain quantities indirectly by trying to count the number of possibilities for a certain object in two different ways.
Next, the book explores Graph Theory with the following chapters:
Graph Theory I: This chapter introduces the topic of Graph Theory with relevant terminology. It also introduces the concept of trees and cycles and shows how these concepts can be applied to a wide range of olympiad problems.
Graph Theory II: This covers several other graph theory concepts such as bipartite graphs, chromatic numbers, cliques and independent sets, Hamiltonian paths and cycles, and tournaments.
Hall’s theorem introduces the concept of matchings in bipartite graphs, and how the existence of such matchings can be determined. Several example problems show how this theorem can be applied to a wide range of seemingly disconnected olympiad problems.
The last three chapters consist of slightly more advanced topics, with:
Processes: This chapter deals with understanding and working with problems where a certain process needs to be analysed. It also introduces an interesting technique known as the technique of “superposition”.
Expected Value: This chapter introduces probability and expected value and shows us several methods to evaluate such quantities.
The Probabilistic Method: This final chapter deals with how we can use probability and expected value to solve a wide range of olympiad problems in non-standard ways.