Track / Stage 6 / 150 of 400 #1150 of 1964

Problem 1150

National olympiad, first round

Combinatorics Difficulty 6.2 Prove it

1 A 15 -inch-long stick has four marks on it, dividing it into five segments of length $1,2,3,4$ , and 5 inches (although not neccessarily in that order) to make a "ruler." Here is an example.

Using this ruler, you could measure 8 inches (between the marks $B$ and $D$ ) and 11 inches (between the end of the ruler at $A$ and the mark at $E$ ), but there's no way you could measure 12 inches.
Prove that it is impossible to place the four marks on the stick such that the five segments have length $1,2,3,4$ , and 5 inches, and such that every integer distance from 1 inch through 15 inches could be measured.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution 1: In order to measure 14 inches, one mark must be 1 inch from an end of the ruler. Likewise, in order to measure 13 inches, there must be another mark that is 2 inches from an end of the ruler. Without loss of generality, suppose the leftmost mark is 1 inch from the end, and the rightmost mark is 2 inches from the other end.
Next, we observe that the second mark from the left must be 5 inches from the first, or else it would be impossible to measure 6 inches.
At this point, there are only two cases to consider: either the distances between marks are, in order,
$1,5,4,3,2$
or the distances are
$1,5,3,4,2 \text {. }$

In the first case, we cannot measure 8 inches, and in the second case, we cannot measure 10 inches. We conclude that it is impossible.

Solution 2: In order to make a measurement, you must choose a pair of marks, where the two endpoints are included. Since there are 6 marks, that means that we can measure at most 15 different segments $(6 \times 5 / 2)$ . Therefore a ruler that can measure every length from 1" through 15 " must have exactly one way of measuring each length.
If the 1 " segment is next to the 2 ", 3 ", or 4 " segments, then that would make a second way of measuring 3 ", 4 ", or 5 ". Therefore, the 1 " segment must be next to the 5 " segment only: the 1 " is on the end, next to the 5 ". Now, if the 2 " segment is next to the 3 " or 4 " segments, then that would make a second way of measuring 5 " or 6 ". So the 2 " segment is also next to the 5 " segment only. But that leaves nowhere to put the 3 " and 4 " segments.

Solution 3: Let $a, b, c, d, e$ be the segments in order (equalling $1,2,3,4,5$ , but not necessarily in that order). As above, there are only 15 possible segments that can be measured. The sum of all 15 segments (in inches) is
$1+2+\cdots+15=15 \times 16 / 2 .$

But this is also equal to $5 a+8 b+9 c+8 d+5 e$ .
Hence
$5 a+8 b+9 c+8 d+5 e=15 \times 16 / 2=15 \times 8 .$

Now note that $15=a+b+c+d+e$ , so
$5 a+8 b+9 c+8 d+5 e=8 a+8 b+8 c+8 d+8 e .$

Subtract $5 a+8 b+8 c+8 d+5 e$ from both sides to get $c=3 a+3 e$ .
But $a+e$ is at least 3 and $c$ is at most 5 , a contradiction.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.