다음에서 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$.

그런 다음 패리티에 따라 두 가지 경우가 있습니다. $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$ 대답으로.