River crossing (3) – couples

There is a third class of river crossing problems, which has the same old origin as those of the farmer crossing the river: the publication of medieval manuscript Propositiones ad Acuendos Juvenes, which is generally attributed to generally attributed to Abbott Alcuin.

The original puzzle was:
1) Three couples want to cross a river. The boat they have available is small and can hold only 2 people.
A complication is that the three men are extremely jealous, and don’t want any man or men to be with their wife on one of the two shores if he is not there himself.
How many trips does it take them to all get across the river?

This puzzle was described as “quite sexist” by David Singmaster in his lecture “The utility of recreational mathematics”. He made the statement during the Eugene Strens memorial conference on recreational mathematics and its history, the proceedings of which were written by Richard K. Guy, Robert E. Woodrow. Part of these proceedings can be read here:
http://books.google.nl/books?id=-4W_5ZISxpsC&pg=PA344&dq=puzzle+river+crossing&hl=nl&ei=3qdNTdntGo6WOp_2ieMP&sa=X&oi=book_result&ct=result&resnum=8&sqi=2&ved=0CFoQ6AEwBw#v=onepage&q=puzzle%20river%20crossing&f=false
I think it is sexist in the sense that the puzzle makes a difference between men and women, and that the men are depicted as jealous where the women are not described as such. But frankly I don’t see any discrimination in it in the sense that women are regarded as less than the men. Also, the roles can easily be reversed. The only discrimination aspect I could find in it is that the women do not protest against the jealousy of their husbands.

For the solution, see solution 101

There is a variation of this puzzle, usually termed “missionaries and Cannibals”.
2) 3 Missionaries and 3 Cannibals want to cross a river. There boat can hold only 2 people at any time. The missionaries do not have the courage to be a minority on either shore for fear of being eaten.
How many trips does it take them to all get across?
During the same lecture David Singmaster called this one racist. An understandable accusation, though the puzzle does not mention any race of the cannibals. They might as well be the inhabitants of a secret village in mid-Europe. It also does not mention any religion of the missionaries, they might be Christian, as most people probably will imply, but they might as well be Islamic, though the word misionary is usually associated with the first.

For the solution, see solution 91

3) Just two rowers
There is a version with a small additional constraint: Only one of the cannibals and all of the missionaries can row. I will not give the solution here.

4) A boat for three.
Dudeney comes up with an enlarged boat:
During certain local floods five married couples found themselves surrounded by water, and had to escape from their unpleasant position in a boat that would only hold three persons at a time. Every husband was so jealous that he would not allow his wife to be in the boat or on either bank with another man (or with other men) unless he was himself present. Show the quickest way of getting these five men and their wives across into safety.
Call the men A, B, C, D, E, and their respective wives a, b, c, d, e. To go over and return counts as two crossings. No tricks such as ropes, swimming, currents, etc., are permitted.
The problem of larger boats was later fully analyzed by a mathematician, whose name has eluded me.
You can find the solution at solution 111

5) The four elopements
Sam Loyd made a classic expansion, introducing an island. Dudeney came also up with this variation, which might be an indication that they both got it from a third source. Here the puzzle is presented in Dudeneys words:
Colonel B—— was a widower of a very taciturn disposition. His treatment of his four daughters was unusually severe, almost cruel, and they not unnaturally felt disposed to resent it. Being charming girls with every virtue and many accomplishments, it is not surprising that each had a fond admirer. But the father forbade the young men to call at his house, intercepted all letters, and placed his daughters under stricter supervision than ever. But love, which scorns locks and keys and garden walls, was equal to the occasion, and the four youths conspired together and planned a general elopement.
At the foot of the tennis lawn at the bottom of the garden ran the silver Thames, and one night, after the four girls had been safely conducted from a dormitory window to terra firma, they all crept softly down to the bank of the river, where a small boat belonging to the Colonel was moored. With this they proposed to cross to the opposite side and make their way to a lane where conveyances were waiting to carry them in their flight. Alas! here at the water’s brink their difficulties already began.
The young men were so extremely jealous that not one of them would allow his prospective bride to remain at any time in the company of another man, or men, unless he himself were present also. Now, the boat would only hold two persons, though it could, of course, be rowed by one, and it seemed impossible that the four couples would ever get across. But midway in the stream was a small island, and this seemed to present a way out of the difficulty, because a person or persons could be left there while the boat was rowed back or to the opposite shore. If they had been prepared for their difficulty they could have easily worked out a solution to the little poser at any other time. But they were now so hurried and excited in their flight that the confusion they soon got into was exceedingly amusing—or would have been to any one except themselves.
As a consequence they took twice as long and crossed the river twice as often as was really necessary. Meanwhile, the Colonel, who was a very light sleeper, thought he heard a splash of oars. He quickly raised the alarm among his household, and the young ladies were found to be missing. Somebody was sent to the police-station, and a number of officers soon aided in the pursuit of the fugitives, who, in consequence of that delay in crossing the river, were quickly overtaken. The four girls returned sadly to their homes, and afterwards broke off their engagements in disgust.
For a considerable time it was a mystery how the party of eight managed to cross the river in that little boat without any girl being ever left with a man, unless her betrothed was also present. The favourite method is to take eight counters or pieces of cardboard and mark them A, B, C, D, a, b, c, d, to represent the four men and their prospective brides, and carry them from one side of a table to the other in a matchbox (to represent the boat), a penny being placed in the middle of the table as the island.
Readers are now asked to find the quickest method of getting the party across the river. How many passages are necessary from land to land? By “land” is understood either shore or island. Though the boat would not necessarily call at the island every time of crossing, the possibility of its doing so must be provided for. For example, it would not do for a man to be alone in the boat (though it were understood that he intended merely to cross from one bank to the opposite one) if there happened to be a girl alone on the island other than the one to whom he was engaged.

