bridges of konigsberg

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

IIAOPSW
Posts: 131
Joined: Sat Dec 27, 2008 1:52 am UTC

bridges of konigsberg

Postby IIAOPSW » Tue Aug 18, 2009 1:07 am UTC

greetings glorious citizens of the peoples republik of teh internet

im looking for a solvable (but hard) adaptation of the bridges of Koenigsberg problem. preferably it should take about 7-8 min to solve it. returning to your starting point is not a requirement.
-President of the peoples republik of the internet.

screw your coffee, i download my java!

User avatar
Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Re: bridges of konigsberg

Postby Blatm » Tue Aug 18, 2009 1:24 am UTC

You can generate these yourself easily. Figuring out the sufficient condition is probably more fun than actually solving these puzzles too.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: bridges of konigsberg

Postby quintopia » Tue Aug 18, 2009 8:01 am UTC

It's true. For graphs with solutions, all solutions are really easy to find, and for those without solutions, this fact can quickly be discerned. Not a very interesting class of problems at all. Hamiltonian Tours are much more challenging. Have you tried the Hamiltonian Tour of the dodecahedron, OP?

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: bridges of konigsberg

Postby Buttons » Tue Aug 18, 2009 3:47 pm UTC

It's true that, for someone who already understands the problem, you won't be able to find a solvable graph that will take 7-8 minutes, unless it's a graph so unwieldy that it actually takes that long to find out which vertices have even and odd degree.

But your question isn't unreasonable. It's one I found myself asking just a month ago. I was teaching a class of fifth graders about the problem, so we started by trying to find a solution on the original bridges of Königsburg. After ten minutes with no luck, I had them tackle the "bridges of Budapest." I was pretty liberal with my map (if it's an excuse, I hadn't actually been to the city in three years), and in particular I decided to treat the platform in the middle of Margit bridge as its own zone, with bridges to Buda, Pest, and Margit Island. The map is attached. It took about 8 minutes (likely increased by the time it took for students to walk up to the board, and the fact that fifth graders aren't the fastest writers, and their natural inclination to start on one of the two banks) for them to solve it.

Then we looked at this solution, and how we could find a similar thing for the original problem. What was special about these particular starting and ending points? From there they eventually figured out the rule.
Attachments
bridges.jpg
bridges.jpg (40.08 KiB) Viewed 1476 times

IIAOPSW
Posts: 131
Joined: Sat Dec 27, 2008 1:52 am UTC

Re: bridges of konigsberg

Postby IIAOPSW » Wed Aug 19, 2009 11:40 pm UTC

i've been thinking about it some more...

lets say we augment the original conditions of the puzzle.

you ARE allowed to go over a bridge twice but doing so is like not going over it at all. that is to say, you must go over every bridge an odd number of times.

is it still impossible?
-President of the peoples republik of the internet.

screw your coffee, i download my java!

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: bridges of konigsberg

Postby Buttons » Thu Aug 20, 2009 2:40 am UTC

This changes nothing.
Spoiler:
Suppose you could solve the bridges of Königsberg using these augmented conditions. Now on the original map, replace each bridge i with ai copies, where ai is the number of times that bridge was used in your augmented solution. So now there's a normal solution on this augmented map. However, since each ai was odd (or else some bridge was "unused"), you've added an even number of copies of each bridge, so you haven't changed the parity of the degrees of any of the islands. So such a solution can't exist on the augmented map, so an augmented solution didn't exist on the original map, either.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests