¿Cuántos números kkk de (200k)(200k)200 \choose k son divisibles por 333? k∈{0,1,2,⋯200}k∈{0,1,2,⋯200}k \en \{0,1,2,\cdots 200\}

$\newcommand{\dcc}[1]{\left\lfloor#1\right\rfloor}$Sabemos por el teorema de Legendre que la potencia de un número primo$p$en$n!$es igual a$\sum_{a=1}^\infty \dcc{\frac{n}{p^a}}$. Véase, por ejemplo, Wikipedia , ProofWiki ; puede encontrar fácilmente muchos recursos en línea y libros donde se explica este resultado.

Nos interesa la potencia en la que aparece el 3 primo en el número$\binom{200}k=\frac{200!}{(200-k)!k!}$.

¡La multiplicidad de 3 en 200! es

$$\dcc{\frac{200}3}+\dcc{\frac{200}9}+\dcc{\frac{200}{27}}+\dcc{\frac{200}{81}}.$$ Queremos comparar este número con $$\dcc{\frac{200-k}3}+\dcc{\frac{200-k}9}+\dcc{\frac{200-k}{27}}+\dcc{\frac{200-k}{81}} +\dcc{\frac{k}3}+\dcc{\frac{k}9}+\dcc{\frac{k}{27}}+\dcc{\frac{k}{81}},$$ cual es la multiplicidad en que $3$aparece en $(200-k)!k!$.

Desde$\dcc a +\dcc b\le\dcc{a+b}$, tenemos

$$\begin{align*} \dcc{\frac{k}3}+\dcc{\frac{200-k}3} &\le \dcc{\frac{200}3}\\ \dcc{\frac{k}9}+\dcc{\frac{200-k}9} &\le \dcc{\frac{200}9}\\ \dcc{\frac{k}{27}}+\dcc{\frac{200-k}{27}} &\le \dcc{\frac{200}{27}}\\ \dcc{\frac{k}{81}}+\dcc{\frac{200-k}{81}} &\le \dcc{\frac{200}{81}} \end{align*}$$ Queremos encontrar los valores de $k$para los cuales al menos una de estas desigualdades es estricta.

Es útil notar que el valor$\dcc{\frac{k}3}+\dcc{\frac{200-k}3}$es igual para todos$k$está en la misma clase de residuo módulo 3. Por lo tanto, basta con verificar$k=0,1,2$y vemos que

$$\dcc{\frac{k}3}+\dcc{\frac{200-k}3} = \dcc{\frac{198}3} = \dcc{\frac{200}3}$$ para cualquier $k$. (Nosotros tratamos $k\equiv 0,1,2\pmod3$).

Para 9 obtenemos

$$\dcc{\frac{k}9}+\dcc{\frac{200-k}9}= \begin{cases} \frac{198}9=22=\dcc{\frac{200}9} & \text{for }k\equiv0,1,2 \pmod9, \\ \frac{191}9=21<\dcc{\frac{200}9} & \text{for }k\equiv3,4,\dots,8 \pmod9 \end{cases}$$

Para 27 tenemos

$$\dcc{\frac{k}{27}}+\dcc{\frac{200-k}{27}}= \begin{cases} \frac{189}{27}=7=\dcc{\frac{200}{27}} & \text{for }k\equiv0,1,2,\dots,11 \pmod{27}, \\ \frac{162}{27}=6<\dcc{\frac{200}{27}} & \text{for }k\equiv12,13,\dots,26 \pmod{27} \end{cases}$$

Para 81 obtenemos

$$\dcc{\frac{k}{81}}+\dcc{\frac{200-k}{81}}= \begin{cases} \frac{162}{81}=2=\dcc{\frac{200}{81}} & \text{for }k\equiv0,1,2,\dots,38 \pmod{81}, \\ \frac{81}{81}=1<\dcc{\frac{200}{81}} & \text{for }k\equiv39,\dots,80 \pmod{81} \end{cases}$$

Así que los números que$k$para cual$\binom{200}k$no es divisible por$3$son precisamente los números que cumplen simultáneamente las condiciones

$$\begin{align*} k&\equiv0,1,2 \pmod9\\ k&\equiv0,1,2,\dots,11 \pmod{27}\\ k&\equiv0,1,2,\dots,38 \pmod{81} \end{align*}$$ Las dos primeras condiciones se cumplen si $k\equiv0,1,2,9,10,11\pmod{27}$. Si sumamos la tercera condición, obtenemos que esto se cumple para $$k \equiv 0,1,2,9,10,11,27,28,29,36,37,38 \pmod{81}$$ Esto nos da los 36 valores posibles. $k= 0,1,2,9,10,11, 27,28,29,36,37,38, 81,82,83,90,91,92, 108,109,110,117,118,119, 162,163,164,171,172,173, 189,190,191,198,199,200$.

Esto coincide con los cálculos mencionados en este comentario .