33rd IMO shortlist 1992/15 solution

33rd IMO 1992 shortlist

Problem 15

Does there exist a set of 1992 positive integers such that each subset has a sum which is a square, cube or higher power?

Answer

Yes.

Solution

We show that given any positive integer n, we can find a positive integer d such that d, 2d, 3d, ... , nd are all squares or higher powers. We use induction on n. n = 1 is trivial. Suppose the result is true for n, so d = m₁^k₁, 2d = m₂^k₂, ... , nd = m_n^k_n. Put k = lcm(k₁, k₂, ... k_n), D = d(n+1)^kd^k. Then D certainly works for 1, 2, ... , n. But it also works for n+1: (n+1)D = ((n+1)d)^k+1. So the result is true for n+1 and hence for all n.

So take d for n = 1+2+3+...+1992. Then the set {d, 2d, 3d, ... , 1992d} meets the requirements.

33rd IMO shortlist 1992