34
$\begingroup$

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?

$\endgroup$
  • 24
    $\begingroup$ Perhaps this is a better fit for the Mathematics Educators $\endgroup$ – Danu Dec 1 '15 at 20:00
  • 3
    $\begingroup$ Do you want to explain the problem, or the solution? When I was about 8 this was a pretty popular game with my peers ("draw this shape without lifting your pen or going over any line twice"). We would usually solve it by brute force. $\endgroup$ – Superbest Dec 2 '15 at 6:54
  • $\begingroup$ What 'solution'? Has the Konigsberg Bridges problem been shown to have a Eulerian Cycle? By whom, and when? AFAIK, the problem has no solution (according to Euler). @superbest - the problem you showed has a solution (although not one where the end and start nodes are the same), but is orders of magnitude less problematic than the KB problem. $\endgroup$ – GT. Dec 2 '15 at 8:19
  • 2
    $\begingroup$ So this is essentially an ELI5 with actual 5-year-olds? :P $\endgroup$ – Mason Wheeler Dec 2 '15 at 15:45
  • $\begingroup$ What age are the children? $\endgroup$ – shoover Dec 2 '15 at 21:46

10 Answers 10

81
$\begingroup$

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.

$\endgroup$
  • 19
    $\begingroup$ That's a nice trick for motivating used edges becoming ineligible for re-use. It also gently hints at the notion of a greedy algorithm, as well as the fact that sometimes greedy algorithms don't work. $\endgroup$ – Ian Dec 1 '15 at 13:08
  • 11
    $\begingroup$ (nitpick) - 4 jars. 7 trails. $\endgroup$ – Darrel Hoffman Dec 1 '15 at 16:14
  • 36
    $\begingroup$ I'm shocked at how many up votes this got. The question asks for a way to explain the solution, not for a infantile presentation of the problem which is what this answer provides. $\endgroup$ – Git Gud Dec 1 '15 at 20:07
  • 20
    $\begingroup$ @GitGud How do I approach the demonstration to make it appear more attractive? he asks. That I provided. That is also the key to his question, it takes no genius to finish it after that. btw, an infantile presentation of the problem? Isn't that exactly what he asked for? $\endgroup$ – Eric S. Dec 2 '15 at 7:41
  • 5
    $\begingroup$ @EricS. The key word there is demonstration (of the solution if you read the OP). This answer does not talk about the solution (namely that such a path is does not exist) at all, and even less (if that were possible) about a demonstration. $\endgroup$ – Marc van Leeuwen Dec 2 '15 at 10:18
73
$\begingroup$

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

Konigsberg diagram

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?

$\endgroup$
  • 6
    $\begingroup$ +1 I would give the original description in all its glory, then explain that this is an equivalent problem (or maybe the opposite: "what is this drawing a model of? Actually it's a [topological] map of the town of Konigsberg!" ), By actually doing it, one of them may realise it is impossible because all the dots have an odd number of lines. Children may perceive this as a failure, so an "easy" example with no odd nodes and a "hard" example with exactly 2 odd nodes would be useful. $\endgroup$ – Level River St Dec 2 '15 at 1:10
  • 2
    $\begingroup$ (As noted) Repeat demo for several other similar diagrams. Then ask if anyone can guess why you can draw some but not others. $\endgroup$ – cobaltduck Dec 2 '15 at 13:03
  • 2
    $\begingroup$ +1 for the good old "try to draw this without lifting your pencil" puzzle format that does not resort to some ridiculously contrived scenario. It exactly describes the problem without muddying it with nonsense or being condescending like some of the other answers. As a child, I loved abstract puzzles like this. $\endgroup$ – Jordan Dec 4 '15 at 11:10
19
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ Probably not! Euler hasn't found a solution unless you have 8 bridges. $\endgroup$ – SPRBRN Dec 2 '15 at 12:38
  • $\begingroup$ This is a really great example because solving it on the first time pretty much requires understanding 7 Bridges. $\endgroup$ – QuestionC Dec 2 '15 at 17:04
  • 4
    $\begingroup$ @SPRBRN Wait, what? $\endgroup$ – Superbest Dec 2 '15 at 21:02
  • $\begingroup$ I remember this from around the same age :) $\endgroup$ – Engineer Dec 5 '15 at 8:29
  • $\begingroup$ de.wikipedia.org/w/index.php?title=Haus_vom_Nikolaus $\endgroup$ – Carsten S Dec 5 '15 at 17:10
