Ibero 94/B2 solution

9th Iberoamerican 1994

Problem B2

n and r are positive integers. Find the smallest k for which we can construct r subsets A₁, A₂, ... , A_r of {0, 1, 2, ... , n-1} each with k elements such that each integer 0 ≤ m < n can be written as a sum of one element from each of the r subsets.

Answer

smallest integer such that k^r ≥ n.

Solution

We can form at most k^r distinct sums, so k^r must be ≥ n.

Now consider A₁ = {0, 1, 2, ... , k-1}, A₂ = {0, k, 2k, ... , (k-1)k}, A₃ = {0, k², 2k², ... , (k-1)k²}, ... , A_r = {0, k^r-1, 2k^r-1, ... , (k-1)k^r-1}. Then for any non-negative integer m < k^r, we can write m with r digits in base k (using leading zeros as necessary) and hence as a sum of one element from each A_i. This subset works for (k-1)k^r-1 < n ≤ k^r. For smaller n above (k-1)^r we cannot use all the elements given above, but we do not need them, so we just replace the elements which are too large by arbitrary elements under n.

For example, suppose n = 17, r = 4. We need k = 3. So we form A₁ = {0, 1, 2}, A₂ = {0, 3, 6}, A₃ = {0, 9, 18}, A₄ = {0, 27, 54}. Now 18, 27, 54 are unnecessary, so we pad out A₃ and A₄ with other elements. We could take A₃ = {0, 1, 9}, A₄ = {0, 1, 2}.

9th Ibero 1994