An Exploration of Olympiad Combinatorics

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.