Brazilian Math Olympiad

Question

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?

Accepted Answer

The smallest perfect square, apart from

1

, is

2^{2} = 4

. So let

a_{1}, a_{2}, \dots, a_{k}

be the numbers on the list modulo

4

. We cannot have

a_{i} = 0

; also, there is at most one

a_{i}

equal to

2

and we cannot have

a_{i} = 1

and

a_{j} = 3

simultaneously.

We claim that among any four distinct numbers

a_{1}, a_{2}, a_{3}, a_{4}

fulfilling the above properties there are three of them whose sum is a multiple of

4

. Indeed, there are two equal numbers, say

a_{1}, a_{2}

. We cannot have

a_{1} = a_{2} = 2

, so either

a_{1} = a_{2} = 1

or

a_{1} = a_{2} = 3

. We can suppose wlog

a_{1} = a_{2} = 1

(otherwise, reverse the signs of all four numbers modulo

4

). But since we also cannot have

a_{j} = 3

and

a_{3} = a_{4} = 1

, one of

a_{3}, a_{4}

, say

a_{3}

, is

2

. But then

a_{1} + a_{2} + a_{3} = 1 + 1 + 2 = 4

.

So the quantity of numbers is at most

3

.

5

,

13

and

17

is an example of a list with three numbers.