Henry Ernest Dudeney/Modern Puzzles/157 - Crossing the Lines/Solution
Jump to navigation
Jump to search
Modern Puzzles by Henry Ernest Dudeney: $157$
- Crossing the Lines
- You are asked to draw the diagram of Figure $1$ (exclusive of the little crosses) with three continuous strokes of the pencil,
- without removing the pencil from the paper during a stroke, or going over a line twice.
- As generally understood, it is quite impossible.
- Wherever I have placed a cross there is an "odd node", and the law for all such cases is that half as many lines will be necessary as there are odd nodes --
- that is, points from which you can depart in an odd number of ways.
- Here we have, as indicated, $8$ odd nodes, from each of which you can proceed in three directions (an odd number),
- and therefore, four lines will be required.
- But, as I have shown in my book of Amusements in Mathematics, it may be solved by a trick, overriding the conditions as understood.
- You first fold the paper, and with a thick lead-pencil draw $CD$ and $EF$, in Figure $2$, with a single stroke.
- Then draw the line from $A$ to $B$ as the second stroke, and $GH$ as the third!
- During the last few years this puzzle has taken a new form.
- You are given the same diagram and asked to start where you like and try to pass through every short line comprising the figure,
- once and once only, without crossing your own path.
- Figure $3$ will make quite clear what is meant.
- It is an attempted solution, but it fails because the line from $K$ to $L$ has not been crossed.
- We might have crossed it instead of $KM$, but that would be no better.
- Is it possible?
- Many who write to me about the puzzle say that though they have satisfied themselves as a "pious opinion", that it cannot be done,
- yet they see no way whatever of proving the impossibility, which is quite another matter.
- I will show my way of settling the question.
Solution
The solution is straightforward by Characteristics of Traversable Graph, but it is interesting to see how wordy Dudeney could be:
- Let us suppose that we cross the lines by bridges, represented in Figure $1$ by the little parallels.
- Now, in Figure $2$, I transform the diagram, reducing the spaces $A$, $B$, $C$, $D$, $E$ to mere points,
- and representing the bridges that connect these spaces by lines or roads.
- This transformation does not affect the conditions,
- for there are $16$ bridges or roads in one case, and $16$ roads or lines in the other,
- and they connect with $A$, $B$, $C$, $D$, $E$ in precisely the same way.
- It will be seen that $9$ bridges or roads connect with the outside.
- Obviously we are free to join these up in pairs in any way we choose, provided the roads do not cross one another.
- The simplest way is shown in Figure $3$, where on coming out from $A$, $B$, $C$, or $E$,
- we immediately return to the same point by the adjacent bridge, leaving one point, $X$, necessarily in the open.
- In Figure $2$ there are $4$ odd nodes, $A$, $B$, $D$, and $X$ (if we decide on the exits and entrances, as in Figure $3$),
- so, as I have already explained, we require $2$ strokes (half of $4$) to go over all the roads,
- proving a perfect solution to be impossible.
- Now, let us cancel the line $AB$.
- Follow the line in Figure $3$ and you will see that this can be done, omitting the line from $A$ to $B$.
- This route the reader will easily transform into Figure $4$ if he says to himself,
- "Go from $X$ to $D$, from $D$ to $E$, from $E$ to the outside and return into $E$," and so on.
- The route can be varied by linking up those outside bridges differently,
- by making $X$ an outside bridge to $A$ or $B$, instead of $D$, and by taking the cancelled line either at $AB$, $AD$, $BD$, $XA$, $XB$, or $XD$.
- In Figure $5$ I make $X$ lead to $B$.
- We still omit $AB$, but we must start and end at $D$ and $X$.
- Transformed in Figure $6$, this will be seen to be the precise example that I gave in the question.
- The reader can now write out as many routes as he likes for himself,
- but he will always find it necessary to omit one line or crossing.
- It is thus seen how easily sometimes a little cunning, like that of the transformation shown,
- will settle a perplexing question of this kind.
Sources
- 1926: Henry Ernest Dudeney: Modern Puzzles ... (previous) ... (next): Solutions: $157$. -- Crossing the Lines
- 1968: Henry Ernest Dudeney: 536 Puzzles & Curious Problems ... (previous) ... (next): Answers: $414$. Crossing the Lines