Let p be a prime and A={a1,…,ap−1} an arbitrary subset of the set of natural numbers such that none of its elements is divisible by p. Let us define a mapping f from P(A) (the set of all subsets of A) to the set P={0,1,…,p−1} in the following way: (i) if B={ai1,…,aik}⊂A and \sum_{j=1}^k a_{i_{j}} \equiv n \pmod p, then f(B) = n, (ii) f(\emptyset) = 0, \emptyset being the empty set. Prove that for each n \in P there exists B \subset A such that f(B) = n.
Problem
Source:
Tags: modular arithmetic, algebra, polynomial, number theory, Divisibility, IMO Shortlist