से एन तक पहुँचें $0$ कम से कम चालों में जहां n'th चाल में n चरण शामिल हैं और प्रत्येक चरण a है $\pm 1$ आंदोलन

Jan 01 2021

संख्या पर पहुँचें $\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$

क्या मुझे इसके लिए कोई ठोस सबूत मिल सकता है?

जवाब

peterwhy Jan 01 2021 at 22:19

शेष मामला यह है कि निम्नलिखित सभी सत्य हैं:

  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$ उत्तर के रूप में।