Solution to problem 15 -- Carpenter Ruler

Solution to The Carpenter Ruler Problem

Graders: Wenqing Deng, Yangang Li, Anuradha Sethuraman , Jun Wang.

The Problem:

This problem deals with the Carpenter's Ruler.

A) Suppose m is the largest of the wi's. Prove that the Carpenter's Ruler can always be folded into a length of no more than 2m. Do this by giving an algorithm for folding the ruler and basing the result on the folding that the algorithm produces.

B) Prove that the bound in part a is the best possible. That is, for any given e > 0, explain how to construct a ruler for which the optimal folded length is at least 2m - e.

Solution to part A:

Algorithm:

Run a linear algorithm to find the maximum link(or one of the maximum links) of the ruler, call it link AB.
Establish a coordinate with positive direction to the right hand side and with a zero point Z.
Place the maximum link AB onto the coordinate; align point A with point Z and make the link toward the positive direction.
Consider the remaining links one at a time and in order, beginning with end point A and end point B respectively. For each link, if its starting point is in the range [A,B] inclusive, then fold it to the positive direction; otherwise, fold it to the negative direction. Do the same thing until all the remaining links are folded.

It is easy to see that the algorithm does the folding within the range [0,2m] by noting that if the link is folded to the right, then its starting point (i.e. the point connected to already placed link that it connects to) is located in the range [0,m], hence once placed, the ending point of that link is located at a point no greater than 2m, since m is the maximum link length. Similarly if the link is folded to the left, then its starting point is lcoated in (m,2m], hence once placed its ending point is no less than zero.

Complexity: The running time is clearly O(n) --- that is, linear.

Solution to part B:

To prove the above (part a) bound is optimal, we must find at least one ruler with maximum link length of M, such that, given any e(epsilon), we cannot fold the ruler in less than 2M-e.

In fact we can construct such a ruler. Consider a ruler that consists of 2*ceiling(m/e) links. We build the ruler in a particular way such that it looks like:

M , M-e , M , M-e , M , M-e , ...
That is, every other link (say, even numbered links) is of length M, and every other link (say, odd numbered links) is of length M-e.

We claim that an optimal folding is 2M-e.

Proof:

First, we claim that every pair of adjacent links must be folded, i.e., the angle between them is zero degree. If there exists a pair of links such that the angle between them is 180 degree, then the folded length is at least 2M-e, i.e., the summation of the adjacent links. This means we already proved that the best we can do is 2M-e. If we wish to do better than 2M-e, we must fold every pair of adjacent links.
Second, since we fold each pair of the adjacent links, after the treatment of the first pair, we have a length M; after the treatment of the second pair, we will have a length M + e; after the treatment of the third pair, we have a length M+2e. See the example bellow:

Fig: example after the first three pairs of links are treated.
Third, follow the pattern above, after the Nth pair of the links are folded, we will have a length of M + (N-1) * e. Since we have 2*ceiling(M/e) links, i.e., we have ceiling(M/e) pairs of them, after all of them are folded, we will have a folded length of M + (ceiling(M/e) - 1) * e which is at least M + (M/e -1) * e = 2M-e. So, we still cannot do it better than 2M-e. Because e is an arbitrary value, 2M is really optimal.