Monthly Archives: October 2011

River crossings (4) – Bigamists


The puzzles in this post are extracted from the previous river crossing post, as that post grew too large. There is a common characteristic too these puzzles, though I find it hard to give an exact definition of this common property.

1) Bigamists
Back to the form of the puzzle with Jealous couples. M.G. Tarry has complicated the problem by assuming that the wives are unable to row. He also proposed a further complication by suggesting that one of the husbands is a bigamist traveling with both his wives.
Steven Kransz’s in his book: “Tecbniques of problem solving” gives a similar variation: “A group consists of two men, each with two wives, who want to cross a river in a boat that only holds two people. The jealous bigamists agree that no woman should be located either in the boat or on the river banks unless in the company of her husband.” That is how Miodrag Petković cites it in his book: Famous puzzles of great mathematicians. The latter condition makes it impossible to solve, and I guess that the latter condition should actually read “The jealous bigamists agree that no woman should be located either in the boat or on the river banks with the other man unless in the company of her husband.”
For the solution, see solution 121

2) A family affair
A recent addition tot his class of puzzles, which surfaced on the web as a flash game, is the following: A father and two sons, a mother with two daughters, and a thief guarded by a policeman want to cross a river. Their only means of transport is a raft able to carry 2 people. There are some problems:
• The Father is a rather nasty guy who will beat up the two girls if the mother is not present
• I regret to say that the Mother is equally nasty and will beat up the two boys unless the father is present
• The thief will beat up the boys, girls and adults if not accompanied by the police.
• Only the Father, the Mother and the Policeman know how to operate the raft
How many trips do you need to get them all across?
The site is in an Asian language, which suggests that the puzzle is of Chinese/Japanese or Korean origin. I welcome any information on the inventor of this puzzle. You can find it here.

You can find the solution at number 131

Actually this puzzle has a strong connection to both the elementary farmer-wolf-goat-cabbage puzzle and the bigamists puzzle.

3) The farmer, the kids and the pets.
Another recent flash based river crossing panel can be found at http://www.smart-kit.com/s888/river-crossing-puzzle-hard/>this site
The rules are simple:
A farmer, his son and daughter, and their pets need to cross a river. The pets are an aggressive dog, 2 hamsters, 2 rabbits. There is a small two-seater boat they can use. All 3 people know how to use the boat, but none of the animals can.

  1. If the farmer is not around, the aggressive dog will bite everyone and everything.
  2. If the daughter is not around, the son will tease the rabbits.
  3. If the son is not around, the daughter will tease the hamsters.
  4. The hamsters and rabbits get along fine with each other.

The solution is number 151

4 ) The two polygamists
Here is a new puzzle, which occurred to me while traveling by car today: Two polygamists, each accompanied by three wives, want to cross a river with a boat that can hold only 2 people at a time. The two men are so jealous, that they wont allow any of their wives to be in the boat, or on one of the riverbanks, with the other man unless he himself is present. An extra complication is that only one of the men, and one of his wives, can row.
How many crossings do they need?

You can find the solution at number 135

Advertisements

The bridges of Konigsberg


This time we make a side step from the previous series of river crossing puzzles. Where you had only a boat ion the previous series of puzzles, this time the only allowed way is to walk over bridges.

The bridges of Konigsberg is a classical mathematical problem solved by mathematician Leonard Euler.
The town of Konigsberg is situated along a river, with two islands in the middle, connected by 7 bridges. On Sunday afternoons, the inhabitants tried to make a walk in such a way that they crossed every bridge exactly once. No swimming or boats were allowed.
Konigsberg bridges
Euler proved that this was impossible, and his prove provided the base for what is now known as graph theory. His concept is simple to understand. He reduced the riverbanks and islands to dots, and the bridges to lines. It will be clear that if an intermediate dot has an uneven number of lines, this knot will have a problem: the walker should exit the dot as often as he enters it. Only at the start and at the end of the walk there can be a dot with an uneven number of lines.

The question of course arises: If it is impossible, and if the mathematics is clear, how can we still use it for puzzles?

Over the past two centuries a few puzzles have been invented. Here they are:

1) The monk
bridges in the monk puzzle
British puzzlemaster Dudeney reduced the problem to one island and five bridges. In this situation the bridges can all be crossed exactly once.
His problem is: If a monk want to start somewhere, in how many ways can he cross all bridges exactly once?
You can check your solution.

2) The two contractors

2a) The contractor on the northern shore.
The town had two important and rich contractors. One lived on the northern river bank, the other on the southern riverbank. The favorite Kneipe, or pub, of both was on the rightmost island with 5 bridges.
Hearing of Eulers method, the contractor on the northern riverbank decided to build an extra bridge at his own cost, which would allow him to start at his home, cross all bridges once, and end for a pint in his favorite pub.
Where did he build this bridge?
You can check your solution.

2b) The contractor on the southern shore.
When the contractor on the southern shore saw the new bridge, he realized that it was impossible for him to make a sunday afternoon trip and end in the same pub. He immediately decide to build an extra bridge at his own cost in such a way that he himself was able to start from his own home, cross all bridges exactly once, and end up in their favorite pub.
Where did he build this bridge?
You can check your solution.

2c) The mayor.
The mayor, seeing the two new bridges, called the two assembly together and decided to build a third new bridge, in such a way that all inhabitants of the town, no matter where they lived, could start from home, cross all bridges exactly once, and end up in the pub on the rightmost island.
Where did he build this bridge?
You can check your solution.

3) The pastor en the penitence
Here is a new puzzle for you:
A mayor with a good sense of history restored the bridges to the original situation at the time of Euler.
However, during one of the many wars in the region, one of the bridges was destroyed and rebuild at another spot. The new situation did allow the citizens to cross all bridges exactly once on their Sunday afternoon walks, provided they lived on either the northern or southern riverbank. See the following illustration:
The situation with one bridge rebuilt in the wrong place.
When one of his parochians confessed him the rather severe sin of eating 7 cakes on a single afternoon, the pastor – for this sin of gluttony – ordered him to make the Sunday afternoon from his home walks in all possible ways.

Starting on the southern riverbank, how many ways are there to cross all bridges exactly once?
You can check your solution.