2
$\begingroup$

I am trying to solve the following problem:

Let's say a "frog" is jumping on the numberline starting at $0$, jumps randomly on every integer from $1,\dots,n$ and then comes back to 0. What is the longest possible distance it can cover for a given $n$?

As an example the case where $n=3$, the longest walk the "frog" can take can be expressed as follows: $$0\to2\to3\to1\to0$$ the maximal covered distance in this case is $2+|2-3|+|3-1|+1=8$. In general, I will express these random walks as $0a_1a_2\dots a_n0$ where each $a_i\in{1,\dots, n}$ is distict, the walk in the example can then be expressed as $02310$. The problem asks to maximize the quantity $L:=a_1+|a_1-a_2|+\dots +|a_{n-1}-a_n|+a_n$.

I was not able to find the complete proof of this result, however I was able to find an equivalent problem, that could possibly be easier to solve. I am going to explain my proof with $n=5$, but the same logic can be applied for any $n$. I came up with the following diagramm, here the $y$ coordinates of the points are the elements of the sequence from $1,...,5$ from left to right, the corresponding sequence in the example is $0415230$. I then proceeded to calculate the area under the graph in two ways. First I calculated the area as the sum of areas of the green triangles, $A_1$, and the red rectangles, $A_2$, on the diagramm. The calculation is a bit complicated to explain but can be seen from the diagramm (in every triangle one of the legs is equal to 1, and so is one of the sides in every rectangle). In general: $$A_1=\frac{1}{2}⋅ 1⋅a_1+\frac{1}{2}⋅1⋅|a_1-a_2|+\dots+\frac{1}{2}⋅1⋅a_n=\frac{1}{2}L$$ and $$A_2=a_1+\min(a_1,a_2)+\min(a_2,a_3)+\dots+a_n:=B$$ So the overall area under the graph is equal to $A=A_1+A_2=\frac{1}{2}L+B$. And now we calculate the area the second way using the trapesoids as seen here. Then: $$A=\frac{a_1}{2}+\frac{a_1+a_2}{2}+\dots+\frac{a_{n-1}+a_n}{2}+\frac{a_n }{2}=$$ $$=a_1+a_2+a_3+\dots + a_n=\frac{n(n+1)}{2}$$ So we get $$\frac{1}{2}L+B=\frac{n(n+1)}{2}$$ for any randomly chosen sequence of $a_i$'s. If we rearrange for $L$ we get $L=n(n+1)-2B$. So the problem of maximizing $L$ can now be restated as the problem of minimizing $B$, where $$B:=a_1+\min(a_1,a_2)+\min(a_2,a_3)+\dots+a_n$$ Other than that I found the maximal values of $L$ for $n=1,2,3,4$ which are $2,4,8,12$ respectively. These numbers hint on the fact that if there is a general polynomial formula for $\max(L)$ in terms of $n$ then it is a polynomial of degree $\ge 3$. However I sadly couldn't proceed anywhere further from this. The problem of minimizing $B$ seems way simpler than the original one, but I do not have any ideas on how to go about proving it as well. I would greatly appreciate any help or reference to this problem!

$\endgroup$
6
  • 5
    $\begingroup$ There is nothing random in your problem. You want to maximize the length among all possible paths. Do you get longer than the greedy solution $0,n,1,n-1,\dots,\lceil\frac n2\rceil$? $\endgroup$ Commented Nov 29 at 21:51
  • 2
    $\begingroup$ $2+|2-3|+|3-1|+1$ is six, not eight. $0\to3\to1\to2\to0$ is eight. $\endgroup$ Commented Nov 29 at 23:25
  • 2
    $\begingroup$ I changed the title in something that is more likely to pop up in search engines if someone look for similar problems $\endgroup$ Commented Nov 30 at 0:08
  • 1
    $\begingroup$ Mathematics Magazine Problem 1654 jstor.org/stable/3219092 $\endgroup$ Commented Nov 30 at 0:10
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/4372504/… $\endgroup$ Commented Nov 30 at 0:13

