MathLabs

Problem 1

Let n≥100n \ge 100 be an integer. Ivan writes the numbers n,n+1,…,2nn, n+1, \ldots, 2n each on a different card. He then shuffles these n+1n+1 cards and divides them into two piles. Prove that at least one of the piles contains two cards whose numbers sum to a perfect square.
Step 5 of 5: Apply the pigeonhole principle to the two piles
Previous stepNext step
{a,b,c}⊂{n,n+1,…,2n}\{a,b,c\}\subset\{n,n+1,\ldots,2n\}
Detailed analysis

For every n≥100n\ge100 we now have a,b,c∈{n,n+1,…,2n}a,b,c\in\{n,n+1,\ldots,2n\} with a+ba+b, b+cb+c, c+ac+a all perfect squares. When these three cards are split between two piles, two of them must land in the same pile by the pigeonhole principle, and their sum is already one of (2k−1)2,(2k)2,(2k+1)2(2k-1)^2,(2k)^2,(2k+1)^2, completing the proof.