Puzzles and Paradoxes: Fascinating Excursions in Recreational Mathematics

Puzzles and Paradoxes: Fascinating Excursions in Recreational Mathematics

by T. H. O'Beirne

Paperback

$12.74 $12.95 Save 2% Current price is $12.74, Original price is $12.95. You Save 2%.
View All Available Formats & Editions
Choose Expedited Shipping at checkout for guaranteed delivery by Friday, November 16

Product Details

ISBN-13: 9780486246130
Publisher: Dover Publications
Publication date: 09/13/2017
Series: Dover Books on Mathematical and Word Recreations
Pages: 256
Product dimensions: 5.40(w) x 8.40(h) x 0.60(d)

About the Author

T. H. O'Beirne wrote a weekly column, also called "Puzzles and Paradoxes," for the British magazine New Scientist. He is the inventor of O'Beirne's Cube, a classic box-packing problem in which six irregularly shaped pieces can be packed into a cube or five other rectangular solids.

Read an Excerpt

CHAPTER 1

One More River to Cross

Transport problems and imperial exercises

The first problems we shall discuss are based on difficulties which can arise when travellers have to cross rivers in small rowing-boats. Some of the difficulties derive merely from the limitations of carrying capacity, part of which must continually be reserved for a traveller who will be passenger, crew, and prime mover, all in one: in some cases the problem is further complicated by actual or potential antagonisms between different travellers. Problems of this type may well have once been matters of real practical concern. Similar questions of a more complicated nature can nowadays provide employment for specialists in logistics and operational research.

About 1,000 years ago, some of these questions were offered as problems for sharpening the wits of the young, or as diversions for their presumably more acute elders: probably they circulated by word of mouth for some time before that. Since then they have passed into popular tradition, and intermittently they emerge into print, in a variety of places — unaltered, or trivially rejuvenated — with little to show how old they actually are.

We start with one of the best-known problems of this type, which we can state in the words of Charles Hutton, LL.D., F.R.S., Professor of Mathematics in the Royal Military Academy, Woolwich, who in 1803 included it in the first of his four volumes of Recreations in Mathematics and Natural Philosophy:

Three jealous husbands with their wives having to cross a river at a ferry, find a boat without a boatman; but the boat is so small that it can contain no more than two of them at once. How can these six persons cross the river so that none of the women shall be left in company with any of the men, unless when her husband is present?

This is a translation from the Problèmes plaisants et délectables of Claude-Gaspar Bachet, Sieur de Méziriac — a book first published at Lyons in 1612, and still in print today.

This problem may have been first recorded by 'one or other of two celebrated Englishmen. In one early source it is attributed — probably spuriously — to the Venerable Bede, in the ninth century A.D.: it also appears in a mixed collection of about fifty problems which are included (with more plausibility) in the Works of Alcuin of Northumbria, who sent 'some examples of subtlety in Arithmetic, for your enjoyment', to accompany his Letter LXXXV to his august pupil, the Emperor Charlemagne.

It is fair — and perhaps enough — to remark that in its original form our problem reflected the dangers and crudities of contemporary behaviour in a way which Bachet evidently thought unsuitable for the polite society of seventeenth-century France. Those who seek more details will find them in the Latin original.

Three men and a boat — not forgetting their wives

Even if no question of jealousy arose, a minimum of nine one-way crossings would be needed to transport six persons across: a back-and-forward trip can take no more than one person across, before the final crossing, since someone must go back with the boat. The jealousy of the husbands in fact involves the party in one additional trip in each direction.

This is fairly easy to establish, for if we rule out all the arrangements which violate imposed conditions, cancel previous progress or merely exchange one couple for another, we find that very little effective choice is left.

At the start, two must embark and one return. Two men cannot leave their wives with the third man, and no man can let his wife cross with another man. If a husband crosses with his wife, he cannot send her back alone to the other men. So a woman must be left on the far side while either her husband or another woman returns with the boat.

No progress is made if only one person now embarks. It is futile merely to visit the first woman, or bring her back, and equally futile for another woman to change places with her. Her husband could cross over, but could not send her back to the other men, and neither of the other men could be allowed to cross over to her.

Two men cannot embark, as one (at least) would be leaving his wife with the remaining man. So a second woman must be taken across, not by her husband, since he would meet the first woman without her husband on the far bank, but necessarily by the third woman; and one woman must return with the boat.

It is now useless for the third woman to cross alone, as she or another woman would have to return. Neither of the men alone, nor the third couple together, can cross to two unaccompanied women. It must be two men, and these the husbands of the two women on the farther bank.

