Cuántos números $k$ de $200 \choose k$ son divisibles por $3$ ? $k \in \{0,1,2,\cdots 200\}$

Question

"¿Cuántos de los números (200 Elija k), donde k es un elemento del conjunto {0,1,2,3,4,....,200} son divisibles por 3?"

Esto es lo que pienso:

(200 Elija 0,1, y 2) no son múltiplos de 3 pero cada combinación siguiente tiene al menos 1 múltiplo de 3 en el numerador por lo que el número es divisible por 3. Como hay 201 números de 0 a 200, y 3 números (0,1, y 2) no funcionan, hay 198 números k.

¿Esta respuesta es correcta y es el método adecuado?

Answer 1

Según Teorema de Lucas un coeficiente binomial $\binom{m}{n}$ es divisible por un primo p si y sólo si al menos una de las bases p dígitos de n es mayor que el dígito correspondiente de m .

Answer 2

$\newcommand{\dcc}[1]{\left\lfloor#1\right\rfloor}$ Sabemos por el teorema de Legendre que la potencia de un 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 primo 3 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 esta cifra 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}},$$ que es la multiplicidad en la 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 las que al menos una de estas desigualdades es estricta.

Es útil observar que el valor $\dcc{\frac{k}3}+\dcc{\frac{200-k}3}$ es el mismo para todos los $k$ en la misma clase de residuo módulo 3. Por lo tanto, basta con comprobar $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$ . (Intentamos $k\equiv 0,1,2\pmod3$ ).

Para el 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 obtenemos $$\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 lo cual $\binom{200}k$ es no 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 añadimos 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 .

Answer 3

Véase, por ejemplo, N. J. Fine, Binomial coefficients modulo a prime, Am. Math. Monthly 54 (10) (1947) 589-592, http://www.jstor.org/stable/2304500 . Véase también D. Singmaster, Divisibility of binomial and multinomial coefficients by primes and prime powers, http://www.fq.math.ca/Books/Collection/singmaster.pdf .