número de subconjuntos de $\lbrace 1,2,...,53 \rbrace$ con adición de miembro divisible por $3$

Question

En $\lbrace 1,2,3,...,53 \rbrace$ cuantas subdivisiones tenemos con esta condición:
la suma de los miembros del subconjunto debe ser divisible por $3$.

por ejemplo $\lbrace 1,2 \rbrace$ & $\lbrace 1,2,3,4,5 \rbrace$ cuenta.

Answer 1

De la $8$ subconjuntos de a $[3]=\{1,2,3\}$ cuatro en suma $0$ mod $3$, e $2$ cada uno tiene suma $1$ o $2$ mod $3$. Denotar por $p_m$ la probabilidad de que un subconjunto aleatorio de $[3m]$ suma $0$ mod $3$. A continuación,$p_0=1$, y la primera frase de esta respuesta implica $$p_{m+1}={1\over 2}p_m+{1\over4}(1-p_m)\ .$$ De acuerdo con el Maestro Teorema de la solución a esta ecuación es la diferencia $$p_m={1\over3}+{2\over3}4^{-m}\ .$$ En particular, la probabilidad de que un subconjunto aleatorio de $[54]$ suma $0$ mod $3$ está dado por $p_{18}={1\over3}+{2\over3}4^{-18}$. El análogo de la probabilidad para un subconjunto de a $[53]$ es el mismo. De esto podemos concluir que hay $$2^{53}\left({1\over3}+{2\over3}4^{-18}\right)={1\over3}\bigl(2^{53}+2^{18}\bigr)=3\,002\,399\,751\,667\,712$$ admisible subconjuntos de a $[53]$.

Answer 2

3002399751667712

La computación en madera de Arce:

F := proc(n,k) las opciones de recordar; si n=1 entonces si k=0 o k=1 entonces 1 otra cosa 0 fi otra cosa F(n-1, k) + F(n-1, k-n mod 3) fi final: F(53,0);

También es posible hacerlo a mano. Decir que $F(m)$ es el número de subconjuntos de a $\{1,\ldots,3m\}$. Ahora encontrar una relación de recurrencia para $F(m)$. A continuación, calcular $F(51/3)$. La respuesta final es, a continuación, $2^{51} + F(51/3)$ debido a que cada subconjunto de $\{1,\ldots,51\}$ puede ser ampliado en 2 o 1 maneras, un subconjunto de a $\{1,\ldots,53\}$, dependiendo de si el subconjunto tiene una suma congruente a $0$ mod 3 o no.

Answer 3

La generación de la función de estos es

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

y con $\zeta = \exp(2\pi i/3)$ obtenemos la respuesta

$$\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^{t2}).$$

Ahora desde $(1+\zeta)(1+\zeta^2)(1+\zeta^3)= (2+\zeta+\zeta^2) \times 2 = 2$ esto se convierte en

$$\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.$$