What lengths of L inches can be measured with unmarked strai

What lengths of L inches can be measured with unmarked straightedges 20 inches and 72 inches?

Solution

The problem concerns the set of integers {20m+12n, m and n arbitrary integers in Z}.

Consider the equation 20m+12n = L.

As 4 (HCF of 20 and 12) divides the left hand side , 4 must also divide L.

The converse is also true by Euclidean algorithm.

Thus L can be measured iff 4 divides L.

NOTE: We allow for subtraction. For example we can measure 20 and take off 12 using the second ruler , thereby measuring 8. Similarly , using 2 times the second ruler (24) and subtracing the first , we can measure 4 .