Jangkau N dari $0$ dalam jumlah langkah paling sedikit di mana langkah ke-n terdiri dari n langkah dan setiap langkah adalah a $\pm 1$ gerakan

Question

Hubungi nomornya $\text{N}$ dari $0$ dalam jumlah langkah paling sedikit di mana $n\text{th}$ bergerak terdiri dari $n$ banyak langkah dan setiap langkah adalah a $\pm 1$gerakan. Masalah yang sama juga ada di sini tanpa bukti.

Seharusnya $k$ adalah bilangan terbesar sedemikian rupa $S :=1 + 2 + \cdots + k \leq \text{N}$. Jika itu sama$\text{N}$ kita selesai dan jika jarak tersisa setelah pergi dari $S$ untuk $N$ adalah genap, kita masih selesai (dan jawaban kita adalah $k+1$) karena kita dapat kembali secara berulang-ulang $N$ untuk $\text{N}-1$ dan kembali ke $\text{N}$dalam jumlah langkah genap. Sekarang jika jarak kiri ganjil, kita melakukan hal yang persis sama, dan bergantung pada paritas$k$, jawabannya adalah $k+2$ atau $k+3$. Tapi intinya adalah, saat jarak pergi$(k+1 - (N - S))$Aneh, saya tidak memiliki alasan yang cukup baik untuk menyimpulkan bahwa "itu" adalah jawabannya. Saya hanya memiliki itu sebagai batas atas dan$k+1$ batas bawah, tidak lebih.

Tulis ulang setiap gerakan $j$ sebagai $a_j + b_j = j$(keduanya non-negatif) sehingga masalah dapat ditulis ulang sebagai: Temukan yang paling sedikit$j \in \mathbb{N}$ seperti yang $\sum(a_j) + \sum(b_j) = N$ tunduk pada $0 \leq \max(|a_j|, |b_j|) \leq j$.

Bolehkah saya mendapatkan bukti kuat untuk ini?

Answer 1

Kasus yang tersisa adalah bahwa semua hal berikut ini benar:

1. $S:= 1 + 2 + \cdots + k < N$,
2. $S+(k+1) > N$ dan
3. $S+(k+1) - N$ aneh

Kondisi $3$ cara $S+(k+1)$ dan $N$ berada di paritas yang berbeda,

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

dan jumlah gerakan minimum benar-benar lebih besar dari $k+1$.

Lalu ada dua kasus tergantung pada paritas $k+2$:

---

Jika $k+2\equiv 0 \pmod 2$, kemudian

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

jadi jumlah gerakan minimum masih lebih besar dari $k+2$. Tapi mengingat$(k+3)$langkah ke,

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

Sebaliknya jika $k+2 \equiv 1\pmod 2$, kemudian

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

---

Ini menunjukkan bahwa jumlah gerakan minimum yang cocok dengan paritas $N$ aku s $k+2$ atau $k+3$ (tergantung pada paritas $k$), dan ini menolak $k+1$ sebagai jawabannya.