10
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ How many edges are there supposed to be exactly in that? 8 or 16? $\endgroup$ – user2813274 Dec 3 '15 at 16:51
  • $\begingroup$ My illustration as a graph would be 6 nodes, with a total of 16 edges. The Top-Left, Top-Right, and Bottom-Center boxes each have 5 exits. The Bottom-Left and Bottom-Right boxes have 4 exits. The exterior region has 9 exits. Each edge of the graph represents 2 exits (one for each node it connects to) so the 32 exits form 16 graph edges. $\endgroup$ – QuestionC Dec 3 '15 at 23:07
6
$\begingroup$

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:

Firefighters of Koningsberg. Centrally we have a large fenced-off-area marked "Pool" connected to a first corridor connected to a room marked "Gym" connected to a second corridor. The first corridor opens upward into rooms marked "Alice" and "Bob" which open out to the street above; the second corridor opens upward into a room marked "Carol" which opens out into the street above. Similarly the first corridor opens downward to two rooms marked "Darryl" and "Eric" which open into the street below, and the second corridor opens downward into a room marked "Fiona" which opens out into the street below. These named rooms are all marked in orange with a thin alleyway along the right hand side of the block that is marked in red.

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

$\endgroup$
  • 8
    $\begingroup$ I don't get it. There doesn't seem to be any reason that room must be left through a different door/window than what through which it was entered, there is no incentive that the fire fighter team's journey must end where they started, and most of all the "north street", "south street" and "middle hallway" nodes are conveniently connected through the pool area. Also, this "alley hallway" seems to be unrelated and has special rules (or: three nodes connected through one edge)? $\endgroup$ – Bergi Dec 2 '15 at 16:30
  • 2
    $\begingroup$ "the now-very-firey first corridor" - wasn't it said to be safe? $\endgroup$ – Bergi Dec 2 '15 at 16:34
  • $\begingroup$ @Bergi: Thanks for these! (a) Indeed, the impetus to leave through a different door than you entered is simply because the oxygen from the door starts the blaze roaring on that side of the apartment, and that needs to be communicated to the kids, so I guess they went Gym-to-Pool. (b) There is certainly no incentive for the fire fighter team to end where they started -- but there doesn't need to be! (c) Indeed the firefighter who you're talking to needs to view running around the pool as just-as-costly as traversing the alley. (d) The reason the corridor was less-safe was the alley-time. $\endgroup$ – CR Drost Dec 2 '15 at 16:46
  • 2
    $\begingroup$ "an apartment building where all of the apartments were very near a flashover point -- they're only burning somewhat due to oxygen deprivation" That would be completely incomprehensible to all ten-year-olds and most fifteen-year-olds. Also, the whole set-up seems overwhelmingly contrived compared to the original scenario of wondering if you can cross a bunch of bridges exactly once each. $\endgroup$ – David Richerby Dec 5 '15 at 16:29
  • 1
    $\begingroup$ @HelloGoodbye Because the situation is intended for 10-15 year olds, but the full explanation of the situation is intended for grown adults who might be showing this situation to kids. The reader of this site should probably be able to figure out what flashover is and might be able to explain it very simply to a kid, something like "fire needs air as much as it needs fuel, so when you open a door and this air comes in with you, things start burning really fast." Maybe you don't even need to explain it to the kids, depending on how interested they are in firefighting. $\endgroup$ – CR Drost Dec 7 '15 at 21:09
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

enter image description here
(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...

$\endgroup$
  • 1
    $\begingroup$ Nice answer...+1... $\endgroup$ – tatan Dec 4 '15 at 15:34
  • $\begingroup$ Why is it a problem that even numbers are not permitted? Why would you end up with an even number by following this scheme? $\endgroup$ – HelloGoodbye Dec 7 '15 at 12:08
  • 1
    $\begingroup$ @HelloGoodbye en.wikipedia.org/wiki/… $\endgroup$ – Konstantinos Gaitanas Dec 7 '15 at 20:03
1
$\begingroup$

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?"

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

protected by Zev Chonoles Dec 5 '15 at 4:00

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.