からNに到達 $0$ n番目の移動がnステップで構成され、各ステップが $\pm 1$ 移動

Question

数に達する $\text{N}$ から $0$ 最小の移動数で $n\text{th}$ 移動はで構成されます $n$ 多くのステップと各ステップは $\pm 1$移動。同じ問題が証明なしでここにも存在します。

仮定します $k$ そのような最大数です $S :=1 + 2 + \cdots + k \leq \text{N}$。等しい場合$\text{N}$ 完了し、出発後の距離が残っている場合 $S$ に $N$ でも、私たちはまだ終わっています（そして私たちの答えは $k+1$）その後、繰り返し戻ることができるので $N$ に $\text{N}-1$ に戻る $\text{N}$偶数のステップで。ここで、残りの距離が奇数の場合、まったく同じことを行います。$k$、答えは $k+2$ または $k+3$。しかし、要点は、距離が残ったときです$(k+1 - (N - S))$奇妙なことに、私には「それ」が答えであると結論付けるのに十分な理由がありません。私はそれを上界と下界として持っているだけです$k+1$ 下限、それ以上はありません。

すべての動きを書き直します $j$ なので $a_j + b_j = j$（両方とも非負）問題を次のように書き直すことができるように：最小を見つける$j \in \mathbb{N}$ そのような $\sum(a_j) + \sum(b_j) = N$ 対象 $0 \leq \max(|a_j|, |b_j|) \leq j$。

これについて確かな証拠を得ることができますか？

Answer 1

残りのケースは、次のすべてが当てはまる場合です。

1. $S:= 1 + 2 + \cdots + k < N$、
2. $S+(k+1) > N$ そして
3. $S+(k+1) - N$ 奇妙です

状態 $3$ 手段 $S+(k+1)$ そして $N$ 異なるパリティにあり、

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

したがって、最小移動数は厳密に $k+1$。

次に、のパリティに応じて2つのケースがあります $k+2$：

---

場合 $k+2\equiv 0 \pmod 2$、その後

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

したがって、最小移動数は依然として厳密に $k+2$。しかし、$(k+3)$移動、

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

それ以外の場合 $k+2 \equiv 1\pmod 2$、その後

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

---

これは、のパリティに一致する移動の最小数を示しています $N$ です $k+2$ または $k+3$ （のパリティに応じて $k$）、これは拒否します $k+1$ 答えとして。