Problem

Source:

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



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.$