Henry Ernest Dudeney/Modern Puzzles/157 - Crossing the Lines/Solution

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