7) Summer Tourists
Sam Loyd, as number 207 of his Cylopedia of Puzzles, comes up with a small variation:

As a preface to a very interesting problem which shows how a company of very quarrelsome picnickers might cross a stream in the same boat without upsetting it, I shall take for granted that all puzzlists, young and old, are familiar with the ingenious tactics of the boatman who had to ferry a fox, a goose and some corn across a river in a small boat “built for two”.
There is a German version of the story which tells of a peasant with a wolf, a goat and, I think a tomato can, which he was to get across the river in a way to circumvent the wolf’s love for goat meat, as well a the natural tendency of the tomato can to telescope into the goat. Eithe of the stories, a familiarly told, possesses interest for the juveniles, and when solved would strengthen a branch of the memory and reasoning powers not generally called into exercise. To a trained puzzlist the problem poses no problem whatsoever, but to one not versed in such matters, if he will just try to run the solution through his mind to test mentally just how many times the boat must cross the river, he will speedily realize what a valuable school it is for learning to concentrate the thoughts.
I wonder, however, if any of our readers who are familiar with both stories have chanced to realize what a funny state of affairs might arise if the two incidents were combined in one? That is a trick I often resort to when I have a couple of easy puzzles which are susceptible of being twisted together into one genuine poser.
Added by the accompanying picture, which explains the situation in a way that words would fail to do, we will tell the story of a party of tourists, who, returning from a picnic were compelled to cross a stream in a small boat, which would hold but two at a time, and none of the ladies could row.
It so happened that Parson Cinch, the popular coloured preacher, has quarreled with the other two gentlemen, and as a result Mrs. Cinch had a falling out with the other ladies.
How is it possible for the gentlemen to conduct them all across the stream in such a way that no two disagreeing parties shall ever cross over together or either remain on either side of the stream at the same time. Another curious feature of the strained relations being that no one gentlemen should remain on either side with two ladies.
The puzzle is merely to show how many times the little two seated boat must cross the stream, to ferry the entire party over; but I take occasion to say that not one person out of a thousand is endowed with a headpiece which would figure it out mentally, without recourse to pencil and paper, although the faculty of doing so may readily be acquired.

In the unlikely case that you are hopelessly lost, peek here.

8) The four elopements

Of course all good puzzlists are familiar with the time honoured problem of the countryman who had to ferry a fox, goose and some corn across a river in a boat which would carry but two at a time. The story of the four elopements, equally old, is built upon similar lines, but presents so many complications that the best or shortest answer seems to have been overlooked by mathematicians and writers upon the subject.
It is told that four men eloped with their sweethearts, but in carrying out their plan they were compelled to cross a stream in a boat which would hold only two at a time. It appears that the young men were so extremely jealous that not one of them would permit his prospective bride to remain at any time in the company of any other man or men unless he was also present.
Nor was any men to get in the boat alone, when there happened to be a girl alone or on the island or shore, other than the one to whom he was engaged. This feature of the condition looks as if the girls were also jealous and feared that their fellows would run off with the wrong girl if they got a chance. Well, be that as it may, the problem is to guess the quickest way to get the whole party across the river according to the conditions imposed. let us suppose the river is two hundred yards wide, with the island in the middle. How many trips would the boat make to get the four couples safely across in accordance with the stipulations?
Don’t spoil puzzle fun to quick by peeking at the solution

9) Four jealous couples and a picnic

