5
$\begingroup$

We have a rope with a prime unit length, and we need to divide this rope into $9$ ropes by cutting it with prime and/or 1 unit lengths. After cutting the rope, you are supposed to find any kind of unit length (1,2,3,4...) until the original prime unit length by combining these ropes together.

So what is the longest prime length rope you can have with the conditions above?

Note that 1 is a must to find all numbers until the original length so it is allowed to be used.

If this question was asked for 3 rope pieces, the answer would be $5$ with 1,1,3 or 1,2,2 rope length pieces since these are the only possible solutions by using primes and 1.

$\endgroup$
1
  • $\begingroup$ optimisation tag? $\endgroup$ Jun 21, 2019 at 11:27

1 Answer 1

3
$\begingroup$

I think the longest prime length rope we can have is of length

317

Reasoning

Notice that the sum of the lengths of the nine pieces of rope must be odd which means that, if we have a rope of length 2 then we must have another rope of length 2. Otherwise, if we do not have a rope of length 2, we need two ropes of length 1. This leads to the conclusion that the 3 smallest pieces of rope will be either (1,2,2) or (1,1,3).
Given that we then need to be able to create a rope of length 6, we will need one more piece of rope whose length is less than 6 and 5 would be the best choice here to maximise the range of lengths we can achieve. These four pieces of rope, (1,1,3,5) or (1,2,2,5), together add up to 10 so our best option for the next smallest piece of rope would be 11 as this maximises the possible range of sums for the smallest five pieces.

We can continue to apply this reasoning to subsequent choices for the pieces of rope. That is, always choose the next smallest piece of rope to be that whose length is the largest prime which is less than or equal to the sum of the existing pieces + 1. This generates the following possible sequences:
(1, 1, 3, 5, 11, 19, 41, 79, 157)
(1, 2, 2, 5, 11, 19, 41, 79, 157)
In both cases, the sum is 317 which is fortunately also a prime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.