Paving The Bridges

Computer Science Level 1

Seven Bridges

The men in Red Castle want to pave the bridges of Konigsberg with bricks. They will do so by sending out magical paving machines which can pave the bridges as they traverse the bridges. However, their superstitions make them follow these rules:

No paving machine can use a bridge more than once.
No paving machine can leave the land of Blue Castle once it enters it.

What is the maximum number of bridges one paving machine can pave?

The answer is 5.

3 solutions

Peter van der Linden
Oct 13, 2016

Go from red to beer to church and back to red. That's 3 bridges. Now there's 1 bridge left to the beer island. From there on there's only one possibility: going to blue. So 5 is the max because you maxed out the other bridges from and to the other islands.

Explains one possibility, but doesn't address the possibility of another solution with a higher number.

Joshua Nesseth - 4 years, 3 months ago

La Gaudière
Oct 20, 2016

There are 7 bridges. You can only visit the blue side once since you can't go back.

So it's (7-3)+1= 5

Jesse Nieminen
Oct 15, 2016

Only one of the bridges connected to the Blue Castle can be paved, and thus we get an upper-bound of $5$ .
However since, $5$ is possible (Red -> Drink -> Red -> Cross -> Drink -> Blue), the answer must be $\boxed{5}$ .

Technically (though also, as it would have it, trivially), you COULD leave from the island of the Blue Castle once, as there is nothing restricting leaving it if one never "entered" it--i.e. if one started on that island.

This, of course, is a moot point as there are at most 3 other bridges available after this--but simply removing these options is problematic when generalising the problem.

Joshua Nesseth - 4 years, 3 months ago

Sorry, at most 4 other bridges--my bad.

Joshua Nesseth - 4 years, 3 months ago

Paving The Bridges

The answer is 5.

3 solutions

0 pending reports