Cayley 2019 Q5
5. Howard chooses \(n\) different numbers from the list 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, so that no two of his choices add up to a square.
What is the largest possible value of \(n\)?
Cayley Olympiad 2019, Question 5. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: 7
When compiling the list of pairs which add up to a square, we can either work through the list (what numbers pair with 2?, what pairs with 3?, . . . ), or note that we are looking for squares between \(2 + 3\) and \(10 + 11\), that is, 9 and 16.
When considering which numbers Howard should choose, we have to avoid the following pairs of numbers since their sum is a square: 2 and 7, 3 and 6, 4 and 5, 5 and 11, 6 and 10, and 7 and 9.
By considering, for example, the first three pairings, no two of which have a number in common, we see that there is no group of numbers with less than three members with the property that one of the numbers in the group is contained in each of the above six pairings.
However, each of the above six pairings contains one of the three numbers 5, 6 or 7.
Not choosing 5, 6 and 7 means that one of the numbers from all six pairings has been left out, so each pairing will not be included.
So, for the largest possible list, Howard should choose 2, 3, 4, 8, 9, 10 and 11.
Thus the smallest number of individual numbers that need to be avoided so that none of these pairings is present is three.
Hence the largest possible value of \(n\) is seven.
Solution © UK Mathematics Trust, from the Cayley Olympiad 2019 solutions.