Rompecabezas: Suma Acumulada Divisible por 10

Question

Si sumamos la primera $4$ enteros positivos, obtenemos $4 + 3 + 2 + 1 = 10$ que creo que está muy bien.

Estoy interesado en ver las soluciones al siguiente enigma: Si tomamos la suma acumulada de los primeros $N$ enteros positivos, ¿cuántas veces en el camino la suma será divisible por $10$ ?

En otras palabras, definir: $$f(N) = \left|\left\{n \leq N \;:\; \sum_{i=1}^n i = \frac{n(n+1)}{2} \text{ is divisible by $ 10 $}\right\} \right|$$

¿Existe una buena expresión para $f(N)$ ?

Answer 1

Necesitas $20$ para dividir $n(n+1)$ . Nota $n$ y $n+1$ son de paridad opuesta. Por lo tanto, $4$ divide a cualquiera de los dos $n$ o $n+1$ . $5$ divide a cualquiera de los dos $n$ o $n+1$ desde $5$ es un primo. Por lo tanto, tenemos $4$ casos que nos da como se discute a continuación.

$1$ . $4|n$ y $5|n$ . Este caso es trivial. Dado que $(4,5)=1$ , obtenemos que $20|n$ y por lo tanto $n \equiv 0\bmod 20$ .

$2$ . $4|n$ y $5|(n+1)$ . Esto significa que $n = 4k_4$ y $n+1 = 5k_5$ . Por lo tanto, obtenemos que $5k_5 - 4k_4 = 1$ .

La resolución de estas congruencias generales se enmarca en la Teorema del resto chino como señala TMM en los comentarios, y es algo que ciertamente deberías mirar. En este caso, lo resolvemos como sigue. Claramente, $(k_4,k_5) = (1,1)$ es una solución. En general, si $ax+by$ tiene soluciones enteras y $(x_0,y_0)$ es una de esas soluciones enteras, entonces todo las soluciones enteras vienen dadas por $$(x,y) = \displaystyle \left( x_0 + k \frac{\text{lcm}[\lvert a \rvert,\lvert b \rvert]}{a}, y_0 - k \frac{\text{lcm}[\lvert a \rvert,\lvert b \rvert]}{b} \right)$$ donde $k \in \mathbb{Z}$ . Por lo tanto, obtenemos que $(k_4,k_5) = (1+5k,1+4k)$ . Esto nos da que $n = 20k+4$ es decir $n \equiv 4 \bmod 20$ .

$3$ . $4|(n+1)$ y $5|n$ . Esto significa que $n = 5k_5$ y $n+1 = 4k_4$ . Por lo tanto, obtenemos que $4k_4 - 5k_4 = 1$ . Claramente, $(k_4,k_5) = (4,3)$ es una solución. Por lo tanto, obtenemos que $(k_4,k_5) = (4+5k,3+4k)$ . Esto nos da que $n=20k+15$ es decir $n \equiv 15 \bmod 20$ .

$4$ . $4|(n+1)$ y $5|(n+1)$ . Este caso también es trivial. Dado que $(4,5) = 1$ , obtenemos que $20|(n+1)$ y por lo tanto $n \equiv 19 \bmod 20$ .

En resumen, las soluciones vienen dadas por

\begin{cases} n \equiv 0\bmod 20 &(\text{ if }4 \text{ divides }n \text{ and }5 \text{ divides }n)\\ n \equiv 4\bmod 20 & (\text{ if }4 \text{ divides }n \text{ and }5 \text{ divides }n+1)\\ n \equiv 15\bmod 20 & (\text{ if }4 \text{ divides }n+1 \text{ and }5 \text{ divides }n)\\ n \equiv 19\bmod 20 & (\text{ if }4 \text{ divides }n+1 \text{ and }5 \text{ divides }n+1) \end{cases}

Answer 2

Escriba $n$ en la forma $20k+j$ donde $0≤j<20$ .

Entonces tienes $n(n+1) = (20k+j)(20k+j+1) = 400k^2 + 40kj + 20k + j^2 + j$ que obviamente es un múltiplo de 20 si y sólo si $j^2+j$ es. Así que el problema se ha reducido a encontrar $0≤j<20$ donde $j(j+1)$ es un múltiplo de 20; esto ocurre para $j=0,4,15,19$ por lo que todas las soluciones tienen la forma $n=20k+\{0,4,15,19\}$ para algún número entero $k$ .

---

¿De dónde saqué la inspiración para escribir $n$ en la forma $20k+j$ ? Supuse que se repetiría con el período 10 o 20, y miré la lista de números triangulares en OEIS y vio que los múltiplos de 10 sí aparecían en $n=4,15,19,20,24$ Así que 20 parecía ser el camino a seguir.

