Old World Puzzle

A peasant finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Solve this problem for the peasant or prove it has no solution. (Note : The peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage to help him solve the problem. And it goes without saying that the wolf is a protected species.)

==========     ||     ==========

New World Puzzle

There are four people who want to cross a bridge; the all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it can’t be thrown, for example. Each person walks at a different speed : person 1 – 1 minute to across the bridge, person 2 – 2 minutes, person 3 – 5 minutes, person 4 – 10 minutes. A pair must walk together at the rate of the slower person’s pace. For example, if person 1 and person 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If person 4 returns the flashlight, a total of 20 minutes have passed and you have failed the mission.

==========     ||     ==========

Konigsberg Bridge Puzzle

The Konigsberg bridge puzzle is universally accepted as the problem that give birth to graph theory. It was solved by the great  Swiss-born mathematician Leonhard Euler (1707-1783). The problem asked whether one could, in a single stroll, cross all seven bridges of the city of Konigsberg exactly once and return to a starting point. Following is a sketch of the river with its two islands and seven bridges :

 Konigsberg Bridge Puzzle

  • State the problem as a graph problem.
  • Does this problem have a solution? If you believe it does, draw such a stroll; if you believe it does not, explain why and indicate the smallest number of new bridges that would make such a stroll possible.

==========     ||     ==========

Icosian Game

A century after Euler’s discovery, another famous puzzle – this one invented by the renown Irish mathematician Sir William Hamilton (1805-1865)  – was presented to the world under the name of the Icosian Game. The game was played on a circular wooden board on which the following graph was carved :

 Icosian Game

Find a Hamiltonian circuit – a path that visits all the graph’s vertices exactly once before returning to the starting vertex – for this graph.

==========     ||     ==========

Design an algorithm for checking whether two given words are anagrams, i.e., whether one word can be obtained by permuting the letters of the other. (For example, the words tea and eat are anagrams.)