17th Balkan 2000

Show that for any n we can find a set X of n distinct integers greater than 1, such that the average of the elements of any subset of X is a square, cube or higher power.

Solution

Let a₁, a₂, ... , a_n be any n distinct integers. Take N divisible by all of 2, 3, 4, ... , n (for example, we could take N = n!). Let b_i = a_iN. Then the b_i are distinct integers and the average of any subset of {b₁, b₂, ... , b_n} is an integer.

Let the set of all distinct averages be {c₁, ... , c_m}. Let p₁, p₂, ... , p_m be distinct primes. Suppose that p is a prime dividing one or more of the c_i. Suppose that the highest power of p dividing c_i is p to the power of d_i. Then, by the Chinese remainder theorem, we can find an integer K such that K = -d_i mod p_i for each i. Hence if we let N_p = p^K, then the highest power of p dividing N_pc_i is p to the power of a multiple of p_ith power. We now repeat this exercise for each prime p dividing one or more of the c_i. Suppose the resulting set of numbers is {h₁, h₂, ... , h_m}, where h_i = M c_i and M = N_pN_q ... . Then h_i is a p_ith power. Thus the required set of integers is {Mb₁, Mb₂, ... , Mb_n}.

Note that this is a somewhat impractical procedure. Suppose we start with 3, 4, 5. To get the averages integral we move to 6, 8, 10. The set of averages is then 6, 7, 8, 9, 10. The primes involved are 2, 3, 5, 7. To fix 2 we multiply by 2¹⁴⁰⁷, to fix 3 we multiply by 3²⁸⁰⁵, to fix 5 we multiply by 5²¹⁰⁰, and to fix 7 we multiply by 7⁷⁷⁰. Thus our final set of three integers is 6.2¹⁴⁰⁷3²⁸⁰⁵5²¹⁰⁰7⁷⁷⁰, 8.2¹⁴⁰⁷3²⁸⁰⁵5²¹⁰⁰7⁷⁷⁰, 10.2¹⁴⁰⁷3²⁸⁰⁵5²¹⁰⁰7⁷⁷⁰.

17th Balkan 2000

© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002