Unicursal and Route Problems, Amusements in Mathematics

Two old questions run through this chapter. The first is whether a figure can be drawn without lifting the pencil, and the answer was settled by Euler. Call a point where lines meet a node, and call it odd when an odd number of lines meet there. Every stroke passes through a node as often as it leaves it, except at its two ends, so a figure with no odd nodes can be drawn in one stroke that returns to its start, a figure with two can be drawn in one stroke from one odd node to the other, and a figure with more needs at least half as many strokes as it has odd nodes. When lines may be gone over twice, the cheapest way to cover everything is to double the shortest paths that pair up the odd nodes.

The second question asks for a route through every town once. No such tidy rule exists for it, and the answers here come from following every possible route to the end.

No. 239. A Juvenile Puzzle

Draw this figure in three strokes of the pencil, without lifting the pencil during a stroke or going over any line twice. You can get in a good deal of it in one stroke, but it always seems that four are needed. Or draw it on a slate and rub it out in three rubs.

No. 240. The Union Jack

This rough sketch of the Union Jack cannot be drawn in one stroke. How much of it can be drawn without lifting the pencil or going twice over the same line?

No. 241. The Dissected Circle

How many continuous strokes, without lifting the pencil, are needed to draw this design? A new stroke begins whenever the pencil changes direction. You may go over the same line more than once.

No. 242. The Tube Inspector’s Puzzle

An inspector must go over all seventeen lines joining these twelve stations, each a mile long. He may begin and end where he likes. What is his shortest route?

No. 243. Visiting the Towns

A traveller starting from town No. 1 wishes to visit every town once only, going only by the roads shown, and to end at No. 1. How many different routes are there?

No. 244. The Fifteen Turnings

Towns stand a mile apart on a square of roads, eight by eight. Starting from the black town, a traveller wants to go as far as possible while making only fifteen turnings and never going along the same road twice. Going straight to the far side, then to the top corner, across the top, down the left side, along the bottom and up again, he goes thirty-seven miles in five turnings. How far can he go in fifteen?

No. 245. The Fly on the Octahedron

A fly walks only on the edges of an octahedron. Starting from the top point, how many different routes are there by which it may walk over all twelve edges, never going twice along the same edge?

No. 246. The Icosahedron Puzzle

Suppose a planet shaped like an icosahedron, whose only dry land lies along its thirty edges, each 10,000 miles long. A traveller starts at the North Pole. How far must he go to traverse every edge?

No. 247. Inspecting a Mine

The passages of a mine run as shown, each a furlong long, thirty-one in all. An official descends by the shaft to A and must inspect every passage. How far must he travel, and by what route?

No. 248. The Cyclists’ Tour

Two cyclists, starting from the town with the star on their map, must end their tour at E, visiting every other town once, and only once, on the way. Mr Spicer is certain it can be done; Mr Maggs replies, “No way, I’m sure.” Which of them is right?

No. 249. The Sailor’s Puzzle

A sailor trades among twenty islands, always starting from A, visiting every island once only, and returning to A, by the routes on his chart. He always puts off his visit to C as long as possible. What is his route?

No. 250. The Grand Tour

A man who has never left his native town A decides, at fifty, to see his country by rail, entering every town once and only once and finishing at Z, where an old friend lives. He succeeds. How?

No. 251. Water, Gas, and Electricity

Lay on water, gas and electricity from W, G and E to each of three houses, A, B and C, without any pipe crossing another.

No. 252. A Puzzle for Motorists

Eight motorists drove to church along the dotted roads, each from his house to his church of the same letter, and no driver crossed the track of another. Trace their routes.

No. 253. A Bank Holiday Puzzle

A map shows 120 towns in a rectangle, twelve along and ten down, joined by straight roads. Starting from the top left-hand corner and always going due south or due east, two cyclists find exactly 1,365 routes to their destination. Which town is it?

No. 254. The Motor-Car Tour

In how many ways can a motorist starting from London, L, tour all these towns, visiting each once and returning to London? The exact reverse of a route is not counted as different.

No. 255. The Level Puzzle

In how many ways can you spell LEVEL by placing your pencil on an L and passing along the lines from letter to letter, in any direction? You may not miss a letter.

No. 256. The Diamond Puzzle

In how many ways may DIAMOND be read in this arrangement, starting at any D and passing always to a letter that adjoins it, up, down or across?

D N D

D N O N D

D N O M O N D

D N O M A M O N D

D N O M A I A M O N D

D N O M A I D I A M O N D

