Free the Moose!
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.
Bonus: There is a beautiful way to solve this that is much more elegant than randomly attacking the fence with scissors.
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.
1 solution
This problem and solution is a small example of a beautiful duality in graph theory and linear programming: Max-Flow/Min-Cut.
Instead of guessing rope-segments to cut, on this graph it's much easier to draw in horizontal paths that connect the two posts:
Try to draw as many horizontal lines as possible without ever reusing a length of rope. 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 of the system to the right? Turns out this question has the same answer as our Min-Cut challenge: 8 paths! And it's much easier to find the solution for this particular graph from the max-flow perspective.
Here are 8 example paths:
Finding these 8 paths means that at least 8 cuts will be necessary, since we have to cut across each somewhere in order to separate the fence. So, this 'max-flow' diagram of horizontal lines serves as a proof that "at least 8" is as good as we can do in terms of cut. And drawing and refining the horizontal lines is also a great method for finding a minimal set of edges to cut. Just look for segments on each horizontal path that are on a region also bordered by the path above and the path below:
These 8 cuts work! At least 8 cuts are necessary. QED!