Un problema sobre congruencias simples.

Question

Este es un problema sobre congruencias dado en el libro de Andy Liu, titulado "Tierra Aritmética".

Un Dragón tiene $100$ cabezas, y solo puede ser matado si se cortan todas sus cabezas. Un Príncipe tiene dos espadas. La larga puede cortar exactamente $21$ cabezas del Dragón a la vez. La corta puede cortar exactamente $4$ cabezas del Dragón a la vez, pero cada vez que esta espada se usa, el Dragón crece otras $1985$ cabezas. El Príncipe debe tener cuidado de no dejar al Dragón con $1, 2$ o $3$ cabezas, ya que sus espadas serán inútiles entonces. ¿Puede el Príncipe matar al Dragón?

Mi intento:
Como $100/21$ debería dar un resto, que puede ser mínimo de $16$.
Esto significa que la espada corta debe ser utilizada también.
La condición adicional parece inútil a menos que la combinación lineal de $21x+4y$ pueda lograr un valor de $99, 98,$ o $97$, para lo cual la segunda condición adicional de crecer $1985$ cabezas al cortar al dragón con la espada más pequeña debería ser aplicable.

Entonces, al plantear la igualdad: $100 = 21x + 4y$, obtenemos la solución para $x= 4, y =4$.
Pero, esta formulación de la igualdad es incorrecta, ya que el $\gcd$ de $21,4=1$, y así solo puede ser $100=2100x +400y$.

La condición adicional de crecer $1985$ cabezas parece difícil de combinar con la misma igualdad. No está claro cómo debería plantear ecuaciones de tal manera que ambas condiciones adicionales encajen juntas en la misma igualdad.

Answer 1

Cada corte con la espada corta agrega una red de 1981 cabezas (+1985 -4). Simplemente tome 100+1981y = m. Luego use aritmética modular para determinar si m es alguna vez $0 \mod 21$ o $4 \mod 21$. Allí puedes probar o refutar.

Answer 2

$$\begin{align} h_0 &= 100 \\ h_{i+1} &= h_i + (-21 \ \text{o} \ 1981) \end{align}$$

Observamos que $\gcd(-21,1981)=7$ y $100 = 2 \pmod 7$. Se sigue que, para todo $i$, $h_i = 2 \pmod 7$. Concluimos que nunca podremos cortar todas las cabezas del dragón.

Respuesta a un comentario

Si el $21$ hubiera sido un $29$, entonces obtendríamos esta secuencia de recuentos de cabezas

$$\begin{align} h_0 &= 100 \\ h_{i+1} &= h_i + \begin{cases} -29 & \text{si se cortan 29 cabezas.} \\ 1981 & \text{si se cortan 4 cabezas.} \\ \end{cases} \end{align}$$

La estrategia más simple sería cortar cuatro cabezas hasta que haya un múltiplo de 29 cabezas en el dragón. Por lo tanto, necesitamos resolver la ecuación de congruencia

$$\begin{align} 1981x \equiv -100 \pmod{29} \\ 9x \equiv 16 \pmod{29} \\ x \equiv 5 \pmod{29} \end{align}$$

Por lo tanto, cortamos $4$ cabezas $5$ veces seguidas. Obtenemos $h_0 = 100$ y $h_5 = 10005 = 345 \cdot 29$. Cortamos $29$ cabezas $345$ veces y terminamos con $h_{350}=0$