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.

Advertisements

About mathtuition88

http://mathtuition88.com
This entry was posted in graph theory, math olympiad and tagged , . Bookmark the permalink.

3 Responses to A Graph Theory Olympiad Question Whose Answer is 1015056

  1. abyssbrain says:

    I’m glad that my solution was correct lol. That problem was quite hard for an olympiad level question IMO.

    Liked by 2 people

  2. Reblogged this on Problemas e Teoremas and commented:
    Pela blogosfera: uma questão difícil das Olimpíadas de Matemática

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s