10
$\begingroup$

A rope burns irregularly in 16 minutes and costs 32 rupees, while a second rope burns also irregularly in 7 minutes and costs 14 rupees. Both can be lit only at one end and can be turned off and lit again as many times we want, until they are completely burned. In what way can we count 1 minute by using such ropes and how much will it cost? (Multiple ropes can be used but we are looking for the combination that will cost less).

My attempt: We light the two ropes simultaneously so when the second is fully burnt, 7 minutes have passed, so the remaining from the first one will be burnt in 9 minutes. Then we light a second of 7 mins and this way we have one of 2 minutes. Following the same procedure twice, we can have another one of 2 minutes. Then we light another of 7 minutes, along with the two of 2 minutes one after the other, and we have one of 3 minutes left (7-2-2). Then with the one of 3 minutes and another one of 2 minutes we can count 1 minute.

...but this would be a disaster, cost-wise :)

Any other ideas are most welcome!!!

$\endgroup$
  • $\begingroup$ Never thought I'd see a Die Hard (film) reference on maths.SE, let alone one that I posted, but the "Water Riddle" from Die Hard with a Vengeance is actually relevant/related... puzzles.nigelcoldwell.co.uk/twentytwo.htm -- also, a YouTube link to the video, because why not! =P $\endgroup$ – Sam T Mar 21 at 12:21
  • $\begingroup$ I'm reminded of the barometer question. "Good day, kind Sir, I notice you have a watch. I will gladly give you this 14 rupee rope if you will tell me when a duration of 1 minute has elapsed." $\endgroup$ – Eric Towers Mar 21 at 15:15
  • $\begingroup$ If you cut the $16$ minute rope in half, can you llight one end of both halves? $\endgroup$ – Servaes Mar 21 at 15:19
  • 1
    $\begingroup$ @Servaes Because the rope burns unevenly, cutting the rope in half might mean ending up with a 6 minute rope and a 10 minute rope instead of two perfect 8 minute ropes. $\endgroup$ – Question Marks Mar 21 at 15:23
  • $\begingroup$ @QuestionMarks I understand that, but if you can light one end of both halves, you can cut it in half and light both ends. If one runs out, you cut the other in half and burn that too. This way you can burn the entire 16 minute rope in precisely 8 minutes. $\endgroup$ – Servaes Mar 21 at 16:30
5
$\begingroup$

New answer - 116 rupees

So, apparently we can get even cheaper than 120 rupees, this time by buying only a single 16-minute rope, and six 7-minute ropes (cost is $1 \times 32 + 6 \times 14 = 116$). This is how you do it:

  1. Create a 2-minute rope with the 16-minute rope and two 7-minute ropes (remaining ropes: $4 \times 7, 1 \times 2$)
  2. Use the 2-minute rope to turn two 7-minute ropes into 5-minute ropes (remaining ropes: $2 \times 7, 2 \times 5$)
  3. Use one of the 5-minute ropes to turn the remaining 7-minute ropes into 2-minute ropes (remaining ropes: $1 \times 5, 2 \times 2$)
  4. Use the two 2-minute ropes to reduce the 5-minute rope to the 1-minute rope you really wanted all along

I no longer dare to say this might be optimal.

Old answer - 120 rupees

The cheapest I have been able to work out so far is 120 rupees: 2 16-minute ropes and 4 7-minute ropes (cost is $2 \times 32 + 4 \times 14 = 120$). You do this as follows:

  1. Light the two 16-minute ropes and a 7-minute rope to create two 9-minute ropes (remaining ropes: $2 \times 9$, $3 \times 7$)
  2. Use a 9-minute rope and a 7-minute rope to create a 2-minute rope (remaining ropes: $1 \times 9$, $2 \times 7$, $1 \times 2$)
  3. Light the two 7-minute ropes and the 2-minute rope to create two 5-minute ropes (remaining ropes: $1 \times 9$, $2 \times 5$)
  4. Use the 9-minute rope and one of the 5-minute ropes to create a 4-minute rope (remaining ropes: $1 \times 5$, $1 \times 4$)
  5. Use your 5-minute rope and 4-minute rope to create the desired 1-minute rope

I'm reasonably confident this is optimal, but I have no idea how to conclusively prove it.

