Alcance N desde $0$ en el menor número de movimientos donde el n-ésimo movimiento consta de n pasos y cada paso es un $\pm 1$ movimiento

Question

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

Suponer $k$ es el mayor número tal que $S :=1 + 2 + \cdots + k \leq \text{N}$. Si es igual$\text{N}$ hemos terminado y si la distancia se fue después de ir de $S$ a $N$ es incluso, todavía hemos terminado (y nuestra respuesta será $k+1$) ya que luego podemos volver repetidamente desde $N$ a $\text{N}-1$ y de regreso a $\text{N}$en un número par de pasos. Ahora, si la distancia que queda es impar, hacemos exactamente lo mismo, y dependiendo de la paridad de$k$, la respuesta sera $k+2$ o $k+3$. Pero el punto es, cuando la distancia se fue$(k+1 - (N - S))$Es extraño, no tengo un razonamiento lo suficientemente bueno para concluir que "eso" es la respuesta. Solo tengo eso como límite superior y$k+1$ el límite inferior, nada más.

Reescribe cada movimiento $j$ como $a_j + b_j = j$(ambos no negativos) de modo que el problema pueda reescribirse como: Encuentre el mínimo$j \in \mathbb{N}$ tal que $\sum(a_j) + \sum(b_j) = N$ sujeto 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$ medio $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$.

Luego hay dos casos dependiendo 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 considerando el$(k+3)$th movimiento,

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

De lo contrario si $k+2 \equiv 1\pmod 2$, entonces

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

---

Esto muestra 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 la respuesta.