Alcance N de $0$ en el menor número de movimientos donde el n's movimiento comprende n pasos y cada paso es un $\pm 1$ movimiento

Question

Alcanzar el número $\text{N}$ de $0$ en el menor número de movimientos en los que el $n\text{th}$ El movimiento comprende $n$ muchos pasos y cada paso es un $\pm 1$ movimiento. El mismo problema existe también aquí sin una prueba.

Supongamos que $k$ es el mayor número tal que $S :=1 + 2 + \cdots + k \leq \text{N}$ . Si es igual a $\text{N}$ hemos terminado y si la distancia que queda después de ir de $S$ a $N$ es uniforme, todavía estamos hechos (y nuestra respuesta será $k+1$ ) ya que entonces podemos volver repetidamente de $N$ a $\text{N}-1$ y de vuelta a $\text{N}$ en un número par de pasos. Ahora bien, si la distancia que queda es impar, hacemos exactamente lo mismo, y dependiendo de la paridad de $k$ la respuesta será $k+2$ o $k+3$ . Pero la cuestión es que cuando la distancia que queda $(k+1 - (N - S))$ es impar, no tengo un razonamiento lo suficientemente bueno como para concluir que "eso" es la respuesta. Sólo tengo eso como límite superior y $k+1$ el límite inferior, nada más.

Reescribir cada movimiento $j$ como $a_j + b_j = j$ (ambas no negativas) de manera que el problema puede reescribirse como : Encuentre el menor $j \in \mathbb{N}$ tal que $\sum(a_j) + \sum(b_j) = N$ con sujeción a $0 \leq \max(|a_j|, |b_j|) \leq j$ .

¿Puedo obtener una prueba sólida de esto?

Answer 1

El caso restante es que todo lo siguiente es cierto:

1. $S:= 1 + 2 + \cdots + k < N$ ,
2. $S+(k+1) > N$ y
3. $S+(k+1) - N$ es impar

Condición $3$ significa $S+(k+1)$ y $N$ están en diferente paridad,

$$S+(k+1) \not\equiv N \pmod 2$$

por lo que el número mínimo de movimientos es estrictamente mayor que $k+1$ .

Entonces hay dos casos que dependen de la paridad de $k+2$ :

---

Si $k+2\equiv 0 \pmod 2$ entonces

$$S+(k+1)+(k+2)\not\equiv N\pmod 2$$

por lo que el número mínimo de movimientos sigue siendo estrictamente mayor que $k+2$ . Pero teniendo en cuenta la $(k+3)$ de la mudanza,

$$\begin{align*} (k+2)+(k+3) &\equiv 1 \pmod 2\\ S+(k+1)+(k+2)+(k+3) &\equiv N \end{align*}$$

En caso contrario, si $k+2 \equiv 1\pmod 2$ entonces

$$S+(k+1)+(k+2) \equiv N \pmod 2$$

---

Esto demuestra que el número mínimo de movimientos que coincide con la paridad de $N$ es $k+2$ o $k+3$ (dependiendo de la paridad de $k$ ), y esto rechaza $k+1$ como respuesta.