MathDB

15

Part of 1978 IMO Shortlist

Problems(1)

Prove that for each n there exist B such that B(n)=n

Source:

9/20/2010
Let pp be a prime and A={a1,…,ap−1}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 pp. Let us define a mapping ff from P(A)\mathcal P(A) (the set of all subsets of AA) to the set P={0,1,…,p−1}P = \{0, 1, \ldots, p - 1\} in the following way:
(i)(i) if B={ai1,…,aik}⊂AB = \{a_{i_{1}}, \ldots , a_{i_{k}} \} \subset A and ∑j=1kaij≡n(modp)\sum_{j=1}^k a_{i_{j}} \equiv n \pmod p, then f(B)=n,f(B) = n,
(ii)(ii) f(∅)=0f(\emptyset) = 0, ∅\emptyset being the empty set.
Prove that for each n∈Pn \in P there exists B⊂AB \subset A such that f(B)=n.f(B) = n.
modular arithmeticalgebrapolynomialnumber theoryDivisibilityIMO Shortlist