# 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.

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

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:

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.