D N O M A I A M O N D

D N O M A M O N D

D N O M O N D

D N O N D

D N D

No. 257. The Deified Puzzle

In how many ways may DEIFIED be read in the same kind of arrangement, under the same conditions, a letter being allowed to be used twice in one reading?

D E D

D E I E D

D E I F I E D

D E I F I F I E D

D E I F I E I F I E D

D E I F I E D E I F I E D

D E I F I E I F I E D

D E I F I F I E D

D E I F I E D

D E I E D

D E D

No. 258. The Voters’ Puzzle

In how many ways can you read RISE TO VOTE, SIR in an arrangement of the same kind with V at the centre, every reading using the central V as its middle letter?

No. 259. Hannah’s Puzzle

A young lady named Hannah wrote her name thus, and promised to marry her suitor if he could say in how many ways it could be spelt, always passing to an adjoining letter, diagonal steps allowed.

H H H H H H

H A A A A H

H A N N A H

H A A A A H

H H H H H H

No. 260. The Honeycomb Puzzle

Start on a cell of the honeycomb and trace out a very familiar proverb, passing always to a touching cell and visiting every cell once.

No. 261. The Monk and the Bridges

A river has an island and five bridges; a monk on one bank wants to cross every bridge once, and only once, on his way back to the monastery on the other. How many different routes are there?

A Juvenile Puzzle

Taken as it is meant, the puzzle cannot be done. The figure has eight odd nodes, every junction where a line runs into another, so it needs four strokes. Dudeney’s way out is a trick. Fold the paper and push the pencil down between the fold, drawing two of the short upright lines at once; then draw the long line round the outside and through the middle in one stroke; then the last short line. Folding the paper was not forbidden. On the slate, rub out the long line with one finger, the odd short line with another, and the remaining two short lines with two fingers at once.

Answer Four strokes are needed, so it takes the folded paper

The Union Jack

The drawing has sixteen odd nodes, all on the outside, so it needs eight strokes. To get as much as possible into one of them, the other seven should be as short as possible, joining odd nodes in pairs by the shortest pieces of the drawing. On Dudeney’s own sketch the best that can be done leaves out only the dotted pieces below, short stretches of the border.

The single stroke, from A to B, covers 90.6 per cent of the drawing; the dotted pieces are the rest. A program tried every pair of odd nodes as the ends, pairing the others by shortest paths, and Dudeney’s choice of A and B does as well as any.

Answer All but the dotted pieces, starting at A and ending at B

The Dissected Circle

Twelve strokes. Start at A, where a diagonal meets the circle, and draw the eight diagonal and side lines that make the star, which brings you back to A; then round the circle to B, down the upright diameter to C, round the circle again to D, and along the level diameter to E.

Twelve is the fewest. A straight stroke runs from the circle to the circle, so it covers at most one of the ten chords, and the chords need ten straight strokes. Chords can follow one another without a further stroke only where they share an end, and they fall into three such groups: the eight chords of the star, the upright diameter and the level diameter. Passing from one group to the next takes at least one more stroke, along the circle or over a line already drawn, so the three groups cost at least two more: twelve in all. The two arcs of the answer are those two strokes, and between them they cover the circle, so eleven will not do and twelve does.

Answer Twelve strokes

The Tube Inspector’s Puzzle

Nineteen miles: B, A, D, G, D, E, F, I, F, C, B, E, H, K, L, I, H, G, J, K. Only D to G and F to I are gone over twice. There are six odd stations, so at least two stretches must be doubled whatever the ends, and two miles is the least they can cost; a program that tried every way of pairing the odd stations agrees.

Answer Nineteen miles

Visiting the Towns

Six towns have only two roads, and both must be used: 9, 1, 12; 9, 5, 14; 4, 8, 14; 10, 6, 15; 10, 2, 13; 3, 7, 13. That forces the rest. There is only one route, 1, 9, 5, 14, 8, 4, 15, 6, 10, 2, 13, 7, 3, 11, 16, 12, 1, or its reverse, and seven roads go unused. A program that follows every road confirms it.

Answer One route only

The Fifteen Turnings

Seventy miles, turning at the towns numbered in order.

A program checks that the route keeps to fifteen turnings and never uses a road twice, and that the example in the question comes to thirty-seven miles. That seventy is the most possible is Dudeney’s answer; no program has searched every route. He adds that a round trip through every town in fifteen turnings is possible too, but it covers only sixty-four miles.

Answer Seventy miles

