Достичь N от $0$ при наименьшем количестве ходов, где n-й ход состоит из n шагов, и каждый шаг является $\pm 1$ движение
Набери номер $\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$.
Могу я получить этому убедительное доказательство?
Ответы
В остальном случае справедливо все следующее:
- $S:= 1 + 2 + \cdots + k < N$,
- $S+(k+1) > N$ и
- $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$ как ответ.