number of $\lbrace 1,2,...,53 \rbrace$ subsets with member summation divisible by $3$

Question

In $\lbrace 1,2,3,...,53 \rbrace$ how many subsections do we have with this condition:
the summation of subset members must be divisible by $3$.

for example $\lbrace 1,2 \rbrace$ & $\lbrace 1,2,3,4,5 \rbrace$ count.

Answer 1

From the $8$ subsets of $[3]=\{1,2,3\}$ four have sum $0$ mod $3$, and $2$ each have sum $1$ or $2$ mod $3$. Denote by $p_m$ the probability that a random subset of $[3m]$ has sum $0$ mod $3$. Then $p_0=1$, and the first sentence of this answer implies $$p_{m+1}={1\over 2}p_m+{1\over4}(1-p_m)\ .$$ According to the Master Theorem the solution to this difference equation is $$p_m={1\over3}+{2\over3}4^{-m}\ .$$ In particular the probability that a random subset of $[54]$ has sum $0$ mod $3$ is given by $p_{18}={1\over3}+{2\over3}4^{-18}$. The analogous probability for a subset of $[53]$ is the same. From this we can conclude that there are $$2^{53}\left({1\over3}+{2\over3}4^{-18}\right)={1\over3}\bigl(2^{53}+2^{18}\bigr)=3\,002\,399\,751\,667\,712$$ admissible subsets of $[53]$.

Answer 2

3002399751667712

Computation in Maple:

F := proc(n,k) options remember; if n=1 then if k=0 or k=1 then 1 else 0 fi else F(n-1, k) + F(n-1, k-n mod 3) fi end: F(53,0);

It is also possible to do this by hand. Say that $F(m)$ is the number of such subsets of $\{1,\ldots,3m\}$. Now find a recurrence relation for $F(m)$. Then compute $F(51/3)$. The final answer is then $2^{51} + F(51/3)$ because each subset of $\{1,\ldots,51\}$ can be extended in 2 or 1 ways to a corresponding subset of $\{1,\ldots,53\}$, depending on whether that subset has a sum congruent to $0$ mod 3 or not.

Answer 3

The generating function for these is

$$\prod_{q=1}^{53} (1+z^q)$$

and with $\zeta = \exp(2\pi i/3)$ we obtain for the answer

$$\frac{1}{3} \sum_{p=0}^2 \prod_{q=1}^{53} (1+\zeta^{pq}) = \frac{1}{3} 2^{53} + \frac{1}{3} \prod_{q=1}^{53} (1+\zeta^{q}) + \frac{1}{3} \prod_{q=1}^{53} (1+\zeta^{2q}).$$

Now since $(1+\zeta)(1+\zeta^2)(1+\zeta^3)= (2+\zeta+\zeta^2) \times 2 = 2$ this becomes

$$\frac{1}{3} 2^{53} + \frac{1}{3} 2^{17} (1+\zeta)(1+\zeta^2) + \frac{1}{3} 2^{17} (1+\zeta^2)(1+\zeta) = \frac{1}{3} 2^{53} + \frac{2}{3} 2^{17} \\ = 3002399751667712.$$