IMO 1978 SL 15

Origin: YUG

Problem

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} \subsetA and k j=1 aij \equivn (mod p), then f(B) = n, (ii) f(\emptyset) = 0, \emptysetbeing the empty set. Prove that for each n \inP there exists B \subsetA such that f(B) = n.

Solution

Let Cn = {a1, . . . , an} (C0 = \emptyset) and Pn = {f(B) | B \subseteqCn}. We claim that Pn contains at least n+1 distinct elements. First note that P0 = {0} contains one element. Suppose that Pn+1 = Pn for some n. Since Pn+1 = {an+1 + r | r \inPn}, it follows that for each r \inPn, also r + bn \inPn. Then obviously 0 \inPn implies kbn \inPn for all k; therefore Pn = P has at least p \geqn + 1 elements. Otherwise, if Pn+1 \supsetPn for all n, then |Pn+1| \geq|Pn| + 1 and hence |Pn| \geqn + 1, as claimed. Consequently, |Pp−1| \geqp . (All the operations here are performed modulo p.)