It occurred to me that Sam Loyds puzzle with four couple and an island, described fully above, can be taken slightly further. Again we have four couples, a boat for 2 persons to cross the river, and an island.
Again the boys have that awful stroke of jealousy, which forbids them to let one of their friends to be with their girlfriend if he is not present himself.
But in addition, the girls have prepared a huge bag with food for the pick-nick. The bag is so heavy that it wont fit into the boat if it already holds two persons, it has to be ferried across by one person. The food smells so good that girls don’t allow the boys to be with the bag with food if not at least one girl is there to keep watch on the food.

You can find the solution at number 141

UPDATE 2016, December 17
Peter Rowlett ran an interesting discussion on the sexist nature of the three couples puzzle. One reformulation of the puzzle, which maintains the personal relationship aspect, is:
Three actors and their three agents want to cross a river in a boat that is capable of holding only two people at a time, with the constraint that no actor can be in the presence of another agent unless their own agent is also present, because each agent is worried their rivals will poach their client. How should they cross the river with the least amount of rowing?
The variation was suggested by James Summer.

River crossings(2)

The group of river crossing puzzles that I want to have a look at in this post is best characterized by its oldest specimen, that of the farmer, wolf, goat and cabbage. Chances are that you have a chicken instead of the goat, wheat instead of the cabbage or a fox instead of the wolf.

One form is:

1) a wolf, a goat and a cabbage^*
A farmer bought a wolf, a goat and a cabbage at a market. On the way back home he has to cross a river. His small boat will hold, aside from him self, just one item.
If he leaves the wolf and the goat together, the wolf will eat the goat.
If he leaves the goat and the cabbage together, the goat will eat the cabbage.
How does he get everything across the river?
In all these puzzles there are no ropes, bridges or other tricks. Just play the ferryman.
You would disappoint me if you need a solution for this old traditional, but for the sake of completeness it is You can find the solution here

Like many river crossing problems it dates back the middle ages, and is found in the manuscript Propositiones ad Acuendos Juvenes, which is generally attributed to generally attributed to Abbott Alcuin.

The puzzle has been found in the folklore of African-Americans, Cameroon, the Cape Verde Islands, Denmark, Ethiopia, Ghana, Italy, Russia, Romania, Scotland, the Sudan, Uganda, Zambia, and Zimbabwe.[2], pp. 26–27;[7] It has been given the index number H506.3 in Stith Thompson’s motif index of folk literature, and is ATU 1579 in the Aarne-Thompson-Uther classification system.

In some parts of Africa, variations on the puzzle have been found in which the boat can carry two objects instead of only one. When the puzzle is weakened in this way it is possible to introduce the extra constraint that no two items, including A and C, can be left together.

2) One example of an extension with 4 items^*
A farmer has to take a fox, chicken, caterpillar and crop of lettuce with his small ferry boat across a river. His small boat can hold 2 items aside from himself.
The fox would eat the chicken if they are left unattended.
The chicken would eat the caterpillar if left unattended
The caterpillar would eat the lettuce if unattended
How can he take everything across?
You can find the solution at here

That puzzle is rather simple, so we can easily expand it 1 item further:
3) 5 items^*
A farmer has to take 5 items, a fox, chicken, spider, caterpillar and crop of lettuce with his small ferry boat across a river. His small boat can hold 2 items aside from himself.
The fox would eat the chicken if they are left unattended.
The chicken would eat the spider if left unattended
The spider would eat the caterpillar if left unattended
The caterpillar would eat the lettuce if unattended
How can he take everything across?
See Solution

As I told above, in Africa several regional variations have developed. Here is one 4) african variant^*:
A young warrior returns to the village with a young lion, a young tiger and a young leopard. He must cross a small river, but his tiny canoe will only hold 2 items besides himself. Each of these animals will attack any of the others if left unattended. How can he take them all three across?
See Solution

There is a slightly more subtle way to extend the puzzle to 4 items. Serhiy Grabarchuk came up with this variation:
5) The fox, the goose, the grain, and the dog^*
This time, the farmer has to transport a fox, a dog, a goose, and some grain across a river. He has a boat which can carry himself and either the fox, dog, goose, or grain. If the farmer isn’t present, the fox cannot be left with either the dog or the goose, or both. If need be, the goose can be left with the grain provided the dog is present because the dog will guard the grain and won’t eat the goose. Help the farmer cross the river.

(This puzzle is from The New Puzzle Classics by Serhiy Grabarchuk, Sterling publishing company, New York, 2005.)
The mouse, the elephant, the dog, and the cat

