Every so often, a puzzle comes along with a solution that is so patently, painfully, groaningly obvious, you can't help but overlook it. This is one of those puzzles. I am genuinely ashamed of how long it took me to solve this puzzle, the first time I encountered it.
Sunday Puzzle #26: Links in a Chain
The task: Join the four three-link chains on the left to form the circular chain on the right. To join two chains, you must cut, and then re-weld, a link. What is the minimum number of links you must cut and re-weld to complete the circle?
We'll be back next week with the solution – and a new puzzle! Got a great brainteaser, original or otherwise, that you'd like to see featured? E-mail me with your recommendations. As always, be sure to include "Sunday Puzzle" in the subject line!
Art by Jim Cook
SOLUTION To Sunday Puzzle #25: Solving the Unsolvable Puzzle
When last we met, I presented you with an impossible puzzle. The goal of said puzzle was to draw one continuous line that crossed each of the sixteen line segments in the following figure one time and one time only, without lifting your pen from the page:
But – as I warned you in advance – impossible puzzle is impossible! The goal, then, was to explain why it is impossible.
Conceptual Solution
Several of you were quick to provide correct conceptual answers to this problem, though the first to really lay things out step by step was commenter Lluad, who wrote:
If a shape has an even number of edges then the line has to enter it as many times as it exits - so it either has to contain both ends of the line, or neither end.
If, instead, the shape has an odd number of edges then the line has to enter it as many times as it exits, then enter or exit one more time. So it must contain either the beginning or the end of the line.
There are three rectangles with five edges. Each of those three must contain either the beginning or end of the line. You can't put one of two ends in each of three rectangles, so it's impossible.
This is as good a conceptual explanation to this puzzle's unsolvability as I've seen. Well done! If you're still confused, perhaps you'll find the graphical solution more instructive.
Graphical Solution
This puzzle is very similar to the Seven Bridges of Königsberg, an historical conundrum that, like our line-crossing problem, is actually a mathematical challenge in disguise. More specifically, these puzzles deal with a field of maths known as topology, the study of geometric properties that are unaffected by the deformation of figures.
Like our puzzle, the problem of the Seven Bridges of Königsberg ( which you can read about here) has no solution. We can explain why using something called an Eulerian path, a concept named after Swiss mathematician Leonhard Euler, who originally demonstrated the Königsberg problem's unsolvability in the 18th Century.
In graph theory, an Eulerian path is a trail by which one can traverse every path between a given set of nodes exactly once. If you're not versed in graph theory, that definition probably sounds like a bunch of gibberish; but our line-crossing puzzle is actually a graph theory problem in disguise, and is a useful heuristic in this regard. A "node," in the context of our puzzle, applies to any area that can be visited in the course of drawing our continuous line. For us, that of course means all five of the boxes in the diagram, but it also applies to the entire space surrounding the boxes. This gives us six nodes total (which I've labeled in my sketch, below). The "paths between nodes," in the context of our puzzle, are the various ways that one can cross a line segment separating two nodes:
Above: Our six nodes, and the paths between them
Commenter nopunin10did took a similar approach. Like me, they converted every region of space into a node:
Likewise, nopunin10did converted every crossable line-segment into a path between two nodes – but they drew their graph a little differently. See if you can spot the similarities between the paths in this graph, and the paths I drew in my sketch above (I actually like nopunin10did's graph better):
In both cases, we have an Eulerian trail problem, the aim of which is to determine whether it is possible to traverse every path in the graph exactly once. As nopunin10did explains:
One necessary (but not sufficient) rule for all Eulerian Trails is that there must be exactly zero or two nodes with odd "degree" (degree being defined as the number of paths connecting to that node).
In this representation, the nodes have the following degrees:
A - 9, B - 4, C - 5, D - 4, E - 5, F - 5
As you can see, four of the six nodes have odd degrees. Therefore, per Euler's proof, this graph has no Eulerian Trail. Likewise, there can be no path in the original diagram that crosses each line segment exactly once.
Contact the author at rtgonzalez@io9.com.
from ffffff http://io9.com/this-puzzle-is-so-simple-its-hard-1695744509
via IFTTT
Entradas
0 comentarios:
Publicar un comentario