Đạt N từ $0$ trong số lần di chuyển ít nhất trong đó nước đi thứ n bao gồm n bước và mỗi bước là một $\pm 1$ chuyển động

Question

Tiếp cận số $\text{N}$ từ $0$ trong số lần di chuyển ít nhất, nơi $n\text{th}$ di chuyển bao gồm $n$ nhiều bước và mỗi bước là một $\pm 1$chuyển động. Vấn đề tương tự cũng tồn tại ở đây mà không có bằng chứng.

Giả sử $k$ là con số lớn nhất như vậy $S :=1 + 2 + \cdots + k \leq \text{N}$. Nếu nó bằng$\text{N}$ chúng tôi đã hoàn thành và nếu khoảng cách còn lại sau khi đi từ $S$ đến $N$ thậm chí, chúng tôi vẫn đang hoàn thành (và câu trả lời của chúng tôi sẽ là $k+1$) vì sau đó chúng ta có thể lặp lại từ $N$ đến $\text{N}-1$ và trở lại $\text{N}$theo một số bước chẵn. Bây giờ nếu khoảng cách bên trái là số lẻ, chúng tôi làm điều tương tự và tùy thuộc vào độ chẵn lẻ của$k$, câu trả lời sẽ là $k+2$ hoặc là $k+3$. Nhưng vấn đề là, khi khoảng cách còn lại$(k+1 - (N - S))$là kỳ quặc, tôi không có một lý do đủ tốt để kết luận rằng "nó" là câu trả lời. Tôi chỉ có đó là giới hạn trên và$k+1$ giới hạn dưới, không có gì hơn.

Viết lại mọi chuyển động $j$ như $a_j + b_j = j$(cả hai đều không âm) để bài toán có thể được viết lại thành: Tìm ít nhất$j \in \mathbb{N}$ như vậy mà $\sum(a_j) + \sum(b_j) = N$ tùy thuộc vào $0 \leq \max(|a_j|, |b_j|) \leq j$.

Tôi có thể có được một bằng chứng chắc chắn cho điều này?

Answer 1

Trường hợp còn lại là tất cả những điều sau đây đều đúng:

1. $S:= 1 + 2 + \cdots + k < N$,
2. $S+(k+1) > N$ và
3. $S+(k+1) - N$ là số lẻ

Điều kiện $3$ có nghĩa $S+(k+1)$ và $N$ ở mức tương đương khác nhau,

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

và do đó, số lần di chuyển tối thiểu lớn hơn $k+1$.

Sau đó, có hai trường hợp tùy thuộc vào tính chẵn lẻ của $k+2$:

---

Nếu $k+2\equiv 0 \pmod 2$, sau đó

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

vì vậy số lần di chuyển tối thiểu vẫn lớn hơn $k+2$. Nhưng xem xét$(k+3)$di chuyển,

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

Ngược lại nếu $k+2 \equiv 1\pmod 2$, sau đó

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

---

Điều này cho thấy rằng số lần di chuyển tối thiểu phù hợp với tính chẵn lẻ của $N$ Là $k+2$ hoặc là $k+3$ (tùy thuộc vào sự ngang bằng của $k$), và điều này từ chối $k+1$ như câu trả lời.