The size of a finite set X is the number of members of X. We say a set of integers $X $of size $n ≥ 1$ is good if and only if it does not contain a nonempty subset $Y$, the sum of whose members is divisible by $n$. Is there a good set of integers of size at least $1$? If so, give an example of a good set of minimal size. Explain your answer. (The sum of the members of a set X = {k} of size 1 is k.)
I have no idea how to approach this problem. I really need an explanation of the thought process on solving this problem in a step by step kind of manner. Thank you.
No, there is not. To see this, suppose you had such a set $X$ and list the members as $\{x_1,\cdots, x_n\}$. For $m\in \{1,\cdots, n\}$ we define $s_m=\sum_{i=1}^m x_i$.
There are two possibilities.
I. No two of the $s_i$ are congruent $\pmod n$. In this case we are done, because there are $n$ of the $s_i$ and $n$ residue classes so we must have hit all the residue classes, so in particular we must have hit the class $0$.
II. We can find $1≤a<b≤n$ with $s_a\equiv s_b\pmod n$. In this case we are done since $$s_b-s_a=\sum_{i=a+1}^bx_i\equiv 0 \pmod n$$
Perhaps a concrete example would clarify matters. Let's take $$X=\{2,3,5,9,10,14\}$$ Then $$\{s_m\}_{m=1}^6=\{2,5,10,19,29,43\}$$ We are only interested in the remainders on division by $6$ so we reduce $\pmod 6$ to get $$\{s_m \pmod 6\}_{m=1}^6=\{2,5,4,1,5,1\}$$ We remark that $s_2\equiv s_5\pmod 6$ and we check that indeed $$s_5-s_2=5+9+10=24$$ is divisible by $6$, as desired.