เข้าถึง N จาก $0$ ในจำนวนการเคลื่อนไหวน้อยที่สุดโดยที่การเคลื่อนไหวที่ n ประกอบด้วย n ขั้นตอนและแต่ละขั้นตอนคือก $\pm 1$ การเคลื่อนไหว
ถึงหมายเลข $\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$.
ฉันขอหลักฐานที่มั่นคงสำหรับเรื่องนี้ได้ไหม
คำตอบ
กรณีที่เหลือคือทั้งหมดต่อไปนี้เป็นจริง:
- $S:= 1 + 2 + \cdots + k < N$,
- $S+(k+1) > N$ และ
- $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$ เป็นคำตอบ