How can we prove this for n=5, 13 and any values?

Question

A man has to paint n consecutive mile posts and wants to do this as inefficiently as possible - So that he walks as far as possible from the first post he paints to the last post he paints. He can only turn around and go back the other way immediately after painting a post, and each post can only be painted once. How should he do this if =5, and if =13?

Can you generalise this to any ?

I know we have to work from the middle post and then go to first last second second last and so on. But how would i write a proof for this?

Answer 1

Let the posts be painted in the sequence $a_1, a_2, \ldots a_n$.

The distance that he walks is

$$|a_1 - a_2 | + | a_2 - a_3| + \ldots | a_n - a_{n-1}|. $$

This can be expressed as
$$\sum_{i=1}^n |a_i - a_{i+1} | = \sum_{i=1}^{n-1} \pm a_i + \sum_{i=2}^n \pm a_i.$$

with the following conditions:

1. There are $n-1$ + signs and $n-1$ - signs.
2. $a_i$ is negative iff $a_{i+1}$ is positive and $ ai < a_{i+1}$

For now, ignoring the second condition, we see that the maximum value is achieved at:

$$ -2 \times 1 -2 \times 2 -2 \times 3 +\ldots \text{check the middle} + \ldots + 2 \times (n-1) + 2 \times (n). $$

Now, is there a rearrangement of $ \{ 1, 2, \ldots n-1, n \}$ that will allow us to achieve this maximum?