Calculando el último dígito no nulo de ${1027 \choose 41}$ ?

Question

Estoy trabajando en el siguiente problema:

Dejemos que $x_n$ sea una secuencia de números Impares positivos. Si $N$ es el número de pares ordenados $(x_1, x_2, x_3, \dots, x_{42})$ tal que $$x_1 + x_2 + x_3 + \dots + x_{42} = 2014,$$

entonces encuentra $N \pmod {1000}$

Mi progreso: Deja $x_n = 2a_n + 1$ con $a_n \geq 0$ . Entonces $$a_1 + a_2 + a_3 + \dots + a_{42} = 986$$

Por estrellas y barras, esto equivale a ${1027 \choose 41}$ .

Para encontrar lo que es igual a $\pmod {1000}$ Primero calculé el número de $5$ en él. Encontré que había $2$ más $5$ s en el numerador, y estoy seguro de que hay al menos $2$ más $2$ s en el numerador también (la parte superior tiene $2^{10} = 1024$ ), por lo que hay dos ceros finales. Sin embargo, no sé cómo podría encontrar el último dígito distinto de cero de este número.

Answer 1

Pude resolver el problema utilizando una de las generalizaciones del teorema de Lucas (tomada de la página 2 del maravilloso documento Coeficientes binomiales módulo de la potencia del primo ).

$$\dfrac1{p^k}\binom{n}{m}\equiv(-1)^k\left(\dfrac{n_0!}{m_0!r_0!}\right)\left(\dfrac{n_1!}{m_1!r_1!}\right)\cdots\left(\dfrac{n_d!}{m_d!r_d!}\right)\pmod{p}$$

donde $r = n -m$ y $n_i, m_i, r_i$ son los $i$ dígitos en la base $p$ representación de $n, m, r$ respectivamente. $k$ es la mayor potencia de $p$ dividiendo $\binom{n}{m}$ .

Tenemos $n=1027, m = 41, r = 986$ . En la base $p=5$ , $n = (13102)_5, m = (00131)_5, r = (12421)_5$ .

El resultado anterior da

$\begin{align}\frac{1}{5^k}\binom{1027}{41} &\equiv (-1)^k\left(\frac{1!}{0!1!}\right)\left(\frac{3!}{0!2!}\right)\left(\frac{1!}{1!4!}\right)\left(\frac{0!}{3!2!}\right)\left(\frac{2!}{1!1!}\right) \mod{5}\\&\equiv (-1)^k \left(\frac{1}{1}\right) \left(\frac{6}{2}\right)\left(\frac{1}{24}\right)\left(\frac{1}{12}\right)\left(\frac{2}{1}\right) \mod{5}\\&\equiv (-1)^k \cdot 1 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \mod{5}\\&\equiv (-1)^k \cdot 2 \mod{5}\end{align}$

Obtenemos $2$ lleva al añadir $m$ y $r$ en la base $5$ , por lo que a partir de Teorema de Kummer , $k=2$ . $\begin{array}{c}\color{blue}{\text{carry}}&\color{blue}{0}&\color{blue}{0}&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}\\m&-&0&0&1&3&1\\r&-&1&2&4&2&1\\\hline \\m+r&-&1&3&1&0&2\end{array}$

Por lo tanto, tenemos

$\begin{align}\frac{1}{5^2}\binom{1027}{41} &\equiv (-1)^2 \cdot 2 \mod{5}\\\iff \frac{1}{5^2}\binom{1027}{41}&=5j + 2 \text{ where } j \in \mathbb{N}\\\iff\binom{1027}{41} &= 125j + 50\\\iff\binom{1027}{41} &\equiv 50 \mod{125}\end{align}$

Pasos similares para la base $p=2$ dar $\begin{align}\binom{1027}{41} &\equiv 0 \mod{8}\end{align}$

Y así obtenemos nuestra respuesta:

$\begin{align}x&\equiv \binom{1027}{41} (\text{mod }{1000})\equiv 50 (\text{mod }{125})\equiv 0 (\text{mod }{8})\\\implies x &\in \{50, 175, 300, 425, 550, 675, \color{green}{800}, 975\} \cap \{0, 8, 16, \cdots, 792, \color{green}{800}, 808, \cdots 992\}\\\implies x &= {800}\end{align}$

Answer 2

$\sum_{i = 1}^{\infty} \left \lfloor \frac{1027}{5^i} \right \rfloor - \left \lfloor \frac{41}{5^i} \right \rfloor - \left \lfloor \frac{1027-41}{5^i} \right \rfloor= 2$ por lo que sólo hay dos ceros al final.

Por lo tanto, basta con encontrar el coeficiente binomial módulo $1000$ .

Ahora $\sum_{i = 1}^{\infty} \left \lfloor \frac{1027}{2^i} \right \rfloor - \left \lfloor \frac{41}{2^i} \right \rfloor- \left \lfloor \frac{1027-41}{2^i} \right \rfloor >3$ así que $ \dbinom{1027}{41} \equiv 0 \pmod 8$ .

Ahora para evaluar la expresión modulo $125$ Lo reescribimos.

$\dbinom{1027}{41} = \frac{1027 \cdot 1026 \cdot 1025 \cdots 1001}{986 \cdot 985 \cdot 984 \cdots 960} \dbinom{1000}{959} \equiv \frac{27!}{111 \cdot 110 \cdots 85} \dbinom{1000}{959} $

$\dbinom{1000}{959} = \frac{1000}{959} \dbinom{999}{958} = \frac{42}{959} \dbinom{1000}{958}$ .

Continuando de esta manera,

$\dbinom{1000}{959} = \frac{42 \cdot 43 \cdots 125}{959 \cdot 958 \cdots 876} \dbinom{1000}{875}$ .

Ahora por el Teorema de Wolstenholme que es $\dbinom{ap}{bp} \equiv \dbinom{a}{b} \pmod {p^3}$ , $\dbinom{1000}{875} \equiv \dbinom{8}7 \equiv 8 \pmod {125}$ .

Ahora tenemos que evaluar $\frac{27! \cdot 42 \cdot 43 \cdots 125}{111 \cdot 110 \cdots 85 \cdot 876 \cdots 958 \cdot 959} \pmod {125}$ .

Podemos reescribirlo como $\frac{27! \cdot 42 \cdot 43 \cdots 125}{111!} \pmod {125}$ .

Ahora podemos cancelar para obtener

$\frac{27! \cdot 42 \cdot 43 \cdots 125}{111!} \equiv \frac{ 112 \cdot 113 \cdots 125}{28 \cdot 29 \cdots 41} \pmod {125}$ .

Entonces $\frac{112 \cdot 113 \cdots 124 \cdot 125}{28 \cdot 29 \cdots 41} \equiv \frac{(-1)(13!) \cdot 125}{28 \cdot 29 \cdots 41} \pmod {125}$ .

Entonces $28 \cdot 29 \cdots 41 = 5^3K$ donde $K \equiv 12 \pmod {125}$ . (Se obtiene fácilmente multiplicando dos números en los extremos a la vez y reduciendo).

Finalmente, $\frac{(-1)(13!) \cdot 125}{28 \cdot 29 \cdots 41} \equiv \frac{-13!}{12} \equiv 100 \pmod {125}$ .

Entonces, finalmente, $\dbinom{1027}{41} \equiv 8 \cdot 100 \equiv 50 \pmod {125}$ .

Resolver el sistema $N \equiv 0 \pmod 8, N \equiv 50 \pmod {125}$ da que $N \equiv 800 \pmod {1000}$ por lo que el último dígito no cero es $8$ .