Maths Olympiad Prep

Library / /11 of 27

Number theory Difficulty 5.6 AIME, harder Prove it Brazil

Emerald wrote a list of positive integers. Renan noticed that each number in the list and any sum of any quantity of distinct numbers from the list were square-free (that is, not divisible by any perfect square except, of course, 1). What is the maximum quantity of numbers that Emerald's list can have?

Solution

The smallest perfect square, apart from 11, is 22=42^2 = 4. So let a1,a2,,aka_1, a_2, \dots, a_k be the numbers on the list modulo 44. We cannot have ai=0a_i = 0; also, there is at most one aia_i equal to 22 and we cannot have ai=1a_i = 1 and aj=3a_j = 3 simultaneously.

We claim that among any four distinct numbers a1,a2,a3,a4a_1, a_2, a_3, a_4 fulfilling the above properties there are three of them whose sum is a multiple of 44. Indeed, there are two equal numbers, say a1,a2a_1, a_2. We cannot have a1=a2=2a_1 = a_2 = 2, so either a1=a2=1a_1 = a_2 = 1 or a1=a2=3a_1 = a_2 = 3. We can suppose wlog a1=a2=1a_1 = a_2 = 1 (otherwise, reverse the signs of all four numbers modulo 44). But since we also cannot have aj=3a_j = 3 and a3=a4=1a_3 = a_4 = 1, one of a3,a4a_3, a_4, say a3a_3, is 22. But then a1+a2+a3=1+1+2=4a_1 + a_2 + a_3 = 1 + 1 + 2 = 4.

So the quantity of numbers is at most 33. 55, 1313 and 1717 is an example of a list with three numbers.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.