How do I explain the Königsberg Bridge problem to a child?

Question

I am going to demonstrate the Königsberg seven bridge problem in a science exhibition. I am also going to use a model for a more visual representation of the problem. Now, how do I explain this (the solution) simply to a child who is not too much familiar with high school mathematics. How do I approach the demonstration to make it appear more attractive?

Answer 1

Cookie Monster is facing four jars of cookies with seven trails of cookie crumbs between them.

Obviously, Cookie Monster does not want to go from jar to jar without also eating the trails of crumbs between them.

Answer 2

Please help me hand out these blank pieces of paper and some crayons. Now look at this weird picture:

Can any of you draw a copy of this picture without lifting your crayon off the paper, and also not tracing the same line twice?

Answer 3

When I was a kid (about 8?), a riddle that would be making rounds was to draw this shape without lifting your pen:

This is more of an 8 bridge problem, and also not "visit all nodes" but "visit all edges", if that is important to you. Anyway, if you actually show the solution quickly to very young children, they are convinced that a solution is possible, but don't have time to remember your steps (and to a child the problem seems trivial, they have to try doing it to see what the big deal is). For cleverer kids you can draw the edges in random order to avoid spoiling the solution.

Technically, you need to explain that going over the same edge twice is not allowed, and going parallel to an existing edge is not allowed... But usually kids grasp intuitively that these sorts of tricks are cheating. Also if they do double edges, then the result looks clearly different from what you asked for. It might help to do it on graph paper, since the lines look like "potential edges".

The problem is soluble by brute force. A determined child trying variations at random will probably discover it after a few minutes, and it's not a huge insight to try each edge in turn systematically. So it's a pretty nice example.

Answer 4

The picture and model of the bridges is clear. No need to change it to kiddy stuff in the weird belief kids don't know what bridges are but know what rooms and walls are (which are much harder view abstractly).

To explain the answer simply point out that the hiker has to start at a starting place; end at an ending place; and all the rest of the places are passing through places. The passing through places must have a the hiker coming in and going out; coming in and going out; coming in and going out. But some of them have three number of bridges going to them so the hiker can come in (1), go out (2) and come in (3) and then the hiker is stuck there because he's used up all his bridges and he can't go out. So this isn't a passing through place. It must be a starting place or an ending place. Here's another with three bridges. It must be a starting place or an ending place. Here's a third place with five bridges. He goes in; out;in; out; and in-- and he's stuck. So it can't be a passing through place. So IT has to be a starting place or an ending place too. But wait! There can only be two starting and ending places. This is impossible! he has to get out by walking over one of the bridges a second time. The hiker can't cross each bridge exactly once.

