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?
24$\begingroup$ Perhaps this is a better fit for the Mathematics Educators $\endgroup$– DanuDec 1, 2015 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$– SuperbestDec 2, 2015 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, 2015 at 8:19
2$\begingroup$ So this is essentially an ELI5 with actual 5-year-olds? :P $\endgroup$– Mason WheelerDec 2, 2015 at 15:45
$\begingroup$ What age are the children? $\endgroup$– shooverDec 2, 2015 at 21:46
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.
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$– IanDec 1, 2015 at 13:08
11$\begingroup$ (nitpick) - 4 jars. 7 trails. $\endgroup$ Dec 1, 2015 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 GudDec 1, 2015 at 20:07
21$\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, 2015 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$ Dec 2, 2015 at 10:18
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?
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$ Dec 2, 2015 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$ Dec 2, 2015 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$– JordanDec 4, 2015 at 11:10
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.
$\begingroup$ Probably not! Euler hasn't found a solution unless you have 8 bridges. $\endgroup$– SPRBRNDec 2, 2015 at 12:38
$\begingroup$ This is a really great example because solving it on the first time pretty much requires understanding 7 Bridges. $\endgroup$ Dec 2, 2015 at 17:04
4$\begingroup$ @SPRBRN Wait, what? $\endgroup$ Dec 2, 2015 at 21:02
$\begingroup$ I remember this from around the same age :) $\endgroup$– EngineerDec 5, 2015 at 8:29
$\begingroup$ de.wikipedia.org/w/index.php?title=Haus_vom_Nikolaus $\endgroup$ Dec 5, 2015 at 17:10
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...
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.
1$\begingroup$ How many edges are there supposed to be exactly in that? 8 or 16? $\endgroup$ Dec 3, 2015 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$ Dec 3, 2015 at 23:07
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.)
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$– BergiDec 2, 2015 at 16:30
2$\begingroup$ "the now-very-firey first corridor" - wasn't it said to be safe? $\endgroup$– BergiDec 2, 2015 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 DrostDec 2, 2015 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$ Dec 5, 2015 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 DrostDec 7, 2015 at 21:09
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.
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...
1$\begingroup$ Nice answer...+1... $\endgroup$– SohamDec 4, 2015 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$ Dec 7, 2015 at 12:08
1$\begingroup$ @HelloGoodbye en.wikipedia.org/wiki/… $\endgroup$ Dec 7, 2015 at 20:03
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?"
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.
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.