N'ye ulaş $0$ n'inci hareketin n adımdan oluştuğu ve her adımın bir $\pm 1$ hareket

Question

Numaraya ulaşın $\text{N}$ itibaren $0$ en az hamle sayısında $n\text{th}$ hareket içerir $n$ birçok adım ve her adım bir $\pm 1$hareket. Aynı sorun burada da kanıt olmadan var .

Varsayalım $k$ en büyük sayıdır öyle ki $S :=1 + 2 + \cdots + k \leq \text{N}$. Eşitse$\text{N}$ Bitirdik ve gittikten sonra kalan mesafe $S$ -e $N$ eşit, hala bitirdik (ve cevabımız olacak $k+1$) çünkü daha sonra tekrar tekrar geri dönebiliriz $N$ -e $\text{N}-1$ ve geri dön $\text{N}$çift ​​sayıda adımda. Şimdi eğer kalan mesafe tuhafsa, aynı şeyi yapıyoruz ve paritesine bağlı olarak$k$cevap olacak $k+2$ veya $k+3$. Ama mesele şu ki, kalan mesafe$(k+1 - (N - S))$tuhaf, cevabın "o" olduğu sonucuna varmak için yeterince iyi bir gerekçem yok. Buna sadece üst sınır olarak sahibim ve$k+1$ alt sınır, daha fazlası değil.

Her hareketi yeniden yazın $j$ gibi $a_j + b_j = j$(ikisi de olumsuz değildir) öyle ki sorun şu şekilde yeniden yazılabilir: En azını bulun$j \in \mathbb{N}$ öyle ki $\sum(a_j) + \sum(b_j) = N$ tabi $0 \leq \max(|a_j|, |b_j|) \leq j$.

Bunun için sağlam bir kanıt alabilir miyim?

Answer 1

Geri kalan durum şudur:

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

Durum $3$ anlamına geliyor $S+(k+1)$ ve $N$ farklı eşitlikte

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

ve bu nedenle minimum hamle sayısı kesinlikle şundan fazladır: $k+1$.

Daha sonra paritesine bağlı olarak iki durum vardır $k+2$:

---

Eğer $k+2\equiv 0 \pmod 2$, sonra

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

bu nedenle minimum hamle sayısı hala kesinlikle daha büyük $k+2$. Ama dikkate alındığında$(k+3)$inci hareket,

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

Aksi takdirde eğer $k+2 \equiv 1\pmod 2$, sonra

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

---

Bu, parite ile eşleşen minimum hamle sayısının $N$ dır-dir $k+2$ veya $k+3$ (paritesine bağlı olarak $k$) ve bu reddeder $k+1$ cevap olarak.