Monthly Archives: February 2011

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