The Fly on the Octahedron

The octahedron can be drawn flat with its six points and twelve edges intact, A being the top point.

Four edges meet at every point, so every route over all the edges ends where it began. There are 1,488 routes from the top, counting a route and its reverse separately, as a program that follows every possibility confirms. Dudeney said his count took five minutes and asked the reader to accept it.

Answer 1,488 routes

The Icosahedron Puzzle

Five edges meet at each of the twelve points, so every point is odd, and a single journey must repeat edges enough to leave only its start and end odd. The other ten points must be paired off by repeated edges, and the cheapest way is five edges that do not touch one another or the North Pole. The traveller goes over twenty-five edges once and five twice, 350,000 miles in all. A program that tried every end point and every pairing agrees that no shorter journey exists.

Answer 350,000 miles

Inspecting a Mine

Thirty-six furlongs: A, B, G, H, C, D, I, H, M, N, I, J, O, N, S, R, M, L, G, F, K, L, Q, R, S, T, O, J, E, D, C, B, A, F, K, P, Q. He goes twice along A–B, C–D, F–K, J–O and R–S. The mine has ten odd points. Starting at one of them and finishing at another, he would need to repeat only enough passages to pair up the other eight, four at least, for thirty-five furlongs. But A is even, and a walk that starts there must end at an odd point while the repeated passages make A itself odd; that leaves nine odd points and A to be paired, five passages at least. A program confirms thirty-six from A and thirty-five from the best starting point.

Answer Thirty-six furlongs

The Cyclists’ Tour

Both were right. Mr Maggs’s reply is the route: from the star, visit the towns in the order N, O, W, A, Y, I, M, S, U, R, E. The roads of the map were read by a program that blanked out the towns and listed the pair of towns each remaining stroke of ink joins; on that map this is the only route from the star to E through every town.

Answer “No way, I’m sure”: N, O, W, A, Y, I, M, S, U, R, E

The Sailor’s Puzzle

Dudeney finds just four round trips from A, or eight counting the reverse ways:

A I P T L O E H R Q D C F U G N S K M B A

A I P T S N G L O E U F C D K M B Q R H A

A B M K S N G L T P I O E U F C D Q R H A

A I P T L O E U G N S K M B Q D C F R H A

Counting A as the first island, these reach C as the 12th, 13th, 16th and 17th island; backwards, as the 10th, 9th, 6th and 5th. So the sailor takes the last route as written, which puts C off until the seventeenth island. A program checks that each route visits all twenty islands once and that the positions of C are as stated.

That these four are the only routes needs the chart itself, whose many crossing lines are hard to follow. Read from a clear scan of the 1917 printing, it has 28 roads: at every island the roads ending there can be counted: three at most islands, two at C, M, N and P. Two lines only look like extra roads: the road from R to F runs over K without touching it, and the road from Q to D hooks round F.

A program that tried every round trip from A over these roads found exactly Dudeney’s four, each in both directions, so his count stands and the seventeenth island is as late as C can come.

Answer A I P T L O E U G N S K M B Q D C F R H A

The Grand Tour

Dudeney straightens the railway map into a grid of 24 towns, four across and six down, with A at the top right and Z at the bottom left. Colour the towns like a chessboard. Each journey from town to town changes colour, so a route through all 24 towns, which makes 23 journeys, would end on the other colour from A; but Z is the same colour as A. The tour is impossible as it stands.

The loophole is the word “enter”. The man had never left A, so he had never entered it. He goes to a neighbouring town and comes straight back, entering A for the first time; then he has 22 towns left, an even number, and can end on Z.

A program confirms that no route of the plain kind exists, and finds forty-three routes of this kind.

Answer Out to a neighbouring town and straight back into A, then on through the rest to Z

Water, Gas, and Electricity

As the conditions are meant, it cannot be done. Suppose the nine pipes could be drawn without crossing: they would divide the paper into regions, and for a connected drawing of 6 points and 9 lines Euler’s formula (for any connected drawing without crossings, points less lines plus regions is always 2, as for a single point, and adding a line either joins a new point or closes off a new region) says there are $2 - 6 + 9 = 5$ of them. But every region would be bounded by at least four pipes, since a pipe always runs from a house to a supply, and each pipe borders two regions, so there could be at most $18/4$ , four and a half. Dudeney’s way out: the water pipe for house C runs through house A, whose owner does not object, and then no pipe crosses another.

Answer Impossible, unless one pipe passes through a house

A Puzzle for Motorists

