Atteindre N à partir de $0$ dans le plus petit nombre de mouvements où le nième mouvement comprend n étapes et chaque étape est un $\pm 1$ mouvement

Question

Atteignez le nombre $\text{N}$ de $0$ dans le plus petit nombre de coups où le $n\text{th}$ déménagement comprend $n$ plusieurs étapes et chaque étape est un $\pm 1$mouvement. Le même problème existe également ici sans preuve.

Supposer $k$ est le plus grand nombre tel que $S :=1 + 2 + \cdots + k \leq \text{N}$. Si c'est égal$\text{N}$ nous avons terminé et si la distance restante après être parti $S$ à $N$ est égal, nous avons encore terminé (et notre réponse sera $k+1$) puisque nous pouvons alors revenir de manière répétitive $N$ à $\text{N}-1$ et retour à $\text{N}$en un nombre pair d'étapes. Maintenant, si la distance à gauche est bizarre, nous faisons exactement la même chose, et en fonction de la parité de$k$, la réponse sera $k+2$ ou $k+3$. Mais le fait est, quand la distance à gauche$(k+1 - (N - S))$C'est bizarre, je n'ai pas un raisonnement assez bon pour conclure que «ça» est la réponse. Je n'ai que cela comme limite supérieure et$k+1$ la borne inférieure, rien de plus.

Réécrivez chaque mouvement $j$ comme $a_j + b_j = j$(tous deux non négatifs) de telle sorte que le problème puisse être réécrit comme suit : Trouvez le moins$j \in \mathbb{N}$ tel que $\sum(a_j) + \sum(b_j) = N$ sujet à $0 \leq \max(|a_j|, |b_j|) \leq j$.

Puis-je en avoir une preuve solide?

Answer 1

Le cas restant est que tout ce qui suit est vrai:

1. $S:= 1 + 2 + \cdots + k < N$,
2. $S+(k+1) > N$ et
3. $S+(k+1) - N$ est impair

État $3$ veux dire $S+(k+1)$ et $N$ sont de parité différente,

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

et donc le nombre minimum de coups est strictement supérieur à $k+1$.

Ensuite, il y a deux cas selon la parité de $k+2$:

---

Si $k+2\equiv 0 \pmod 2$, puis

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

donc le nombre minimum de coups est toujours strictement supérieur à $k+2$. Mais compte tenu du$(k+3)$ème déménagement,

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

Sinon si $k+2 \equiv 1\pmod 2$, puis

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

---

Cela montre que le nombre minimum de coups correspondant à la parité de $N$ est $k+2$ ou $k+3$ (en fonction de la parité de $k$), et cela rejette $k+1$ comme réponse.