The tracing an envelope puzzle maybe should be shown first because it is less frustrating to a child because it can be solved. (Abstractly, young children sometimes have a hard time conceptualizing things can't be done via contradiction.) In the envelope, you can point out that that only the starting and ending points can have odd paths from it. There are exactly two points with odd paths so you must start at one and end at the other. Then a solution is pretty easy. But if you start at any other point it can't be done, try it. path out... path out... .... path in and oops! we're stuck! We must start and end at a place with odd number of paths... now look at this map of bridges...

Answer 5

When I was a child, this was a very common and fairly well known problem...

The fact that this is impossible for the same reason as 7 Bridges is fairly interesting.

As for explaining the solution... I don't see why a high school education would matter. It's all about counting evens and odds.

If you have a room with an odd number of doors, and you start outside of it, and you must cross every door, then you must end your path inside the room. Once you understand that, you have the proof.

The problem above has four nodes with an odd number of exits (outside the box counts as a node), so it's impossible. If you start in one of the nodes you can only end in one of the others.

Similarly, 7 Bridges has four nodes with an odd number of exits.

If the kid walks away knowing that he can determine if a similar problem is solvable by just counting edges, then your job is done. They don't need to fully grok the proof. Just draw some numbers on pictures.

Incorporate this with the answer provided by @Superbest. Draw numbers to show that riddle has only two nodes with an odd number of edges, so it is solvable with you starting in one odd-edged node and ending in another.

Make some printouts and bring some pencils.

Answer 6

This is if you've got kids in the 10-15 range who can appreciate a little more detail and drama, but maybe aren't quite as serious as high-schoolers.

Firefighters of Konigsberg

A firefighter comes to you after saving everybody in an apartment building where all of the apartments were very near a flashover point -- they're only burning somewhat due to oxygen deprivation, but when you open a door or a window the fire builds very quickly in intensity. The building's "rooms" happened to be laid out like the "bridges" of Konigsberg:

So each of these orange rooms was "safe until you enter it": it would start billowing in flames due to the oxygen that the firefighter team was bringing in with them through the doors they open. The two hallways in the middle were really bare concrete hallways with very little to burn, so they offered safe travel.

At the time, the firefighter team chose a very linear path to save everyone:

• First they entered Alice's apartment, and they brought her to the pool. The rescue team outside the apartment then brought in a ladder and got her over the fence surrounding the pool area, and treated her on the North side.
• Then they entered Darryl's apartment, and they brought him to the South street, where soon some other medical professionals were able to help him.
• Then they entered Eric's apartment, and brought him to the pool, where he was evacuated like Alice was.
• Then they entered Bob's apartment, and brought him to the North street.
• Then they entered Carol's apartment, and, having very few options, they brought her with them into Fiona's apartment.
• They rescued Fiona too, and brought them both to the South street.
• When they met up with Darryl there he told them that his wife was exercising in the gym, so two members of the team had to go through the alleyway marked in red. This turned out to be messy because there were trash cans and debris through there which made getting to the window super-slow. They bust down the window shown, got her and another person from the gym, and (depending on which story you prefer) brought them through the now-very-firey first corridor or brought them back through the broken window. It was not a pleasant last step.

The firefighter was upset about the chaos at the very end of this rescue, and in general wanted to avoid the alleyway mid-rescue. The team wants to know whether there would have been a better solution had they visited the rooms differently, possibly by either (a) jumping the fence to start in the pool area, or (b) making their way down the red alleyway at the start, before they had turned all of the rooms into a firey hellscape, and busting the window from the very beginning.

Is there a way to rescue everyone by passing through each of these rooms exactly once, without using the alley in the middle? And if not, what made the alley so special? If they can figure out in advance what the floor plan is, what's the general rule for how they should start passing through rooms?

(Note that this suggests an interesting generalization as many "rooms" can have more than 2 doors.)

Answer 7

Imagine some simple graphs and let him try to draw them without lifting the pen from the paper and without passing through some edge more than once. Let him note by himself that sometimes it's not possible.

Answer 8

How to explain why the problem can't be solved

Do not use usual bridges.Say that you have bridges which collapse if you cross them.

When you cross a bridge ,in front of the entrance you put a

(Because you want to be sure that you will not use it again)
Now explain that you never walk if you see a Stop (parents will love this).

And then the crucial part:

If you walk into a mainland you will make use of two "Stop"
(one entering, and one leaving).
If you walk twice ,you will use four etc.
But there is no possibility for even numbers here so...

Answer 9

Exactly how I would explain it to an adult:

(Present a map of Königsberg)

"Can you walk through Königsberg by crossing each bridge exactly once?"

(Present the equivalent graph and a pencil)

"Can you draw this without lifting your pencil, and without retracing a line you already drew?"

(After giving some time to think)

"These are exactly the same problem. And it is impossible to solve.

Unless you start or end on a dot, note that for each line you draw to it, you have to draw a line from it. Therefore, it has to be connected to an even number of lines. Since you can only start on one dot and end on one dot, that means no more than two of the dots can be connected by an odd number of lines.

Now look at this and count how many dots are connected by an odd number of lines. Do you see why the problem is impossible to solve?"

Answer 10

It's about drawing.

You can tell the child: Let's say we draw this map in one go. We can start at one point X and come back to X. Or we can start at one point X and finish at Y. All the other points are neither start point nor end point of the drawing.

Now we take any of those points that are neither start nor end point, and we look only at that point Z. We don't start or finish at Z. We may never touch Z at all - then there are zero lines at Z. Or we draw a line from the start point X, go all over the place, hit Z and we must leave again because Z isn't the end point - we now have two lines meeting at Z. Of course we can continue drawing and hit Z again and leave it again - four lines. And we can repeat that again - six lines. And so on. No matter how we draw the lines, there must be an even number of lines at every point Z that isn't the start or the end point.

Now look at the map of Königsberg: There are three points where three lines meet, and one point where five lines meet. That's four points with an odd number of lines meeting. That's not possible. There can be only two start and end points. And therefore only two points with an odd number of lines. We have four points with an odd number of lines. Not possible.

Answer 11

I have done this as a summer exercise, laying out a map on a school field or the like using rope to mark the rivers and wooden planks for bridges.

If you have several graphs to trace (I vary it a bit and use, for example, a Hamiltonian path on the projection of a dodecahedron laid out in rope) you can rotate teams between them.

It works well to do it on a large scale and to involve physical activity - more of the pupils learn it rather more easily.

It is useful to have markers for paths already travelled. The Hamiltonian circuit can be done by tracing a piece of rope over the edges (use robust tent pegs to mark the vertices) - but this does take a long piece of rope.