IMO Shortlist 1978 problem 15


Kvaliteta:
  Avg: 0,0
Težina:
  Avg: 0,0
Dodao/la: arhiva
2. travnja 2012.
LaTeX PDF
Let p be a prime and A = \{a_1, \ldots , a_{p-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 \mathcal P(A) (the set of all subsets of A) to the set P = \{0, 1, \ldots, p - 1\} in the following way:

(i) if B = \{a_{i_{1}}, \ldots , a_{i_{k}} \} \subset 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.
Izvor: Međunarodna matematička olimpijada, shortlist 1978