A man has to paint n consecutive mile posts and wants to do this as inefficiently as possible... 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 $n=5$, and if $n=13$?
Can you generalise this to any $n$?

Hello everyone. I've done a lot with this one. The largest number I can get for the $n=5$ case is $10$, and $78$ for the $n=13$ case, using the equation $n(n-1)/2$, which is just from the sum of natural numbers.
It can also be shown using induction that this can be generalised to any n.
My problem is, how can I prove that this is truly the least efficient way of doing things? I can clearly see that there is no better option, but I'm not sure how to project that mathematically.
Thank you.
 A: The first step would be to convert your statements into a mathematical statement that we can manipulate.
Let the man paint posts $a_1, a_2, a_3, \ldots, a_n$ in that order. Then, the number of steps that he would take between posts $a_i$ and $a_{i+1}$ is $|a_i - a_{i+1}|$. Hence, the total number of steps is
$$ \sum_{i=1}^{n-1} | a_i - a_{i+1} | $$
Now, when we expand each individual absolute value term, we will either get $a_i - a_{i+1}$ or $a_{i+1} - a_i$.
Claim: $$ |a_n-a_1| + \sum_{i=1}^{n-1} | a_i - a_{i+1} |  = \sum k_i a_i$$
where $k_i \in \{ -2, 0, 2\}$ and $\sum k_i = 0 $.
The proof is left to you, and should be obvious.
Now, if we wish to maximize this sum (i.e.  most inefficient), it is clear that this is maximal when $k_i = 2$ for large values of $a_i$ and $k_i = -2$ for small values of $a_i$. In particular,
$$ k_i = \begin{cases} -2 & a_i\leq \frac {n+1}{2} \\ 0 & a_i = \frac {n+1} {2} \\ 2 & a_i > \frac {n+1}{2} \end{cases}.$$
I leave it to you to verify that with these coefficients, you would get a sum of $2\lfloor \frac {n}{2} \rfloor \lceil \frac {n}{2} \rceil$.
Hence,
$$ \sum_{i=1}^{n-1} | a_i - a_{i+1} | \leq 2n - | a_{n} - a_{1} | \leq 2\lfloor \frac {n}{2} \rfloor \lceil \frac {n}{2} \rceil-1 $$
It remains to verify that this can actually be achieved. If you understand what has been happening above, you should be able to quickly construct an example walk with this length.
Hint: What must the starting and ending posts be? How does he walk?

From the construction of the inequality, we know that we want to alternate back and forth between posts of value $\leq \frac {n+1}{2}$ and posts of value $\geq \frac {n+1}{2}$. We also want $|a_n - a_1| = 1$. We provide a construction as follows:
For even $n=2k$, paint posts
$$k+1, 1, 2k, 2, 2k-1, \ldots, k-2, k+3, k-1, k+2, k.$$
For odd $n=2k+1$, pain posts
$$k+1, 1, 2k+1, 2, 2k, \ldots, k-2, k+4, k-1, k+3, k, k+2.$$
Note that, with the exception of the starting and ending posts, we can permute the positions of the posts, as long as their new position has the same parity.
A: If he paints $3,5,1,4,2$ he walks $11.$  To prove this is maximal, you can only cover the segment from $1$ to $2$ twice, once to go to $1$ and once to leave.  You can cover the segment from $2$ to $3$ four times, once round trip to $1$ and one round trip to $2.$  By symmetry, you can only cover $12$ segments.  But you can't get them all or you would have a full circuit and presumably you painted a post the first time (before walking any) and don't have to go back to it.  Similarly for $13$, he can go $7,1,13,2,12,3,11,4,10,5,9,6,8$ for $83$ total.
A: n=5
(1) (2) (3) (4) (5)
Visit start = n+1 / 2 (round down)
Visit path = start => (nmax => nmin) loop.
3 -> 5 -> 1 -> 4 -> 2
2 + 4 + 3 + 2 = 11
A0 = (Vn - Vstart) 5-3
A1 = A0 + (Vn - V0) ^ + 5-1
A2 = A1 + (Vn-1 - V0) ^ + 4-1
A3 = A2 + (Vn-1 - V1) ^ + 4-2
A0 = 2
A1 = 4
A2 = 3
A3 = 2
n = 5 implies $\sum_{i=0}^3 Ai = \ 11$
What is left from here is to generalize An
For n = n where $\sum_{i=0}^n Ai \ $
