Competition problem — Combinatorics

Library / /42 of 86

Combinatorics Difficulty 6.7 National Olympiad Prove it United States

Problem:

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 necessarily 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.

Solutions — 3

Solution 1

Solution:

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

Solution:

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

Solution:

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 $5a + 8b + 9c + 8d + 5e$ .
Hence
$5a + 8b + 9c + 8d + 5e = 15 \times 16 / 2 = 15 \times 8.$
Now note that $15 = a + b + c + d + e$ , so
$5a + 8b + 9c + 8d + 5e = 8a + 8b + 8c + 8d + 8e.$
Subtract $5a + 8b + 8c + 8d + 5e$ from both sides to get $c = 3a + 3e$ .
But $a + e$ is at least $3$ and $c$ is at most $5$ , a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.