## July 2021

—————————

In the Math Corner of my June Diary I included the following brainteaser, borrowed from the 2021 International Math Olympiad, which was held in (well, supervised from) St. Petersburg, Russia.

**IMO 2021 Problem 1**.

Letn≥ 100 be an integer. Ivan writes the numbersn,n+ 1, …, 2neach on different cards. He then shuffles thesen+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.

The nifty thing about borrowing a brainteaser from the IMO is that within a day or two of final results being announced, worked
solutions to the problems pop up all over the internet. Some of them are wrong: either they have misunderstood the question (I saw a couple that
assumed the two piles must be of *equal* size, which isn't possible if *n* is even), or they have mistakes in their reasoning. The
ones that are sound, though, offer a mighty temptation to the borrower to just link to them.

Have I yielded to that temptation? Yes, I have; but I beg to offer some qualifications.

- Before looking on the internet for solutions, I put in an honest hour or so of effort into tackling the problem, without getting
very close. If I were marking my own effort, I'd have given it a 2 out of 7.
- I'll give you a link to a good worked solution, but I'll follow the link with some (I hope) clarifying remarks.

—————————

**• Solution**

Here is a good worked solution. It includes some helpful video links.

The key insight is there in the opening sentence.

If we can guarantee that there exist three cards such that every pair of them sum to a perfect square, then we can guarantee that one of the piles contains two cards that sum to a perfect square.

Just pause to convince yourself of that. For *any* three distinct numbers *a*, *b*, and *c*, logic demands that
*either* one of the two piles contains all three of them while the other contains none, *or* one pile contains two of them, the other
pile only one. So one or other of the piles must contain two (at least) of them.

In the special case for which every pair-sum *b*+*c*, *c*+*a*, and *a*+*b* is a perfect square,
the conditions of the problem are met.

So when *are* there three such numbers in the range from *n* to 2*n* inclusive?

That worked solution crunches through the algebra. Bottom line:

Calculateu_{min}= √(1 +n/2) + 1,u_{max}= √(1 +n) − 1. If there is a positive whole numberein the range fromu_{min}tou_{max}inclusive — that is, greater than or equal tou_{min}while less than or equal tou_{max}— thena= 2e² + 1,b= 2e(e− 2),c= 2e(e+ 2), satisfy the required condition.

For what values of *n* does such a number *e* exist? Let's try a few.

When *n* = 10, *u*_{min} = 3.449 … and *u*_{max} =
2.316 … Here *u*_{min} is bigger than *u*_{max}, so no number satisfies the condition for *e*.
Sure enough, there are no three numbers in {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} whose pairwise sums are all perfect squares.

If you plough upwards from *n* = 10, *u*_{max} does eventually overtake *u*_{min}, with real
hope of there being a whole number *e* between them (inclusive). At *n* = 48, *u*_{min} and
*u*_{max} are both precisely equal to 6, so *e* = 6 gives a solution *a* = 73, *b* = 48,
*c* = 96. The pairwise sums are 144, 169, and 121, all perfect squares.

Proceeding on upwards, however, for *n* = 49, *u*_{min} = 6.0497 … and
*u*_{max} = 6.0710. There is no whole number *e* in that range; and this dry spell continues until
*n* = 63, which yields *u*_{min} = 6.7008 … and *u*_{max} = 7, whence
*e* = 7, giving *a* = 99, *b* = 70, and *c* = 126. The pairwise sums are 196, 225, and 169,
all perfect squares.

From *n* = 99 onwards there are no more dry spells (so that *n* ≥ 100 in the problem statement could
be replaced by *n* ≥ 99).

As *n* increases, in fact, you get into zones where there is *more than one* solution for *e*, and so more than one
triplet (*a*, *b*, *c*) available as solutions. When *n* is 198, for example, *u*_{min} =
11, *u*_{max} = 13.1067, so *e* can be 11, 12, or 13, giving (*a*, *b*, *c*) triplets (243,
198, 286), (289, 240, 336), and (339, 286, 390).