¿Por qué supuse que se repetiría con periodo 10 o 20? La razón principal es que las preguntas sobre cuándo un polinomio $P(n)$ es divisible por $q$ suele hacer algo así, porque si se calcula $P(n+q) - P(n)$ el término constante se cancela, al igual que todos los términos que son puros en $n$ y te deja con algunos términos de orden superior que son todos divisibles por $q$ .

Sabía que era lo que había que intentar porque he visto muchos problemas de ese tipo.

Adenda: ¿Cuántas soluciones se encuentran entre 1 y $N$ ? Escriba $N=20k+j$ como antes, y la respuesta es $4k$ más un factor de confusión. El factor de manipulación es 0 si $j<4$ , 1 si $4≤j<15$ , 2 si $15≤j<19$ y 3 si $j=19$ .

Answer 3

Sugerencia $ $ Si $\rm\:m,n,i\in \mathbb Z\:$ y $\rm\:(n,i) = 1\:$ con $\rm\:m,\:\!m\!+\!i\:$ potencias de primos distintos, entonces

$\rm\quad\phantom{m\!|\:\!\rm n\!+\!i,}\:\ m(m\!+\!i)\:|\:n(n\!+\!i)\ $ si se cumple uno de los cuatro casos siguientes

$\quad\begin{eqnarray} \rm &&&\rm m(m\!+\!i)\!\!\! &|&\rm n &\ \iff\ &\rm n\equiv\:\ \ 0&\rm\pmod{\:m(m\!+\!i)} \\ \rm &&&\rm m(m\!+\!i)\!\!\!&|&\rm n\!+\!i &\ \iff\ &\rm n\equiv -i&\rm\pmod{\:m(m\!+\!i)} \\ \rm m\!&|\:&\rm n,\!\!\!\!&\rm \phantom{m(}m\!+\!i\:&|&\rm n\!+\!i &\ \iff\ &\rm n\equiv\ m&\rm\pmod{\:m(m\!+\!i)} \\ \rm m\!&|&\:\!\rm n\!+\!i,\!\!\!\! &\rm \phantom{m(}m\!+\!i\!\!\!\!\!\!\:&|&\rm n &\ \iff\ &\rm n\equiv -m\!-\!i\!\!\!\!\:&\rm\pmod{\:m(m\!+\!i)} \end{eqnarray}$

Poner $\rm\ m=4,\ i=1\:$ para resolver su problema.

Pista para la demostración: para potencias primarias $\rm\:p^k\:|\:n(n\!+\!i)\!\iff\! p^k\:|\:n\:$ o $\rm\:p^k\:|\:n\!+\!i\:$ por $\rm\:n,n\!+\!i\:$ coprima, por $\rm (n,n\!+\!i)=(n,i) = 1.$

Answer 4

Para calcular los múltiplos de diez, sólo importa el dígito de la unidad. Además, un múltiplo de diez más un múltiplo de diez es un múltiplo de diez. Así, podemos encontrar los patrones aplicables que debemos considerar:

Primer patrón para llegar a un múltiplo de diez (empezando por 1):

1+2+3+4 = 10

Segundo patrón (empezando por el 5, ya que en el patrón anterior contamos 4 en último lugar):

5+6+7+8+9+0+1+2+3+4+5 = 50

Tercer patrón (a partir del 6):

6+7+8+9 = 30

Cuarto patrón (a partir del 5):

0

Repita el patrón 1

---

Ahora tenemos los 4 patrones secuenciales que debemos considerar, que constan de 20 números en total. Soy más un programador que un matemático, así que aquí hay una manera de representar la solución mediante programación (en este caso usando JavaScript), con un para verlo en acción :

function getMultiplesOfTenWhileCountingTo(finalCount){
    //There are 4 multiples every 20 numbers
    var multiples = Math.floor(finalCount/20) * 4;

    //Add the additional multiples based on the remainder
    var remainder = finalCount % 20;
    if(remainder >= 4){
        multiples++;
    } 
    if(remainder >= 15){
        multiples++;
    }
    if(remainder >= 19){
        multiples++;
    }
    return multiples;
}

Answer 5

Dada la expresión

$$f(N)=\#\left\{n\le N:\sum_{i=1}^n i=n(n+1)2 \text{ is divisible by 10}\right\},$$

cada vez que el $n=4,64,1024$ etc., toman la raíz (por ejemplo, en $2^2$ , $2^6$ , $2^{10}$ ), por lo tanto, puede formar su función de las siguientes dos maneras:

1. $\text{power}\,\%\,4=2$ ;
2. Una progresión aritmética con el primer término 2 y $d=4$ te dará los poderes de dos.

Disculpas por el mal formato.