A Graph Theory Olympiad Question Whose Answer is 1015056

April’s Math Olympiad Question was a particularly tough one, only four people in the world solved it! One from Japan, one from Slovakia, one from Ankara, and one from Singapore!

The question starts off seemingly simple enough:

In a party attended by 2015 guests among any 7 guests at most 12 handshakes had been
exchanged. Determine the maximal possible total number of handshakes.

However, when one starts trying out the questions, one quickly realizes the number of handshakes is very large, possibly even up to millions. This question definitely can’t be solved by trial and error!

This question is ideally modeled by a graph, and has connections to the idea of a Turán graph.

The official solution can be accessed here: http://www.fen.bilkent.edu.tr/~cvmath/Problem/1504a.pdf

 

Turan 13-4.svg
The Turán graph T(13,4)

 

To read more about Math Olympiad books, you may check out my earlier post on Recommended Math Olympiad books for self-learning.

Number Theory Notes – Art of Problem Solving

Source: http://www.artofproblemsolving.com/Resources/Papers/SatoNT.pdf

Excellent notes on Olympiad Number Theory!

Preface:

This set of notes on number theory was originally written in 1995 for students

at the IMO level. It covers the basic background material that an IMO

student should be familiar with. This text is meant to be a reference, and

not a replacement but rather a supplement to a number theory textbook;

several are given at the back. Proofs are given when appropriate, or when

they illustrate some insight or important idea. The problems are culled from

various sources, many from actual contests and olympiads, and in general

are very difficult. The author welcomes any corrections or suggestions.