2 Answers 2

Reset to default
4
$\begingroup$

If we call the sequence $$ 0=x_0, x_1 \cdots , x_n,x_{n+1}=0 $$ then one can think to the sequence as a graph with edges $(x_i,x_{i+1})$ $$ L= \sum_{i=0}^n |x_{i+1}-x_i| $$

for $k=0,1 \cdots n-1$ define $C_k$ as the number of edges $(a,b)$ such that $a \le k,b \ge k+1$. We want to prove that $$ L= \sum_{k=0}^{n-1} C_k $$

Notice how any edge $(x_i,x_{i+1})$ contribute $1$ to each $C_k$ such that $k \in [\min(x_i,x_{i+1}),\max(x_i,x_{i+1})-1]$ and $0$ to all the other $C_k$.

As it is possible to write $$ |x_{i+1}-x_i| = \sum_{\min(x_i,x_{i+1})}^{\max(x_i,x_{i+1})-1} 1 $$ The equation immediatly follows

Now we want to prove that $$ C_k \le 2 \min(k+1,n-k) $$ THis is immediate if we divide the number line in 2 sections $A=(0,\cdots k)$ and $B=(k+1,\cdots n)$. Each vertex contribute at most at $2$ to each $C_k$ (one when the frog land and one when the frog depart) and for an edge to contribute $1$ it need to take one element from $A$ and $1$ from $B$, thus the minimum

$$ L \le \sum_{k=0}^{n-1}2 \min(k+1,n-k) $$ If $n=2m$ is even, then \begin{align} \sum_{k=0}^{2m-1} \min(k+1,2m-k)&= \sum_{k=0}^{m-1} k+1 + \sum_{k=m}^{2m-1} 2m-k\\ & =2\sum_{j=1}^m j=m(m+1) \end{align} If $n=2m+1$ odd \begin{align} \sum_{k=0}^{2m} \min(k+1,2m+1-k)&= \sum_{k=0}^m k+1 + \sum_{k=m+1}^{2m} 2m+1-k\\ & =\sum_{j=1}^{m+1} j + \sum_{j=1}^m j=(m+1)^2 \end{align}

Combining the 2 estimates using the ceiling function we have $$ L \le \frac{n(n+1)}{2}+\left\lceil \frac{n}{2} \right\rceil $$ That is attained by the greedy solution in the comments

$\endgroup$
1
  • 1
    $\begingroup$ Wow, thank you very much, it is a beutiful solution! $\endgroup$ Commented 2 days ago
0
$\begingroup$

We wish to maximise the sum: $$\sum_{i=0}^n |x_i-x_{i+1}|,$$ where $x_0=x_{n+1}=0$, and $(x_1,\cdots,x_n)$ is a permutation of the numbers $1,\cdots,n$. This expression sums each number $1,\cdots,n$ twice, with coefficients $\pm1$, each occurring an equal number of times.

Thus it is optimised when we have coefficients $+1$ on the larger half of the numbers both times and $-1$ on the smaller half of the numbers both times. If $n$ even, then we will have both coefficients $+1$ and $-1$ on the middle number $n/2$.

When $n$ odd, this is achieved if every jump goes between the top half and the bottom half. When $n$ even, there will additionally be one jump between the top half and the middle number, and one between the middle number and the top half.

An example of such a sequence is alternating between highest available values and lowest e.g. for $n=7$: $071625340$ or for $n=8$: $0817263540$.

For $n$ odd, there are $\frac{n+1}{2}$ numbers in the top half, each $\frac{n+1}{2}$ above a corresponding number in the bottom half, so our sum comes to $$2\left(\frac{n+1}{2}\right)^2=\frac{(n+1)^2}{2}.$$

For $n$ even, there are $\frac{n}{2}$ numbers in the top half, each $\frac{n}{2}+1$ above a corresponding number in the bottom half, so our sum comes to $$2\left(\frac{n}{2}\right)\left(\frac{n}{2}+1\right)=\frac{(n+1)^2-1}{2}.$$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.