The boat cannot be brought back by the two women, or by one woman, returning to the third man; nor by one man alone, who would leave his wife with another man on the far bank. If the men are not to return uselessly, the boat must be brought back by a married couple.

In this fashion we can go on and solve our problem. But there is a better way.

Half-way through the return crossing last mentioned there is one couple on either bank, and one in mid-stream. Suppose at this point they decided to abandon the whole project. The boat would turn and everything would be done in reverse, back to the beginning.

If, instead, they keep this reversal in mind, but go through its steps with the banks of the river exchanged, as well as the couples on them, the boat will in fact continue to the other side and finally all three couples will be transported to the farther bank.

This will take eleven one-way crossings in all: the five necessary before the symmetrical position arose, the one which produced the symmetrical situation when the boat was in the middle, and five more which are the reflections in space and time of the first five. The latter five cannot be replaced by anything better, since if they could, so could the first five; and we have seen this is impossible.

A solution can be shown diagrammatically as in Table la, where capital letters denote men, and corresponding lower-case letters their wives. There must be a minimum of three who can handle a boat, and if there are only three, these must be two women and the third woman's husband.

Our solution, like Alcuin's, makes men row rather than women if a choice is possible, but his requires four persons able to row. As with many old problems, there is a traditional mnemonic for the solution, in Latin elegiac verse. Hutton gives this with an English rendering in which the solution is symmetric though that in the Latin is not, and both of these make women row unnecessarily.

With four couples (or more), the first four crossings are no different and leave two women on the far bank. Then either a third woman must be taken across by a fourth who returns; or else the two husbands cross together to their wives, and one couple returns.

With three women (or more) alone on the far bank, no man, no couple, and no pair of men are allowed to cross. Women must transport women until an impasse arises when there are no more: all else will merely undo previous work.

With a couple alone on the far bank there is another impasse. Only a couple can embark, and only a couple can return. With only three couples, two men could cross and leave their wives entirely alone; now at least one strange man would remain with the forsaken wives. The problem with more than three couples is therefore insoluble.

The sixteenth-century Italian mathematician Tartaglia (so named from a speech defect) had the wrong view of this; it is better to remember his claim to be the first to solve a cubic equation.

It may be well to dispel some common misconceptions by emphasizing that the conditions are not merely that a wife must not be alone with another man; and that they do not imply that a husband will be content so long as all other husbands have their wives with them if they are with his wife when he is not present himself. These husbands are jealous in the worst sense of the word: they see their own presence as the only security against maltreatment or misbehaviour of their wives. More reasonable husbands would in fact have an easier passage.

When valets or cannibals are second-class passengers

Another traditional problem is almost — but not exactly — equivalent to that of the three jealous husbands with their wives. Again there are two classes of travellers, usually taken to be either three gentlemen each with his lackey or valet: or alternatively three missionaries or explorers accompanied by three cannibals or savages. Here, too, the boat can hold no more than two; and undesirable behaviour is now to be expected if passengers of the first class are ever in a minority to passengers of the second class, in any isolated assembly.

Very little goes wrong if we now assume that the husbands are like the gentlemen (or the missionaries or the explorers), and that the wives are like the valets (or the cannibals or the savages). A preponderance of wives in any company is unacceptable, for some wife must then be apart from her husband in the company of another man, or men: but the conditions of the new problem would permit husbands and wives to associate in equal numbers but not necessarily in married couples. This raises new possibilities.

Actually these involve less change than might be feared: the travelling arrangements are virtually unaffected. No type of journey which was allowed before is now prohibited; and only two types of journeys are freed from prohibition. In one of these, a couple in the boat are travelling between isolated couples on either bank, just as in the journey which forms the mid-point of the previous solution: but either two or all three of the couples concerned can now be unmarried. In the other type of journey an unmarried couple are in the boat, and all the others are on the same bank.

The first possibility provides an alternative way of making a crossing at the half-way stage, and the second possibility allows the wife who makes the first or last crossing to be ferried by any of the men — not by her husband only, or by one of the other wives. Apart from this, the optimum programme must proceed as before: the only difference is that interchange of husbands may take place, and similarly of wives, in ways which now are considered to be immaterial. If the husbands who treat their wives like this are then considered to be gentlemen, and not to be savages, we obtain the solutions of the other problems.

It is of some interest to consider what other possibilities are open to our travellers, in addition to crossing successfully together. There is one obvious impossibility: they cannot all be on one bank, separated from the boat. All other divisions which do not involve prohibited assemblies can be achieved, with one exception — wives or savages can not be abandoned on either bank without a boat: which seems only elementary justice.

Readers may now wish to consider how best to leave varied selections of personnel on either bank, with or without the boat. We shall return to these questions later.

Tribulations of a father of five

