Drawing Without Picking Up Your Pencil

When I was five years old, a kid in my neighborhood challenged me with a puzzle that I've remembered ever since. As it turns out, there's much more to this puzzle than meets the eye.

Puzzle 1: Draw this shape without picking up your pencil or redrawing the same stretch of line more than once.

This puzzle seems relatively benign. Mess around with it for a bit and you'll get it. A less obvious version comes from the Kuba children in the Congo, who took this puzzle much, much farther. The story, related by anthropologist Emil Torday, goes like this: the children were drawing complicated networks in the sand. When they saw Torday, they challenged him to draw the pictures in the sand without picking up his finger or drawing the same stretch more than once.

"The children were drawing," said Torday, "and I was at once asked to perform certain impossible tasks; great was their joy when the white man failed to accomplish them."

The picture the children challenged Torday with is the next puzzle. And it is, as those children knew, possible to draw.

Puzzle 2: Draw this shape without picking up your pencil or redrawing the same stretch of line more than once.

What those children knew is the same thing that mathematician Leonard Euler figured out when he tackled the famous Bridges of Königsberg puzzle.

Puzzle 3: Why is it impossible to to take a walking tour of Königsberg that crosses all 7 bridges exactly once?

What's extraordinary is that Euler and the Kuba children looked deeper into the structure of these puzzles and asked what about the fundamental structure would make it possible to know whether a network could be drawn without lifting your pencil or repeating lines, but without tedious trial and error. How did they do it?

These types of questions are part of an area of mathematics known as graph theory. It's a fascinating area of study. The objects of interest are precisely these kinds of networks. It's worth noticing that the walking tour of Königsberg is quite different on the surface than the "house" image in puzzle 1. However, if we put dots on each side of the bridges, and replace the bridges with connecting lines, Königsberg is just another graph, or network.

Does it matter if the connecting lines are curved or straight? Not for our purposes. In fact, we could abstract the information in a graph like the "house" in puzzle 1 as follows. Label the five points A, B, C, D, and E, and keep track of which pairs have an edge drawn between them: AB, AC, AD, AE, BC, BD, CD, DE. Then we could hand that information over to someone else who could redraw that image however they liked. They could move the points around, or draw curved connecting edges, or squiggles. As long as the points and connections encode the same way, it's essentially the same graph.

This flexibility of information makes graph theory surprisingly important in mathematics. It is possible to use graphs to solve deep problems in geometry and topology. Graphs have also been critical in understanding networks of people and organizations, and can be used to model the spread of disease and forest fires.

Here's a final, more open puzzle to conclude today's column.

Puzzle 4. Given any graph, find a simple way to check whether it is possible to draw the graph without picking up your pencil or redrawing an edge.

Solutions

At the heart of all these puzzles is a remarkably simple observation, which comes down, once again, to parity, or the idea of evenness and oddness.

The fundamental observation that solves all these puzzles is that there are two special points in a path drawn with a single, unbroken, pencil line: the beginning and the end. Consider any other point along the path, and count the number of edges connected to that edge. While the beginning and ending points connect to a single edge, every other point connects to two edges, the one we drew into the point, and the one we drew going out of that point.

So far, so good, but what if our path loops back through these points?

Again, every time the path winds back through a point it has already visited, it adds another two edges to that point. So if the point was even before, it stays even. If the point was odd before, it stays odd.

And that simple insight completely solves the problem! And also gives us the solution for the fourth puzzle. For the path to be drawable with a single pencil according to our rules, it must have no more than two points with an odd number of edges touching them, and those two points are the beginning and end (or end and beginning). This gives us a remarkably easy way to solve the first three problems as well.

For these two puzzles there are exactly two points with an odd number of edges coming from them. Those are the places to start drawing or end drawing.

For the bridges of Königsberg, there are four points with an odd number of edges coming from them. That means it can't be drawn! There would need to be two beginnings and two ends, so it can't be done.

This is one of my favourite examples of how deeper mathematics hides in unexpected places, and how taking a step back and looking at the structure of things can save us from tedious work.

Drawing Without Picking Up Your Pencil

Source: https://www.thehindu.com/children/do-this-without-lifting-your-pencil/article21247929.ece

Bagikan Artikel ini