For yet another variation and a nice discussion of it, see The lettuce-fearing leviathan in the book A fine math you’ve got me into by Ian Stewart.
(the text above comes from http://www.mathfair.com/rvrcrossing.html).
You can look up the Solution

6) 2 wolves, a dog, a goat and a bag of grain
The may issue of Quantum also came with a small variation:^*
A farmer was trying to cross a river in a boat which held him and two items. He had five items to transport to the other side: two wolves, a fierce dog, one goat and one bag of grain. When the farmer was not around, either wolf would eat the dog or the goat, the dog would eat the goat and the goat would eat the grain. How could the farmer transport all five items across the river?

You will find the solution as Solution 134

Some people at MIT took this puzzle type into space. The puzzles are all framed as characters from a cartoon science fiction series called Futurama.
Their puzzles are all placed in the future, with exotic names for stuff that, if you are not familiar with the series, you may find hard to remember. I prefer a translation into here-and-now things. Here we go, this is my contribution to the field:

7) 6 cargoes^*
There are 6 cargoes to be transported over a river by boat from the southern to the northern shore.
The boat may hold 3 persons, including crew, and 1 cargo.
The ship starts at the southern shore.
The ship needs a 2 person crew. The only approved crew combinations are Bill and Bruce, and Lily + 1 other person.
The ship will make 6 trips to the northern bank and 6 trips back.
Not all persons and all cargo may be combined on the ship or on one of the river banks. See the conflict table below.
No one needs to leave the ship in order to pick up of drop of a cargo. Persons and cargo may be transferred simultaneously, so that a cargo is loaded on the ship while a person conflicting with the cargo disembarks at the same time, or vice verse.
At the end of the mission, all cargoes must have been transported to the northern shore. All persons must be back on the southern shore or on the ship.
There may be multiple crew combinations, but there is only one order in which the cargoes can be transported.
Starting positions:
Bill, Bruce and Lily: on the ship
On the northern shore: Alice, Mary, Peter, Quince.
All packages start on the southern shore.

Conflict table:

	Goose	Cheese	Guitars	Cardboard	Bananas	Radios	Persons
Bill				X		X
Bruce		X			X
Lily							Quince
Alice				X	X
Mary			X		X
Peter			X			X
Quince	X		X				Lily

You can check the Solution 73

8) The pigs, peanuts and lilies^*

You are at the planning desk of a small freighter cargo. Both John and Jack can handle the ship. Your transports are between Northport, Southport, and Island. The ship can handle either two persons or one person and one freight. The ship starts in Southport. And as you can guess, the ship needs at least one crew member.
a) Jack is on the ship in Southport. Jack is allergic for peanuts.
b) In Northport John is available. John is allergic for pigs.
c) In Northport there is a cargo of peanuts, which needs to go to the Island.
d) In Southport there is a cargo of pigs, which needs to go to Northport.
e) On the Island there is a cargo of lilies, which needs to go to Southport.

If someone is allergic to an object, he will not go ashore. He will go to a harbor with such a cargo, but will not leave the ship to pick up any cargo. Neither may, if a crewman is in a harbor, such a “toxic” cargo be dropped off in that harbor. There is only one gangway, so it is impossible that crewman A loads (resp. unloads) a cargo while crewman B, who is allergic to that cargo, leaves the ship (resp. boards it).
Roster the transports! What is the minimum number of shipments needed? It does not matter where the ship and the crew end.

River crossing (1)

There are many river crossing problems, and in this post I’d like to take a look at one of them. The basic of river crossing puzzles go back to the book Propositiones ad Acuendos Juvenes, probably published around 900AD.

In this first post on river crossing problems I’d like to take a look at a simple river crossing problem:
1) Man, wife and 2 kids^*
A man and a woman of equal weight, together with their two children, each of half their weight, wish to cross a river using a boat which can only carry the weight of one adult.
How many trips do they need?

For the solution see Solution 4

Because this type of puzzle is so old, it has spread wide. Here is a Russian variant:
2) Three soldiers^*
Three soldiers must cross a river. Two boys have a boat and are willing to help. Their small ferry can hold either the two boys or one soldier. How many moves are necessary to get all across?

For the solution see Solution 43

It is easy to see that the two boys can ferry an arbitrary number of soldiers across, the puzzle becomes in a way easier when the boys have to ferry 10 or 15 soldiers across, as the reader is forced to design a scheme to do it.
In fact, that is exactly what the famous British puzzle author Henry Dudeney (10 April 1857–23 April 1930) did when he formulated the puzzle as:
3) The British batallion^*
During the Turkish stampede in Thrace, a small detachment found itself confronted by a wide and deep river. They discovered a boat with two rowing children. It was so small that it could hold only the two children, or one grown up person.
How did the officer get himself + his 537 soldiers across the river and leave the two children in possession of their boat? And how many times need the boat to pass from shore to shore?
Henry Dudeney published this puzzle ands Martin Gardner republished it in “536 puzzles & Curious problems”. I still wonder if there is any relation between the 536 and the 537.

