Steps Of Increasing Size

For any integer $k \in \mathbb{N}$ with $k \ge 2$ , consider integers $n$ such that $\tfrac12k(k-1) < n \le \tfrac12k(k+1)$ . Since $1 + 2 + 3 + \cdots + (k-1) \; = \; \tfrac12k(k-1)$ we deduce that $m_n > k-1$ , since $n$ is bigger than the largest positive integer that can be reached in $k-1$ steps. On the other hand $\begin{aligned} 1 + 2 + 3 + \cdots + k & = \tfrac12k(k+1) \\ 1 + 2 + \cdots + (j-1) + (-j) + (j+1) + \cdots + k & = \tfrac12k(k+1) - 2j \end{aligned}$ for any $1 \le j \le k$ , and so it is clear that $m_n \le k$ for any $\tfrac12k(k-1) < n \le \tfrac12k(k+1)$ such that $n \equiv \tfrac12k(k+1) \pmod{2}$ . On the other hand $\begin{aligned} 1 + 2 + \cdots + k + (k+1) - (k+2) & = \tfrac12k(k+1) - 1 \\ 1 + 2 + \cdots + (j-1) + (-j) + (j+1) + \cdots + k + (k+1) - (k+2) & = \; \tfrac12k(k+1) - (2j+1) \end{aligned}$ for any $1 \le j \le k$ , and hence $m_n \le k+2$ for all $\tfrac12k(k-1) < n \le \tfrac12k(k+1)$ with $n \not\equiv \tfrac12k(k+1) \pmod{2}$ . In other words $k-1 \; < \; m_n \; \le \; k+2 \hspace{2cm} \tfrac12k(k-1) < n \le \tfrac12k(k+1)$ and hence $\frac{\sqrt{2}(k-1)}{\sqrt{k(k+1)}} \; < \; \frac{m_n}{\sqrt{n}} \; < \; \frac{\sqrt{2}(k+2)}{\sqrt{k(k-1)}} \hspace{2cm} \tfrac12k(k-1) < n \le \tfrac12k(k+1)$ Letting $k \to \infty$ we deduce that $\lim_{n \to \infty} \frac{m_n}{\sqrt{n}} \,=\, \boxed{\sqrt{2}}$ .

The equivalent generating function of "in $k$ th move, I move either $+k$ or $-k$ " is -

$f_n(x) = \prod_{k=1}^n {\left(x^k + x^{-k}\right)}$

such that if we want to reach the number $N$ , then it must be the coefficient of this function, and we have to find minimum such $n$ .

$f_n(x) = \frac{1}{x^{n(n+1)/2}}\prod_{k=1}^n {\left(1 + x^{2k} \right)}$

$f_n(x) = \frac{1}{x^{n(n+1)/2}} \left(1 + x^2 + x^4 + 2x^6 + \cdots + a_n x^{n(n+1)}\right)$

This clearly shows us that we have to minimum $n$ such that $N - \frac{n(n+1)}{2} \geq 0$

$n^2 + n - 2N \geq 0$

$n \geq \frac{-1 + \sqrt{1 + 8N}}{2}$

Hence, $\displaystyle \lim_{n\rightarrow \infty} \frac{m_n}{n} = \lim_{n\rightarrow \infty} \frac{\frac{-1 + \sqrt{1 + 8N}}{2}}{n} = \sqrt{2}$