This is a real problem that was sent around my former maths department. The inquirer had a boat, and he wanted ropes of various lengths to knot together to moor his canal barge (I think each rope may have somehow used an eye splice for knotting). This is more or less the e-mail as I received it:
“I have 5 pieces of rope of length:
- 1 x 10 metres
- 2 x 12 metres
- 2 x 40 metres
I want to be able to cut the ropes into pieces of different lengths and to be able to tie combinations of these together to make longer lengths.
Is there a formula to obtain the optimum number and lengths of pieces ropes (i.e. the minimum number of pieces of ropes to give the most possible combinations of lengths of rope!). The minimum length of rope I need is 6m.”
Being more or less a combinatorial problem, I doubted whether any nice formula existed (or that it would be any more useful than a specific solution!). So, wanting to help, I cheated slightly, and chatted to the guy to get a bit more info. After our discussion, he decided that he wanted ropes with at most two knots (ie. three pieces), and to be able to make lengths at intervals of one or two metres. He also was quite keen on having a 20m rope.
I’ve given some additional assumptions and my solution below. But please have a go first: you may come up with a better way of doing it!
After the discussions, I also decided that I should try to meet the following criteria, roughly in the order below, the most important being at the top:
- Try to create ways of combining ropes to get most of the integer lengths between 6m and 20m, with no more than two knots; the maximum gap between attainable lengths should be two metres;
- Ropes should be of integer length (not necessary, but makes the calculations easier, both initially by reducing the number of options to be explored, and while the ropes are actually being used on the water);
- Minimise the number of knots used;
- Allow for some longer combined rope lengths, minimising the gaps between those;
- Minimise the number of ropes cut (to avoid work, weakening ropes and simplify the instructions).
The guy’s initial thought was that, to have jumps of one or two metres, you would need a rope of one or two metres in length. This may seem like quite an obvious conclusion, but it isn’t actually the case: as long as you have a sufficient number of small ropes at various lengths, you can avoid having this (tiny ropes are perhaps annoying for knotting).
My main consideration was to avoid ropes of identical lengths, including those lengths obtained by combining ropes. If you can make one length in two possible ways, you’ve essentially wasted a combination.
I was fortunate, and my solution turned out to be quite neat:
- Cut a 12m rope into: 3m, 4m, and 5m.
- Cut a 40m rope into: 6m, 14m and 20m.
- Leave the 10m, and the other 12m and 40m ropes as they are.
This would leave us with 3m, 4m, 5m, 6m, 10m, 12m, 14m, 20m, and 40m ropes; with these you make any rope integer length from 3m to 20m with at most one knot, and quite a few more beyond that. Resorting to two knots gives an even better range.
He seemed quite happy with it, which is, in my books, a mathematical success!
Another more general way of approaching such problems was suggested by someone else in the department. It went a little like this: if you cut a rope in half, and then cut one of those halves in half again to make quarters, and so on, you can theoretically make any length of rope (up to the length of the rope you’ve cut up). As we’re in the real world, and can’t use infinitely small objects, instead of cutting up into precise halves, you can make one piece slightly longer and one piece slightly shorter, and stop much earlier in the process (if you were using only one piece of rope, and wanted at most knots, you would stop after cuts or iterations).
I thought at the time this was slightly impracticable, but looking back, my more or less combinatorial guess can be viewed in those terms:
- Cut a 12m rope into: 5m and 7m (m).
- Cut the new 7m rope into: 3m and 4m (m).
- Cut a 40m rope into: two 20m ropes.
- Cut one of the new 20m ropes into: 6m and 14m (m).
As in this example, in general we should vary the ‘halving error’: for example, if we cut ropes of length into , then we can now recombine them to make and . However, if , then we are again wasting an option by being able to construct in two different ways.
I was also happy with my intuitive solution, and I didn’t think I could do much better. Having said this, perhaps there is an obvious slightly better solution? Or, if you started measuring the outcomes, perhaps you can start to sensibly try out and evaluate combinations of non-integer lengths. We might, for instance, aim to minimise the sum of the squares of the gaps between possible lengths up to 40m, mine giving a score of when using a maximum of one knot, as we can’t make lengths of 1,2,21,27–29,31,33, or 35–39m. A score of 40 would be an absolute (though probably unattainable) lower bound for integer-lengthed rope.
In my solution, I could wastefully make 9,10,14,15,17,16,18,20,24 and 26m in two ways, leading to the 8+28-10=26 possible lengths under 40m (8 is the number of individual lengths of rope under 40m; 28 (=8 choose 2) is the number of ways of knotting two of those 8 lengths of rope; and 10 being the number we can make in two ways). Perhaps you could profitably start by eliminating some one those redundant combinations?