The natural number is "good" if for every natural numbers such that we have there exist , such that , for every (empty sum is equal to zero). Find all the "good" numbers.
Solution
We will prove that is a "good" number if and only if it is prime.
First we will prove that if is not prime, then it is not "good". Let , . For then
and for there does not exist a subset .
Now we prove that every prime number is "good".
Let be a prime number. There exist at least different numbers (mod ) as sums of the elements , where , . The proof is by induction.
For , empty sum is equal to zero (mod ) and the sum of is not.
Let and let the proposition be true for .
Let the proposition be not true for . Let be the numbers such that their sums do not give at least different numbers (mod ). Since the proposition holds for , there exist sums distinct from each other (mod ), for . Then do not give a new number (mod ) (different from ). Because , it holds . But there exist such that and , from where . This is a contradiction with being a prime number.