$\endgroup$
  • $\begingroup$ +1 Very nice answer! To start a proof of minimality; first note that you will need at least one of each rope, and without loss of generality the first thing to do is to start burning (at least) one of each rope. So the remaining combinations of $(16,7)$-ropes of lower cost are $(1,x)$ with $1\leq x\leq5$ and $(2,x)$ with $1\leq x\leq3$ and $(3,1)$, leaving $9$ situations to check. It isn't hard to see (with some ad hoc arguments) that $(1,1)$, $(1,2)$, $(1,3)$ and $(2,1)$ and $(3,1)$ won't work, leaving $4$ combinations that require actual work... $\endgroup$ – Servaes Mar 24 at 9:50
3
$\begingroup$

Start by creating a 2 minute rope as you described. Then start burning three 7 minutes rope at the same time, for 2 min. You are left with three 5 min ropes. Start burning a 16 minute ropes for three times five minutes.

$\endgroup$
  • $\begingroup$ Dear sir, nice solution but how do we know this is the cheapest? $\endgroup$ – Sal.Cognato Mar 21 at 8:35
  • 3
    $\begingroup$ I don't know. If you can start burning from two ends, then you can find cheaper solutions. Sell some of the ropes and buy watch, might be better :) $\endgroup$ – Andrei Mar 21 at 8:40
  • $\begingroup$ Sorry sir, I didn't mean to offend you. I was just asking - because I read this problem and it seemed interesting to me. $\endgroup$ – Sal.Cognato Mar 21 at 8:52
  • $\begingroup$ I'm not offended. I really don't know how I would even try to prove that it's the smallest price. The clock remark was a joke $\endgroup$ – Andrei Mar 21 at 8:55
2
$\begingroup$

THIS IS NOT AN ANSWER.

Just some thoughts that might help - please let me know if I've misunderstood any questions/answers.

The costs for the 2 kinds of rope are just double the ropes' burn times, so really we're looking to minimise the number of rope-minutes we buy.

The asker's solution involves a [7 minute] rope and 3 [2 minute] ropes. We can make 3 [2 minute] ropes from 3 [16 minute] ropes lit simultaneously with a [7 minute], and then another [7 minute] we light after the first [7 minute] burns. This means we buy 3 [7 minute] ropes, and 3 [16 minute] ropes, for a total of 69 minutes purchased, 138 rupees.

Andrei's solution involves creating 3 [5 minute] ropes, and burning them alongside a [16 minute]. We can create 3 [5 minute] ropes from 5 [7 minute ropes] and a [16 minute] rope - first the [16] burns with the first [7], then with the second [7], then we light the last 3 [7]s and they end up as [5 minute] ropes. This means we buy 2 [16 minute] ropes and 5 [7 minute] ropes, for a total of 67 minutes purchases, 134 rupees.

If we skipped any tricks with creating [x minute] ropes (x!=7,x!=16), we would be burning 7 [7 minute ropes] for 49 minutes, and 3 [16 minute] ropes for 48 minutes, giving us a [1 minute] rope made from the 7th [7 minute] rope. This costs 194 rupees.

I written up these answers in their optimal forms - to create Y [X minute] ropes I assume we can do the process that creates 1 [X minute] rope, but when we light up the rope that ends up being [X minutes] we buy Y of them instead of 1. This is how we can create 1 [5 minute] rope by purchasing 1 [16], 3[7]s, the end rope having started off as a [7], but we can create 101 [5 minute] ropes by purchasing 1 [16] and 103 [7]s, 2 of which are burnt in the process. This is obviously cheaper than buying 1[16], 3[7]s, 101 times.

We have to begin by burning at least 1 [16] and at least 1 [7] - otherwise we're wasting rope, since can't make any guesses or burn at both ends. We must burn at least 1 other [16], because otherwise we're stuck with just a ridiculous number of [7]s (9, by making 4 [5]s (uses up 6) and then burning those as a [20] alongside 3 more [7]s).

So we have to use at least 2 [16]s. Andrei's solution uses that many, and only 5 [7]s - to use only 4 [7]s I think is impossible, given that the 5 is already an optimisation. If we used 3 [16]s we're on par with the asker's solution, so we'd have to use only 2 [7]s - this also seems pretty impossible, not least because we'd be stuck on even numbers.

$\endgroup$
  • 1
    $\begingroup$ Well, if it is not an answer you should not post it as an answer... It would be more appropriate to post one or more comments with the same content. $\endgroup$ – PierreCarre Mar 21 at 14:17
  • 2
    $\begingroup$ @PierreCarre I disagree. This is much too long and detailed for a sequence of comments, is quite useful, may in fact be the germ of an answer, and is properly qualified right at the start. $\endgroup$ – Ethan Bolker Mar 21 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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