8 of 100: The Most Efficient Cuts
What is the least number of cuts that must be made in order to completely cut through this rope fence? Note: The knots where multiple ropes meet are too thick to cut through.
This puzzle can be solved intuitively and with trial-and-error, but there's also a beautiful result from graph theory, the Max-Flow Min-Cut Algorithm , that can be used to both solve this puzzle and to quickly prove the solution optimal. Use the link to learn how the result applies!
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Finding 5 places to cut so that the fence is severed is only half of a solution -- in order to really know that 5 is the correct answer, you somehow have to prove that it's impossible to sever the fence in four or fewer cuts.
This solution and proof is a small example of the Max-Flow Min-Cut Algorithm , a beautiful duality in graph theory and linear programming!
Here's an illustration of the strategy that "Max-Flow Min-Cut" enables:
How it works:
Instead of guessing rope-segments to cut, draw in a set of horizontal paths that connect the two posts. Try to draw as many horizontal lines as possible without ever reusing a length of rope (though you can reuse an intersection). Wiggle around and refine your lines as needed to fit in as many as possible. This is called the "Max-flow" perspective, and that terminology hints at a different interpretation of the situation: If each of these ropes were instead a hose with a flow capacity of 1cm of water/second, how much water-per-second could be pumped from the left side of the system to the right side?
Because it's possible to draw in 5 distinct, horizontal lines, we can conclude that 5 cuts are not just sufficient but necessary in order to sever the fence. In order to sever the fence, we have to cut across at least one segment in each green path. So, this 'max-flow' diagram of 5 distinct, horizontal green lines serves as a proof that the fence cannot be severed in four or fewer cuts!
The 5 cuts illustrated above work! And now we've also proven that least 5 cuts are necessary. QED!