# Solving an IMO problem Using Graph Theory

Here is a question from IMO 2021:

Let $$n>100$$ be an integer. Ivan writes the numbers $$n,n+ 1,\dots,2n$$ each on different cards. He then shuffles these $$n+ 1$$ cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square.

Algorithm:

1. First find those duplets whose addition will lead to perfect squares.

2. Next try to form a bipartite graph from those duplets.

Proof to show: A bipartite graph is not possible.

Am I going correctly? Basically, I want to solve this using graph theory. It will be very helpful for me if I get some insight on how to approach this more accurately.

• Basically yes, if you fixate a $n$ and build the graph and check for bipartiteness (e.g. via DFS), and it is not bipartite, then you showed that for the choice of $n$ the theorem holds. The tricky thing is then to generalize it, and prove it for every possible $n$. If you can prove that DFS will always find an odd cycle for instance (for a general $n$), then you are done. (Notice, I don't know if such a approach will work or not) Jul 26 at 17:46