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 78 min to solve it. returning to your starting point is not a requirement.
bridges of konigsberg
Moderators: jestingrabbit, Moderators General, Prelates
bridges of konigsberg
President of the peoples republik of the internet.
screw your coffee, i download my java!
screw your coffee, i download my java!
Re: bridges of konigsberg
You can generate these yourself easily. Figuring out the sufficient condition is probably more fun than actually solving these puzzles too.
Re: bridges of konigsberg
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?
Re: bridges of konigsberg
It's true that, for someone who already understands the problem, you won't be able to find a solvable graph that will take 78 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.
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 (40.08 KiB) Viewed 1476 times
Re: bridges of konigsberg
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?
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!
screw your coffee, i download my java!
Re: bridges of konigsberg
This changes nothing.
Spoiler:
Who is online
Users browsing this forum: No registered users and 6 guests