Erreichen Sie N von $0$ in der geringsten Anzahl von Zügen, wobei der n-te Zug aus n Schritten besteht und jeder Schritt a ist $\pm 1$ Bewegung

Jan 01 2021

Erreichen Sie die Nummer $\text{N}$ von $0$ in der geringsten Anzahl von Zügen, in denen die $n\text{th}$ Umzug besteht aus $n$ viele Schritte und jeder Schritt ist ein $\pm 1$Bewegung. Das gleiche Problem besteht auch hier ohne Beweis.

Annehmen $k$ ist die größte Zahl, so dass $S :=1 + 2 + \cdots + k \leq \text{N}$. Wenn es gleich ist$\text{N}$ Wir sind fertig und wenn die Entfernung nach dem Verlassen von $S$ zu $N$ ist gerade, wir sind noch fertig (und unsere Antwort wird sein $k+1$) da wir dann immer wieder von zurückgehen können $N$ zu $\text{N}-1$ und zurück zu $\text{N}$in einer geraden Anzahl von Schritten. Wenn der verbleibende Abstand ungerade ist, machen wir genau das Gleiche und abhängig von der Parität von$k$wird die Antwort sein $k+2$ oder $k+3$. Aber der Punkt ist, wenn die Entfernung übrig ist$(k+1 - (N - S))$ist seltsam, ich habe nicht genug Gründe, um zu dem Schluss zu kommen, dass "es" die Antwort ist. Ich habe das nur als Obergrenze und$k+1$ die Untergrenze, nichts weiter.

Schreiben Sie jede Bewegung neu $j$ wie $a_j + b_j = j$(beide nicht negativ), sodass das Problem wie folgt umgeschrieben werden kann: Finden Sie das Wenigste$j \in \mathbb{N}$ so dass $\sum(a_j) + \sum(b_j) = N$ vorbehaltlich $0 \leq \max(|a_j|, |b_j|) \leq j$.

Darf ich einen soliden Beweis dafür bekommen?

Antworten

peterwhy Jan 01 2021 at 22:19

Der verbleibende Fall ist, dass alle der folgenden Aussagen zutreffen:

  1. $S:= 1 + 2 + \cdots + k < N$,
  2. $S+(k+1) > N$ und
  3. $S+(k+1) - N$ ist ungerade

Bedingung $3$ meint $S+(k+1)$ und $N$ sind in unterschiedlicher Parität,

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

und so ist die minimale Anzahl von Zügen streng größer als $k+1$.

Dann gibt es zwei Fälle, abhängig von der Parität von $k+2$::


Wenn $k+2\equiv 0 \pmod 2$, dann

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

Die Mindestanzahl an Zügen ist also immer noch streng größer als $k+2$. Aber angesichts der$(k+3)$th Bewegung,

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

Ansonsten wenn $k+2 \equiv 1\pmod 2$, dann

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


Dies zeigt, dass die Mindestanzahl von Zügen der Parität von entspricht $N$ ist $k+2$ oder $k+3$ (abhängig von der Parität von $k$), und dies lehnt ab $k+1$ als Antwort.