Our next problem is one which we composed for the purposes of a prize competition.

A father rowing a boat has to transport his five sons across a river, with a minimum number of one-way crossings, such that finally all the children have had an identical number of one-way trips. The boat will hold the father and not more than two children; no pair of children of immediately neighbouring ages can be left together in the absence of their father, or they will start a fight; but children more separated in age will content themselves with more peaceful occupations. Only the father is allowed to row; and he may or may not be able to stop fights in the boat.

Here is the prize-winning solution which came from Mr. A. J. Casson, then in the Sixth Form, Latymer Upper School.

'Let the sons be labelled A, B, C, D, E in descending order of age, and let the starting-point and destination be referred to as the first bank and second bank respectively.

'The first move must be to take B and D to the second bank. For, if B is not taken, A and C must both be taken to prevent them from fighting B, leaving D and E together. Similarly, D must be taken on the first trip. The last move in any solution must be to bring B and D to join their brothers on the second bank, for similar reasons. Therefore B and D must make at least three crossings: the first trip to the second bank, a return crossing at some time, and the final trip, also to the second bank.

'If peace is to be preserved, this means that each son must make at least three crossings, so at least fifteen man-crossings must be made altogether, not counting those made by the father. Only two boys can be taken on each trip, so at least eight one-way crossings are required. Eight crossings would leave the boat on the first bank, so at least nine one-way journeys are in fact necessary.

'The table below [Table 1b] gives a solution in which nine crossings are made, three by each son, and it has been shown that the problem cannot be solved with fewer crossings. Therefore this solution completes the manoeuvre in the minimum number of trips. It can be seen from the table that two rival brothers never cross the river together, so it does not matter if the father cannot manage the oars and his sons at the same time.

'It will now be shown that there are eight solutions. We have seen that fifteen man-crossings must be made in nine boatloads, and that on the penultimate move A, C, E must be on the second bank but the boat must be on the first bank. To achieve this the boat must be returned to the first bank on some trips without a full complement, and exactly three man-journeys must have been sacrificed in this way. But only three can be sacrificed if the problem is to be solved in the minimum number of moves. Therefore no solution can include a journey from the first to the second bank without two passengers on board.

'The first move is forced, as we have seen. B and D cannot return immediately, as this would restore the original position and B and D would now have to make five crossings altogether. Therefore either B or D returns, or the boat must return light. If B returns, the next move is forced, for B cannot move again until the final journey, so the only way to separate A, B, and C is to take A and C across.

'On the fourth move C and D must be separated. If D returns alone, E is the only one who can make the fifth crossing to the second bank. But we have seen that such a move is bound to fail. If C makes the fourth crossing alone, C and E must make the fifth trip. C cannot move again, having made three trips, therefore the sixth crossing must be made by D, possibly with A or E. But B and D cannot move until the ninth trip, therefore two boys cannot cross to the second bank on the seventh trip. Therefore this fourth move also fails. If A and C cross together, they must return on the fifth trip, completing their three crossings. Therefore D must make the next trip alone, which fails for the same reason as before.

'If A and D make the fourth crossing, the solution already given is obtained. B and D must stay on the first bank until the final trip, therefore the fifth move is forced. A has now completed his three crossings, so the sixth trip must be made by one or both of C and E. Whoever crosses must return immediately, therefore both C and E must take a joy-ride to the first bank and back. All those on the second bank have now made three crossings, so the boat must return light to pick up B and D and complete the operation.

'If, from the fourth move onwards, A and C are interchanged, a solution is obtained in which C and D make the fourth move, and the above reasoning shows that all subsequent moves are forced. However, the father would not like this method, since it requires him to watch C and D while rowing the boat.

'We could equally well have taken A, B, C, D, E to be in ascending order of age, and applied the same reasoning. This would have the effect of interchanging A with E and B with D, so all the solutions in which D makes the second journey can be obtained from those already given, by this substitution. Thus we have four solutions so far.

(Continues…)



Excerpted from "Puzzles & Paradoxes"
by .
Copyright © 1965 Oxford University Press.
Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Table of Contents

Preface ix
1. One More River to Cross 1
2. False Coins and Trial Balances 20
3. New Weighs with False Coins 33
4. Jug and Bottle Department 49
5. A Gamut of Geometry from A to Y 76
6. Race-Track Problems and Legal Fictions 88
7. Cubism and Colour Arrangements 112
8. Gamesman, Spare that Tree 130
9. 'NIM' You Say—and 'NIM' It Is 151
10. Ten Divisions Lead to Easter 168
11. Problematic Lies and Unexpected Truths 185
12. A Christmas Cracker with 100 Birds 198
Postscript 209
References 227
Index 233

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews