Dotrzyj na N z $0$ w najmniejszej liczbie ruchów, gdzie n-ty ruch składa się z n kroków, a każdy krok to $\pm 1$ ruch

Jan 01 2021

Osiągnij numer $\text{N}$ od $0$ w najmniejszej liczbie ruchów, w których $n\text{th}$ ruch składa się z $n$ wiele kroków, a każdy krok to $\pm 1$ruch. Ten sam problem istnieje również tutaj bez dowodu.

Przypuszczać $k$ to największa taka liczba $S :=1 + 2 + \cdots + k \leq \text{N}$. Jeśli to równa się$\text{N}$ Skończyliśmy i jeśli pozostała odległość po przejściu z $S$ do $N$ jest równy, nadal jesteśmy skończeni (i nasza odpowiedź będzie $k+1$), ponieważ możemy wtedy wielokrotnie wracać z $N$ do $\text{N}-1$ iz powrotem do $\text{N}$w parzystej liczbie kroków. Teraz, jeśli pozostała odległość jest nieparzysta, robimy dokładnie to samo, w zależności od parzystości$k$, odpowiedź będzie $k+2$ lub $k+3$. Ale chodzi o to, kiedy pozostała odległość$(k+1 - (N - S))$to dziwne, nie mam wystarczającego uzasadnienia, aby stwierdzić, że „to” jest odpowiedzią. Mam tylko to jako górną granicę i$k+1$ dolna granica nic więcej.

Przepisz każdy ruch $j$ tak jak $a_j + b_j = j$(obie nieujemne) tak, aby problem można było przepisać jako: Znajdź najmniej$j \in \mathbb{N}$ takie że $\sum(a_j) + \sum(b_j) = N$ z zastrzeżeniem $0 \leq \max(|a_j|, |b_j|) \leq j$.

Czy mogę uzyskać na to solidny dowód?

Odpowiedzi

peterwhy Jan 01 2021 at 22:19

Pozostały przypadek jest taki, że wszystkie poniższe są prawdziwe:

  1. $S:= 1 + 2 + \cdots + k < N$,
  2. $S+(k+1) > N$ i
  3. $S+(k+1) - N$ to jest dziwne

Stan: schorzenie $3$ znaczy $S+(k+1)$ i $N$ mają różne parytety,

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

a więc minimalna liczba ruchów jest ściśle większa niż $k+1$.

Następnie są dwa przypadki w zależności od parytetu $k+2$:


Jeśli $k+2\equiv 0 \pmod 2$, następnie

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

więc minimalna liczba ruchów jest nadal ściśle większa niż $k+2$. Ale biorąc pod uwagę$(k+3)$ruch,

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

W przeciwnym razie, jeśli $k+2 \equiv 1\pmod 2$, następnie

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


To pokazuje, że minimalna liczba ruchów, która odpowiada parzystości $N$ jest $k+2$ lub $k+3$ (w zależności od parytetu $k$), a to odrzuca $k+1$ jako odpowiedź.