Maths Olympiad Prep

Library / /2 of 6

Number theory Difficulty 4.7 AIME Prove it Brazil

Show that there is a set of 20022002 distinct positive integers such that the sum of one or more elements of the set is never a square, cube, or higher power.

Solution

Let pp be a prime and A={p,2p,3p,,2002p}A = \{p, 2p, 3p, \dots, 2002p\}. The sum of any quantity of numbers from AA is at most p+2p++2002p=10012003pp + 2p + \dots + 2002p = 1001 \cdot 2003p. Choose any p>10012003p > 1001 \cdot 2003 and we are done, because every sum of numbers from AA is a multiple of pp but not of p2p^2, and cannot be a perfect power.

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.