Olympiad Combinatorics

---

Olympiad 
Combinatorics
Pranav A. Sriram 
August 2014

---

Chapter 1: Algorithms 
1 
Copyright notices 
All USAMO and USA Team Selection Test problems in this chapter are 
copyrighted by the Mathematical Association of America’s American 
Mathematics Competitions. 
 
© Pranav A. Sriram. This document is copyrighted by Pranav A. Sriram, 
and may not be reproduced in whole or part without express written 
consent from the author.
 
About the Author 
 
Pranav Sriram graduated from high school at The International 
School Bangalore, India, and will be a Freshman at Stanford 
University this Fall.

---

 
 
 

---

Chapter 1: Algorithms 
1 
 
 
 
 
 
 
 
 
1.
 
A
LGORITHMS
 
 
Introduction 
Put simply, an algorithm is a procedure or set of rules designed to 
accomplish some task. Mathematical algorithms are indispensable 
tools, and assist in financial risk minimization, traffic flow 
optimization, flight scheduling, automatic facial recognition, 
Google search, and several other services that impact our daily 
lives.
Often, an algorithm can give us a deeper understanding of 
mathematics itself. For instance, the famous Euclidean algorithm 
essentially lays the foundation for the field of number theory. In 
this chapter, we will focus on using algorithms to prove 
combinatorial results. We can often prove the existence of an 
object (say, a graph with certain properties or a family of sets 
satisfying certain conditions) by giving a procedure to explicitly 
construct it. These proofs are hence known as constructive proofs. 
Our main goals in this chapter will be to study techniques for 
designing algorithms for constructive proofs, and proving that 
they actually work.

---

Olympiad Combinatorics 
2 
In this chapter, and throughout the book, the emphasis will be 
on ideas. What can we observe while solving a given problem? 
How can disparate ideas and observations be pieced together 
cohesively to motivate a solution? What can we learn from the 
solution of one problem, and how may we apply it to others in the 
future? Each problem in this book is intended to teach some 
lesson - this may be a combinatorial trick or a new way of looking 
at problems. We suggest that you keep a log of new ideas and 
insights into combinatorial structures and problems that you 
encounter or come up with yourself.