Raggiungi N da $0$ nel minor numero di mosse in cui la nesima mossa comprende n passi e ogni passo è a $\pm 1$ movimento

Question

Raggiungi il numero $\text{N}$ a partire dal $0$ nel minor numero di mosse in cui il $n\text{th}$ mossa comprende $n$ molti passaggi e ogni passaggio è un file $\pm 1$movimento. Lo stesso problema esiste anche qui senza una prova.

Supponiamo $k$ è il numero più grande tale che $S :=1 + 2 + \cdots + k \leq \text{N}$. Se è uguale a$\text{N}$ abbiamo finito e se la distanza lasciata dopo essere passati da $S$ per $N$ è pari, abbiamo ancora finito (e la nostra risposta sarà $k+1$) poiché possiamo poi tornare indietro ripetutamente da $N$ per $\text{N}-1$ e di nuovo a $\text{N}$in un numero pari di passaggi. Ora, se la distanza rimanente è dispari, facciamo la stessa identica cosa e in base alla parità di$k$, la risposta sarà $k+2$ o $k+3$. Ma il punto è, quando la distanza a sinistra$(k+1 - (N - S))$è strano, non ho un ragionamento abbastanza valido per concludere che "è" la risposta. Ho solo quello come limite superiore e$k+1$ il limite inferiore, niente di più.

Riscrivi ogni mossa $j$ come $a_j + b_j = j$(entrambi non negativi) in modo che il problema possa essere riscritto come: Trova il minimo$j \in \mathbb{N}$ tale che $\sum(a_j) + \sum(b_j) = N$ soggetto a $0 \leq \max(|a_j|, |b_j|) \leq j$.

Posso avere una prova solida per questo?

Answer 1

Il caso rimanente è che tutte le seguenti condizioni sono vere:

1. $S:= 1 + 2 + \cdots + k < N$,
2. $S+(k+1) > N$ e
3. $S+(k+1) - N$ è strano

Condizione $3$ si intende $S+(k+1)$ e $N$ sono in parità diversa,

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

e quindi il numero minimo di mosse è strettamente maggiore di $k+1$.

Poi ci sono due casi a seconda della parità di $k+2$:

---

Se $k+2\equiv 0 \pmod 2$, poi

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

quindi il numero minimo di mosse è ancora strettamente maggiore di $k+2$. Ma considerando il$(k+3)$th mossa,

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

Altrimenti se $k+2 \equiv 1\pmod 2$, poi

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

---

Questo mostra che il numero minimo di mosse che corrisponde alla parità di $N$ è $k+2$ o $k+3$ (a seconda della parità di $k$), e questo rifiuta $k+1$ come risposta.