Problem

Source:

Tags: modular arithmetic, algebra, polynomial, number theory, Divisibility, IMO Shortlist



Let p be a prime and A={a1,,ap1} 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,,p1} 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.