I have to do a IMO training homework but there is a question that confusing me.
How many non-empty subsets of $1,2,3,\cdots,p-2,p-1$ have a sum which is divisible by $p$ that $p$ is an odd prime?
I have tried $p=3,5,7$ and the number of subsets is $1,3,9$ respectively. I have thought of if the answer is $3^\frac{p-3}{2}$, but I am pretty not sure. If anyone knows the answer or find the number of subsets when $p$ is other odd primes, please tell me. Thank you!
On
The generating function for the sum of non-empty subsets is $P(x) = \prod_{i=1}^{p-1} (1+x^i) -1 $.
We want the sum of the coefficients of the exponents which are multiples of $p$, which is given by $ \frac{1}{p} \sum_{\text{x is a pth root of unity}} P(x)$.
Let $\omega$ be a primitive $pth$ root of unity.
Consider $f(z) = \sum_{j=0}^{p-1} z^j = \prod_{i=1}^{p-1} ( z - \omega^i)$.
Since $p$ is odd, $1 = f(-1) = \prod (-1 - \omega^i) = \prod (1+\omega^i)$. This shows that $P(\omega) = 0 $.
Hence, $ \frac{1}{p} \sum P(x) = \frac{1}{p} P(1) = \frac{1}{p} ( 2^{p-1} -1). $
To get the observation of saulspatz that the number of subsets with sum $\equiv k \pmod{p}$ is also equal to $\frac{1}{p} ( 2^{p-1} -1)$, we want the sum of the coefficients of the exponents which are of the form $np+k$, which is given by $ \frac{1}{p} \sum_{\text{x is a pth root of unity}} x^k P(x)$.
The above shows that $ \frac{1}{p} \sum x^k P(x) = \frac{1}{p} 1^k P(1) = \frac{1}{p} ( 2^{p-1} -1). $
Consider, instead, subsets of $\{0,1,\ldots,p-1\}$. There will be twice as many subsets; and twice as many whose sum is a multiple of $p$ because you have the option of including $0$ in any subset.
Take any subset except the empty set and the full set. Call it $S_0=\{x_1,\ldots,x_k\}$. Note that $1\le k\le p-1$. There are $p$ sets $S_i=\{i+x_1,\ldots,i+x_k\}$ formed by adding the number $i$ to each element, as $i$ ranges from $0$ to $p-1$. This adds $ki$ to the sum, so the sums are all different $\pmod p$ because we have excluded the empty set and the full set.
So the $2^p-2$ subsets split up into $p$ equal groups. There are $(2^p-2)/p$ that are multiples of $p$.
Add back in the empty set and full set to give $2+(2^p-2)/p$. Pair up sets that include $0$ with sets that don't, and remove the sets that include $0$. That leaves $1+(2^{p-1}-1)/p$. Lastly, remove the empty set to leave $(2^{p-1}-1)/p$.