Alcance N de $0$ no menor número de movimentos, onde o enésimo movimento compreende n passos e cada passo é um $\pm 1$ movimento

Question

Alcance o número $\text{N}$ a partir de $0$ no menor número de movimentos onde o $n\text{th}$ mover é composto por $n$ muitas etapas e cada etapa é um $\pm 1$movimento. O mesmo problema também existe aqui sem uma prova.

Suponha $k$ é o maior número tal que $S :=1 + 2 + \cdots + k \leq \text{N}$. Se for igual$\text{N}$ terminamos e se a distância que resta depois de ir de $S$ para $N$ é mesmo, ainda estamos prontos (e nossa resposta será $k+1$), pois podemos, então, voltar repetidamente de $N$ para $\text{N}-1$ e de volta para $\text{N}$em um número par de etapas. Agora, se a distância restante for ímpar, fazemos exatamente a mesma coisa, e dependendo da paridade de$k$, a resposta será $k+2$ ou $k+3$. Mas o ponto é, quando a distância sobrou$(k+1 - (N - S))$é estranho, não tenho um raciocínio bom o suficiente para concluir que "isso" é a resposta. Eu só tenho isso como o limite superior e$k+1$ o limite inferior, nada mais.

Reescrever cada movimento $j$ Como $a_j + b_j = j$(ambos não negativos) de modo que o problema possa ser reescrito como: Encontre o mínimo$j \in \mathbb{N}$ de tal modo que $\sum(a_j) + \sum(b_j) = N$ sujeito a $0 \leq \max(|a_j|, |b_j|) \leq j$.

Posso obter uma prova sólida disso?

Answer 1

O caso restante é que todos os seguintes são verdadeiros:

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

Doença $3$ significa $S+(k+1)$ e $N$ estão em paridade diferente,

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

e assim o número mínimo de movimentos é estritamente maior do que $k+1$.

Então, há dois casos, dependendo da paridade de $k+2$:

---

E se $k+2\equiv 0 \pmod 2$, então

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

então o número mínimo de movimentos ainda é estritamente maior do que $k+2$. Mas considerando o$(k+3)$o movimento,

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

Caso contrário, se $k+2 \equiv 1\pmod 2$, então

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

---

Isso mostra que o número mínimo de movimentos que corresponde à paridade de $N$ é $k+2$ ou $k+3$ (dependendo da paridade de $k$), e isso rejeita $k+1$ como a resposta.