For the solution see Solution 53

Dudeney also published this small variation:
4) The Softleigh family^*
During a country ramble Mr. and Mrs. Softleigh found themselves in a pretty little dilemma. They had to cross a stream in a small boat which was capable of carrying only 150 lbs. weight. But Mr. Softleigh and his wife each weighed exactly 150 lbs., and each of their sons weighed 75 lbs. And then there was the dog, who could not be induced on any terms to swim. On the principle of “ladies first,” they at once sent Mrs. Softleigh over; but this was a stupid oversight, because she had to come back again with the boat, so nothing was gained by that operation. How did they all succeed in getting across? The reader will find it much easier than the Softleigh family did, for their greatest enemy could not have truthfully called them a brilliant quartette—while the dog was a perfect fool.

For the solution see Solution 63

Hats, caps and cards

The first time I read this puzzle was in Willy Hochkeppels “Denken als spel”, somewhere in my youth.

1) The puzzle is simple: A geek kind of sultan had 3 prisoners. He showed them 5 hats: 3 black, 2 white. He blindfolded them, and then put a black hat on each of their heads. He took off their blindfolds. None could see the hat on his own head, and they were not allowed to take it off. Each could however see the hats on the heads of their fellow prisoners.
“If you can tell me what head is on your own head”, he told them, you are free.
The prisoners looked at each other for considerable time. Then they declared together: we all have a black hat.
How had they deducted this?

Solution: nr 1

The puzzle can be told in several settings. Sometimes people are prisoners of a Japanese officer in WW 2, or they are volunteers searching the hand of the daughter of the sultan.

Yesterday a fellow worker, Jon Koeter, told me a similar puzzle:
Four people are shown 2 square hats and 2 triangular hats. One is positioned at one side of a wall, the other three are queued at the other side. They are all facing the wall. Each one can only see the people and hats in front of them – they are not allowed to look behind them or look what hat they have themselves. They are told that the game will stop when one one of them knows the answer – they can hear each other, but are not allowed to talk about their hats.

Still, after a while, one of them says: I know what hat I have.
How does he know?

Solution: Nr 11

3) This puzzle has been made into a game by famous game inventor Robert Abbott, using ordinary playing cards. Each player gets a cap which can hold three cards. The players each get three card stuck on their cap which all fellow players can see, but no one can see his/her own cards. Players may ask each other Y/N questions, such as : do you see 3 jacks? Or: do you see 2 clubs? Is the sum of the numbers you see greater than 15? The first person to know the cards on his own cap wins.

Socks, shoes, gloves and boots

Socks, shoes, boots and gloves.

An old puzzle, the origin of which I was unable to find, is this:
1) My socks are in a dark room, where I can only feel them, not see them. I have 4 black and 4 blue socks. How many socks must I take out to be sure that I have 2 of the same color?

Solution: nr 2

There are numerous variations. A well known variation is where the socks are replaced by shoes. The colours are replaced with the left and right side of the shoes, and people are not allowed to fit them. Other variations are to replace the socks with boots or gloves. These variations are merely cosmetic, they do not change the combinatorial reasoning behind the puzzle.

3) The original puzzle has equal number of socks for both colours. But this is not necessary. It is perfectly valid to have different numbers of socks in the two colours:
You socks are in a dark room. You have 4 blue and 5 black socks. It is too dark to see what colour a sock is. How many socks do you need to take out to be certain you have 2 socks in the same colour?

Solution: nr 22

4) Raymond Smullyan, in his book “What is the name of this book?”, came up with two variations.
In the first one he asks: In the dark room are 4 blue and 4 black socks. How many socks should you take out of the room to be sure you have two socks in DIFFERENT colours?

Solution: nr 32

5) The second variation is: In a dark room are blue and black socks in equal numbers. Suppose the number of socks I must take out to be sure of 2 socks in the same colour happens to be equal to the number of socks I must take out to have 2 socks of different colours, how many colours are there?

Solution: nr 42

6) One variation I came up with, only to learn that others had thought of the same variation, is:
There are 3 socks in each of the colours blue, gray, brown and black in a dark room. How many socks must I take out to be certain that I have two socks in the same colour?

Solution: nr 52

Another variation:
7) Suppose there are an equal number of socks in several colours in a dark room. I tell you that you must take out 6 socks to be certain that you have 2 socks in the same colour. How many colours are there?

Solution: nr 62