4

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.

user65132
  • 287
  • Are you assuming he begins painting at post 1? – Jared Mar 21 '13 at 20:44
  • Determining the most efficient way to paint the posts is also an interesting problem. It seems the answer will be $2n-1$, but as you say, how to prove there is nothing better is not immediately clear. – Jared Mar 21 '13 at 20:46
  • @Jared Note, it doesn't say that he must turn around after painting each post. The most efficient would be to paint 1, 2, 3, .... – Calvin Lin Mar 21 '13 at 20:57
  • I did indeed make that stupid assumption of him starting at post 1. – user65132 Mar 21 '13 at 20:59
  • Calvin, the question states 'He can only turn around and go back the other way immediately after painting a post.' Am I interpreting this statement incorrectly? – Jared Mar 21 '13 at 21:09
  • That is, he is only presented with the option of turning around having painted a post, but otherwise must only continue forward. – user65132 Mar 21 '13 at 21:11
  • I see. My mistake! – Jared Mar 21 '13 at 21:14

3 Answers3

3

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.

Calvin Lin
  • 68,864
  • Sorry, what constitutes as a small or large value of $a_i$?

    I don't know if that question makes sense or not.

     – user65132 Mar 21 '13 at 21:32
  • @user65132 I've edited the answer. Remember that $a_i$ denotes a post number. If the post number is less that $\frac {n}{2}$, it is 'small'. – Calvin Lin Mar 21 '13 at 21:37
  • I have a feeling I'm being very slow here, but I'm looking at your first big statement, the 2nd sum with the $k_i$, and I ask myself how $\sum k_i a_i$ can be calculated when all of the $a_i$ are simply named posts, and as far as I can see so far, no one post has a significant numerical value greater or lower than the one before or after it.

    Are my thoughts making any sense here?

     – user65132 Mar 22 '13 at 17:15
  • @user65132 My guess is that you are uncomfortable with the algebra, and uncertain of what it means. Let me give a concrete example. If the posts painted are in the order $( 3, 5, 1, 4, 2)$, then the number of steps taken are $|3-5| + |5-1| + |1-4| + |4-2|$. Do you agree with that? – Calvin Lin Mar 22 '13 at 17:58
  • @user65132 In the next step, I add the term $|a_n - a_1|$ and then expand the terms, while keeping the actual values. I.e., I expand it as $ (3-2) + (5-3) + (5-1) + (4-1) + (4-2) $, instead of evaluating it as $1+2 + 4 + 3 + 2$. With this expansion, I can rewrite it as $ (-2) \times 1 + (-2) \times 2 + (0) \times 3 + 2 \times 4 + 2 \times 5 $, which corresponds to the $\sum k_i a_i$ that I was referring to. – Calvin Lin Mar 22 '13 at 18:00
  • Alright, after some thought, I get what you're trying to tell me here. But the proof for this statement still isn't obvious to me, and, nor is where the sum of $2 \lfloor \frac {n}{2} \rfloor \lceil \frac {n}{2} \rceil$ came from.

    Sorry if you feel like I'm asking for too much, I'm very inexperienced with discrete maths.

     – user65132 Mar 23 '13 at 01:14
  • Have I been abandoned? I hope not. – user65132 Mar 23 '13 at 14:43
  • @user65132 Proof of which statement in particular? They should all be self-explanatory / follows after thinking about the problem in a short while. The sum of $2 \lfloor \frac {n}{2} \rfloor \lceil \frac {n}{2} \rceil$ can be shown through many ways. E.g. for $n=2k$, the value is $\sum_{i=1}^2k 2i - \sum_{i=1}^k 4i = 2k(2k+1) - 2k(k+1) = 2k^2$. – Calvin Lin Mar 24 '13 at 20:10
1

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.

Ross Millikan
  • 374,822
  • I didn't even think to start from the middle, what an idiot.

    Thank you, you've given me enough.

    This doesn't generalise to all n because even numbers have no natural middle.

     – user65132 Mar 21 '13 at 20:55
  • @user65132: For odd $n=2k+1$ I believe this gives $2k(k+1)-1$. For even $n$ I find $4,8,1,7,2,6,3,5$ has length $\frac 12 n(n-1)-1+\frac n2=\frac 12n^2-1$ – Ross Millikan Mar 21 '13 at 21:01
  • The question asks if the exact same method for 5 and 13 can be extended to all n, but thanks a lot anyway! – user65132 Mar 21 '13 at 21:04
  • @user65132: I believe so. I think the maximality proof I gave for $5$ can be extended to all $n$, but I haven't thought clearly enough about it to be sure. – Ross Millikan Mar 21 '13 at 21:16
  • Having read over this again, this is a very simple and effective explanation. Although I'm not sure it really constitutes as mathematical proof, I really do admire it, now that I understand it. Thanks a lot. – user65132 Mar 22 '13 at 15:12
0

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 \ $

Travis J
  • 101