General Comments

If you have any comments or questions, please e-mail me.
Problem 1

Below is the construction. It's quite simple; you should be able to figure out the order.




Problem 2

(a)
Let the marks on ruler X be at positions X1, X2, ... , Xn, in order. We can assume X1=0 for any ruler. Clearly regardless of what n is, if two rulers (X,Y) are to have the same multiset, then Xn = Yn. The second largest distance in the multiset of X must be |Xn - X2| or |X1 - Xn-1|. By symmetry we can assume the latter case holds. The same applies to Y, so we have Yn-1 = Xn-1. These marks are to the right of the midpoint on the ruler.

For n=4... We have X1, X3 and X4 fixed, as well as Y1, Y3, Y4. So far the two rulers must be identical. The fourth mark on each ruler (still not fixed) must have index 2, according to the construction so far. The only distances in the multiset of X that are not accounted for yet are |X2-X1|, |X2-X3|, |X2-X4|. Since we are searching for two different rulers, we must have Y2 <> X2. We can assume Y2 > X2 without loss of generality. Let |Y2 - X2| = d. Then the three remaining distances in Y are |X2-X1| + d, |X2-X3| - d, and |X2-X4| - d. It is impossible to match these three distances to those of X, for any value d>0.

For n=6 ... Ruler X= 0,1,6,7,9,11 and ruler Y= 0,1,2,6,8,11.
Both give the multiset 1,1,2,2,3,4,5,5,6,6,7,8,9,10,11.

(b) The ruler 0,1,3,7,12 has no duplicate distances and measures (1,2,3,4,5),6,7,9,11,12.

Problem 3

This problem is quite hard. If you didn't get it, don't worry about it. It's not a typical exam question by any means.







Problem 4

A convex polygon has all right turns, and does not cross itself.

Lemma. A polygon with all right turns which crosses itself must contain over 360 degrees of right turns.
Proof. Given any such polygon, note that at any point of self-intersection, the polygon exits, turns right, and re-enters the point of intersection. Therefore the polygon must have more than 360 degrees of "right turns" if it is self-crossing.

We know that a convex simple polygon has no loops, and therefore has just 360 degrees of right turns. Thus:

Algorithm Recognize
  1. turns <-- 0
  2. for each vertex vi in {v1, ..., vn}
  3. if turns = 360, then else