Here is one set of routes, found by a program that searched for eight paths along the roads, each from a house to its church, no two touching.

Dudeney draws a set of his own; the puzzle asks only for some way, and there are others.

Answer Routes as shown

A Bank Holiday Puzzle

Write 1 on every town in the top row and the first column; every other town gets the sum of the numbers on the town above it and the town to its left. The number of routes to the town $m$ places along and $n$ places down is $\frac{(m + n)!}{m!\,n!}.$ The only town with exactly 1,365 routes is the twelfth in the fifth row, where $m = 11$ and $n = 4$ , and $15!/(11!\,4!) = 1{,}365$ . A program confirms that no other town of the 120 has that number.

Answer The twelfth town in the fifth row

The Motor-Car Tour

There are thirty routes. The map is the dodecahedron in disguise: twenty towns, three roads at each, joined exactly as the corners and edges of the twelve-faced solid, as a program confirms. It is the board of Hamilton’s Icosian Game. Dudeney found the thirty by sliding three cardboard shapes round a circular redrawing of the map, each giving ten routes, and left the proof that there are no more to the reader. A program that follows every road from London finds exactly thirty tours, a tour and its reverse counting once.

Answer Thirty

The Level Puzzle

Eighty. From the corner L there are three E’s to go to. Through the E on either side, the V is forced and four E’s lead on to an L, four ways each; through the E on the diagonal there are three V’s, each with four ways to finish, twelve in all. That is twenty from each corner, and eighty from the four. As Dudeney counts, a reading may go back through the E it came by. A program counts eighty.

Answer Eighty ways

The Diamond Puzzle

252 ways. Every reading starts at the D in the middle and works outwards one ring at a time, so count the readings ring by ring. The letters stand at the points of a square grid, the $k$ th ring $k$ steps out, and four points of each ring lie on the two axes through the centre. A reading that has kept to an axis can go on in three ways, straight on or to either side; any other reading can go on in two. So if $T_k$ readings reach ring $k$ , four of them on the axes, $T_{k+1} = 3 \times 4 + 2(T_k - 4) = 2T_k + 4 .$ With $T_1 = 4$ this gives 4, 12, 28, 60, 124, 252, that is $T_k = 4(2^k - 1)$ . DIAMOND takes six steps out, so there are 252 readings, which is Dudeney’s formula $2^{n+1} - 4$ for a word of $n = 7$ letters. A program counts the readings and agrees.

Answer 252 ways

The Deified Puzzle

1,992 ways. Every reading passes through an F. From a corner F, FIED can be read in 16 ways, so DEIFIED through it in $16 \times 16 = 256$ , and the four corner F’s give 1,024. From a side F there are 11 ways, so 121 readings through it, and the eight side F’s give 968. The total is 1,992. Dudeney adds that NUN set out the same way gives 64 readings, NOON 56 and MADAM 400; the program confirms all four.

Answer 1,992 ways

The Voters’ Puzzle

63,504 ways, which is $252^2$ : by the ring count of the Diamond Puzzle there are 252 ways of reading from the central V out to an R, six rings away, and each can be joined to any of the 252 ways back in. Dudeney’s formula for a palindrome of $2n + 1$ letters is $\bigl(4(2^n - 1)\bigr)^2$ , and the program agrees.

Answer 63,504 ways

Hannah’s Puzzle

3,468 ways. From each N there are 17 ways to read NAH, so 68 for the four N’s, and as many ways to reach an N reading HAN. But the two N’s of HANNAH must be different letters, and each N touches the other three, so for every HAN into a given N there are $3 \times 17 = 51$ ways to finish. That gives $17 \times 51 = 867$ through each N, and 3,468 in all. A program counts every spelling and agrees.

Answer 3,468 ways

The Honeycomb Puzzle

The proverb is “There is many a slip ’twixt the cup and the lip.” Start at the T on the outside at the bottom right, go to the H above it, and the rest follows. A program that tried every start and every path finds just one way to trace the proverb through all thirty-six cells.

Answer “There is many a slip ’twixt the cup and the lip”

The Monk and the Bridges

Call the monk’s bank M, the island I and the monastery’s bank Y. Bridges a and b join M to I, c and d join I to Y, and e joins M to Y.

There are sixteen routes: abecd, abedc, acdbe, acebd, adcbe, adebc, baecd, baedc, bcdae, bcead, bdcae, bdeac, ecabd, ecbad, edabc, edbac. A program lists every route over all five bridges and finds exactly these.

Answer Sixteen routes