0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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) $\endgroup$
    – Jakube
    Jul 26 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.