»  Solutions to puzzles in my VDARE.com monthly Diary

  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.

Let n ≥ 100 be an integer. Ivan writes the numbers n, n + 1, …, 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.

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.

  1. 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.

  2. 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 2n inclusive?

That worked solution crunches through the algebra. Bottom line:

Calculate  umin = √(1 + n/2) + 1,  umax = √(1 + n) − 1.  If there is a positive whole number e in the range from umin to umax inclusive — that is, greater than or equal to umin while less than or equal to umax — then a = 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, umin = 3.449 … and umax = 2.316 …  Here umin is bigger than umax, 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, umax does eventually overtake umin, with real hope of there being a whole number e between them (inclusive). At n = 48,  umin and umax 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, umin = 6.0497 … and umax = 6.0710. There is no whole number e in that range; and this dry spell continues until n = 63, which yields umin = 6.7008 … and umax = 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 (abc) available as solutions. When n is 198, for example, umin = 11, umax = 13.1067, so e can be 11, 12, or 13, giving (abc) triplets (243, 198, 286), (289, 240, 336), and (339, 286, 390).