Rope timing

This Riddler problem is all about timing:

Suppose you have four ropes and a lighter. Each rope burns at a nonconstant rate but takes exactly one hour to burn completely from one end to the other. You can only light the ropes at either of their ends but can decide when to light each end as you see fit. If you’re strategic in how you burn the ropes, how many specific lengths of time can you measure? (For example, if you had one rope, you could measure two lengths of time: one hour, by simply burning the entire rope from one end, and half an hour, by burning the rope from both ends and marking when the flames meet.)

Extra credit: What if you had N ropes?

Here is my solution:
[Show Solution]

Note: my solution is incomplete (see comments below!)

13 thoughts on “Rope timing”

  1. Hi Laurent:

    For S3, can you explain the sequence of measurements that will enable you to measure 5/8 of an hour? If I am understanding, this will require you to measure 1/2 of an hour and 1/8 of an hour. Since those are non-consecutive events (i.e. before you get the the last rope burning off in 1/8 of an hour, you will have the 2nd last rope going for 1/4 of an hour) you might not be able to actually “measure” it…

    1. I interpreted “measure” to mean that it’s possible to use a stopwatch that you start and top at specified events and the time indicated on the stopwatch would be the “measured” time.

      We can construct the 5/8 solution by working in reverse. This may seem like a lot of work but it’s very formulaic. As you’ll see, it should be possible to write a recursive computer program that spits out the recipes for each possible number. Here we go:

      1) 5/8 comes from (1+1/4)/2, where 1/4 belongs to S2. Assuming we are able to measure 1/4, we do the following: start the timer, light the rope at one end, wait 1/4, then light the other end. Since there is 3/4 left of the rope and we just lit the second end, it will burn for 3/8. Once it is burnt out, stop the timer. Now 1/4+3/8=5/8. So we have measured 5/8… and all we needed to do was be able to measure 1/4.

      2) 1/4 comes from (1-1/2)/2, where 1/2 belongs to S1. Assuming we are able to measure 1/2, we do the following: light the rope at one end, wait 1/2, light the other end, and start the timer. Since there is 1/2 left of the rope and we just lit the second end, it will burn for 1/4. Once it is burnt out, stop the timer. Now we have measured 1/4… and all we needed to do was be able to measure 1/2.

      3) 1/2 comes from S1 and is found by starting the timer, lighting the rope at both ends, and stopping the timer once the rope is burnt.

      We can now assemble all these pieces of information to construct the solution. Suppose the ropes are labeled A, B, and C. Here are all the steps in the order in which they occur:

      1) simultaneously light A at both ends and light B at one end.
      2) when A burns out: start the timer, light B at other end, light C at one end.
      3) when B burns out: light C at other end.
      4) when C burns out: stop the timer.

      The time elapsed between when we start and stop the timer is 5/8.

      1. I agree with why 5/8 is an option with 3 ropes, but what about 9/8? If you start the timer at the beginning of your example (step 1) and stop at the end, this would be 9/8, which doesn’t seem to be listed. I also noticed for 4 ropes that 19/16 is also possible, which doesn’t seem to be listed.

        The Riddler question is actually much harder than the original question I asked. I was thinking about time points from time 0, while the question says lengths of time which implies your interpretation of starting and stopping the timer. I found there were 23 possible time points from 0 with four ropes, but not sure about possible lengths of time. I believe this should be more than 30 though.

        1. You’re right. My argument is incomplete because it doesn’t account for the incidental measurements that you get for free on your way to measuring a given length of time… I’m not sure how to count these extra cases. I was hoping not to have to resort to a brute-force computer search but it’s looking like this might be the only way. We can at least bound the solution, right? With $N$ ropes, my solution is a lower bound, and an obvious upper bound is to be able to measure from $1$ to $N$ in increments of $\tfrac{1}{2^N}$. So this leaves us with:
          \[
          2^{N+1}-2 \le \text{(solution)} \le N 2^{N}
          \]Not great, but it’s a start.

  2. I don’t see a comment I thought I’d just posted so I’ll try again. I did a brute force search, using the interpretation that measured durations have to be uninterrupted periods of time and not “temporally scattered” ones (start the stopwatch once, stop it once).

    I got the answer 34 for N=4.

    [0.0625, 0.125, 0.1875, 0.25, 0.3125, 0.375, 0.4375, 0.5, 0.5625, 0.625, 0.6875, 0.75, 0.8125, 0.875, 0.9375, 1, 1.125, 1.1875, 1.25, 1.3125, 1.375, 1.4375, 1.5, 1.625, 1.75, 1.875, 2, 2.125, 2.25, 2.5, 2.75, 3, 3.5, 4]

    The Python code is surprisingly slow (takes something like .2 seconds for N=3 and 9 seconds for N=4), so it’s probably not the best approach, but in case anyone wants to see it, it’s here:

    https://gist.github.com/hectorpefo/db9b302f4d33474216da6a81cda28580

    1. I also wrote a Python program to solve this. Here are my numbers for 1-7 ropes. For each number, the first set assumes the timer starts at time 0. The second set contains all of the intermediate start/stop pairs. The two numbers below the two sets are the lengths of the sets. So, for 4 ropes, we agree that there are 34 (23+11) different times that can be measured.

      [0.5, 1.0]
      []
      2 0

      [0.5, 0.75, 1.0, 1.5, 2.0]
      [0.25]
      5 1

      [0.5, 0.75, 0.875, 1.0, 1.125, 1.25, 1.5, 1.75, 2.0, 2.5, 3.0]
      [0.125, 0.25, 0.375, 0.625]
      11 4

      [0.5, 0.75, 0.875, 0.9375, 1.0, 1.125, 1.1875, 1.25, 1.3125, 1.375, 1.4375, 1.5, 1.625, 1.75, 1.875, 2.0, 2.125, 2.25, 2.5, 2.75, 3.0, 3.5, 4.0]
      [0.0625, 0.125, 0.1875, 0.25, 0.3125, 0.375, 0.4375, 0.5625, 0.625, 0.6875, 0.8125]
      23 11

      [0.5, 0.75, 0.875, 0.9375, 0.96875, 1.0, 1.125, 1.1875, 1.21875, 1.25, 1.3125, 1.34375, 1.375, 1.40625, 1.4375, 1.46875, 1.5, 1.53125, 1.5625, 1.59375, 1.625, 1.6875, 1.71875, 1.75, 1.78125, 1.8125, 1.875, 1.9375, 2.0, 2.125, 2.1875, 2.25, 2.3125, 2.375, 2.4375, 2.5, 2.625, 2.75, 2.875, 3.0, 3.125, 3.25, 3.5, 3.75, 4.0, 4.5, 5.0]
      [0.03125, 0.0625, 0.09375, 0.125, 0.15625, 0.1875, 0.21875, 0.25, 0.28125, 0.3125, 0.34375, 0.375, 0.40625, 0.4375, 0.46875, 0.53125, 0.5625, 0.59375, 0.625, 0.65625, 0.6875, 0.71875, 0.78125, 0.8125, 0.84375, 0.90625, 1.03125, 1.0625, 1.09375, 1.28125]
      47 30

      [0.5, 0.75, 0.875, 0.9375, 0.96875, 0.984375, 1.0, 1.125, 1.1875, 1.21875, 1.234375, 1.25, 1.3125, 1.34375, 1.359375, 1.375, 1.40625, 1.421875, 1.4375, 1.453125, 1.46875, 1.484375, 1.5, 1.53125, 1.546875, 1.5625, 1.578125, 1.59375, 1.609375, 1.625, 1.640625, 1.65625, 1.671875, 1.6875, 1.703125, 1.71875, 1.734375, 1.75, 1.765625, 1.78125, 1.8125, 1.828125, 1.84375, 1.859375, 1.875, 1.90625, 1.921875, 1.9375, 1.953125, 1.96875, 2.0, 2.015625, 2.03125, 2.0625, 2.09375, 2.109375, 2.125, 2.1875, 2.21875, 2.25, 2.28125, 2.3125, 2.34375, 2.375, 2.40625, 2.4375, 2.46875, 2.5, 2.53125, 2.5625, 2.59375, 2.625, 2.6875, 2.71875, 2.75, 2.78125, 2.8125, 2.875, 2.9375, 3.0, 3.125, 3.1875, 3.25, 3.3125, 3.375, 3.4375, 3.5, 3.625, 3.75, 3.875, 4.0, 4.125, 4.25, 4.5, 4.75, 5.0, 5.5, 6.0]
      [0.015625, 0.03125, 0.046875, 0.0625, 0.078125, 0.09375, 0.109375, 0.125, 0.140625, 0.15625, 0.171875, 0.1875, 0.203125, 0.21875, 0.234375, 0.25, 0.265625, 0.28125, 0.296875, 0.3125, 0.328125, 0.34375, 0.359375, 0.375, 0.390625, 0.40625, 0.421875, 0.4375, 0.453125, 0.46875, 0.484375, 0.515625, 0.53125, 0.546875, 0.5625, 0.578125, 0.59375, 0.609375, 0.625, 0.640625, 0.65625, 0.671875, 0.6875, 0.703125, 0.71875, 0.734375, 0.765625, 0.78125, 0.796875, 0.8125, 0.828125, 0.84375, 0.859375, 0.890625, 0.90625, 0.921875, 0.953125, 1.015625, 1.03125, 1.046875, 1.0625, 1.078125, 1.09375, 1.109375, 1.140625, 1.15625, 1.171875, 1.203125, 1.265625, 1.28125, 1.328125, 1.515625]
      98 72

      [0.5, 0.75, 0.875, 0.9375, 0.96875, 0.984375, 0.9921875, 1.0, 1.125, 1.1875, 1.21875, 1.234375, 1.2421875, 1.25, 1.3125, 1.34375, 1.359375, 1.3671875, 1.375, 1.40625, 1.421875, 1.4296875, 1.4375, 1.453125, 1.4609375, 1.46875, 1.4765625, 1.484375, 1.4921875, 1.5, 1.53125, 1.546875, 1.5546875, 1.5625, 1.578125, 1.5859375, 1.59375, 1.6015625, 1.609375, 1.6171875, 1.625, 1.640625, 1.6484375, 1.65625, 1.6640625, 1.671875, 1.6796875, 1.6875, 1.6953125, 1.703125, 1.7109375, 1.71875, 1.734375, 1.7421875, 1.75, 1.7578125, 1.765625, 1.7734375, 1.78125, 1.7890625, 1.796875, 1.8046875, 1.8125, 1.828125, 1.84375, 1.8515625, 1.859375, 1.8671875, 1.875, 1.8828125, 1.890625, 1.8984375, 1.90625, 1.921875, 1.9296875, 1.9375, 1.9453125, 1.953125, 1.96875, 1.9765625, 1.984375, 1.9921875, 2.0, 2.0078125, 2.015625, 2.0234375, 2.03125, 2.0390625, 2.046875, 2.0546875, 2.0625, 2.0703125, 2.078125, 2.0859375, 2.09375, 2.109375, 2.1171875, 2.125, 2.1328125, 2.140625, 2.1484375, 2.15625, 2.1640625, 2.171875, 2.1796875, 2.1875, 2.1953125, 2.203125, 2.21875, 2.2265625, 2.234375, 2.25, 2.265625, 2.2734375, 2.28125, 2.296875, 2.3046875, 2.3125, 2.3203125, 2.328125, 2.34375, 2.359375, 2.3671875, 2.375, 2.40625, 2.421875, 2.4375, 2.4453125, 2.453125, 2.46875, 2.484375, 2.5, 2.515625, 2.53125, 2.546875, 2.5625, 2.578125, 2.59375, 2.609375, 2.625, 2.640625, 2.65625, 2.671875, 2.6875, 2.703125, 2.71875, 2.734375, 2.75, 2.765625, 2.78125, 2.8125, 2.828125, 2.84375, 2.859375, 2.875, 2.90625, 2.921875, 2.9375, 2.953125, 2.96875, 3.0, 3.015625, 3.03125, 3.0625, 3.09375, 3.109375, 3.125, 3.1875, 3.21875, 3.25, 3.28125, 3.3125, 3.34375, 3.375, 3.40625, 3.4375, 3.46875, 3.5, 3.53125, 3.5625, 3.59375, 3.625, 3.6875, 3.71875, 3.75, 3.78125, 3.8125, 3.875, 3.9375, 4.0, 4.125, 4.1875, 4.25, 4.3125, 4.375, 4.4375, 4.5, 4.625, 4.75, 4.875, 5.0, 5.125, 5.25, 5.5, 5.75, 6.0, 6.5, 7.0]
      [0.0078125, 0.015625, 0.0234375, 0.03125, 0.0390625, 0.046875, 0.0546875, 0.0625, 0.0703125, 0.078125, 0.0859375, 0.09375, 0.1015625, 0.109375, 0.1171875, 0.125, 0.1328125, 0.140625, 0.1484375, 0.15625, 0.1640625, 0.171875, 0.1796875, 0.1875, 0.1953125, 0.203125, 0.2109375, 0.21875, 0.2265625, 0.234375, 0.2421875, 0.25, 0.2578125, 0.265625, 0.2734375, 0.28125, 0.2890625, 0.296875, 0.3046875, 0.3125, 0.3203125, 0.328125, 0.3359375, 0.34375, 0.3515625, 0.359375, 0.3671875, 0.375, 0.3828125, 0.390625, 0.3984375, 0.40625, 0.4140625, 0.421875, 0.4296875, 0.4375, 0.4453125, 0.453125, 0.4609375, 0.46875, 0.4765625, 0.484375, 0.4921875, 0.5078125, 0.515625, 0.5234375, 0.53125, 0.5390625, 0.546875, 0.5546875, 0.5625, 0.5703125, 0.578125, 0.5859375, 0.59375, 0.6015625, 0.609375, 0.6171875, 0.625, 0.6328125, 0.640625, 0.6484375, 0.65625, 0.6640625, 0.671875, 0.6796875, 0.6875, 0.6953125, 0.703125, 0.7109375, 0.71875, 0.7265625, 0.734375, 0.7421875, 0.7578125, 0.765625, 0.7734375, 0.78125, 0.7890625, 0.796875, 0.8046875, 0.8125, 0.8203125, 0.828125, 0.8359375, 0.84375, 0.8515625, 0.859375, 0.8671875, 0.8828125, 0.890625, 0.8984375, 0.90625, 0.9140625, 0.921875, 0.9296875, 0.9453125, 0.953125, 0.9609375, 0.9765625, 1.0078125, 1.015625, 1.0234375, 1.03125, 1.0390625, 1.046875, 1.0546875, 1.0625, 1.0703125, 1.078125, 1.0859375, 1.09375, 1.1015625, 1.109375, 1.1171875, 1.1328125, 1.140625, 1.1484375, 1.15625, 1.1640625, 1.171875, 1.1796875, 1.1953125, 1.203125, 1.2109375, 1.2265625, 1.2578125, 1.265625, 1.2734375, 1.28125, 1.2890625, 1.296875, 1.3046875, 1.3203125, 1.328125, 1.3359375, 1.3515625, 1.3828125, 1.390625, 1.3984375, 1.4140625, 1.4453125, 1.5078125, 1.515625, 1.5234375, 1.5390625, 1.5703125, 1.6328125, 1.7265625, 1.8203125]
      208 170

  3. Mark – I got 48 times with five ropes starting at time 0. It seems you are missing time 2.06250. Below is how to measure that time (where $r_i$ is burning rope $i$):

    1) Light both ends of $r_1$ and one end of $r_2$
    2) 0.5 hours passes ($r_1$ burned through). Light other end of $r_2$ and one end of $r_3$
    3) 0.25 hours passes ($r_2$ burned through). Light one end of $r_4$
    4) 0.75 hours passes ($r_3$ burned through). Light other end of $r_4$ and one end of $r_5$
    5) 0.125 hours passes ($r_4$ burned through). Light other end of $r_5$
    6) 0.4375 hours passes ($r_5$ burned through).

    Total time is 2.0625 hours (=0.5+0.25+0.75+0.125+0.4375). With 6 ropes I got 101 time points from zero. Not sure about intermediate stop/start pairs.

    1. Thanks, Peter. I’ll have to fix the bug in my program. Having your recipe for the missing value will make it easier.

  4. I fixed my program and sped it up. Here are my new results for up to 12 ropes. 12 ropes took 80 hours to compute. The columns are number of ropes, number of 0-based times, number of intermediate-based times, number of seconds to find solution.

    1: 2, 0
    2: 5, 1
    3: 11, 4
    4: 23, 11
    5: 48, 30
    6: 101, 73
    7: 218, 168 2.36 seconds
    8: 473, 371 17.26 seconds
    9: 1044, 793 158 seconds
    10: 2284, 1676 1695 seconds
    11: 5011, 3502 25162 seconds
    12: 10979, 7259 287960 seconds

    1. Mark – Incredible you calculated the answer up to 12 ropes! I stopped at 7 when my program started to take too long. Thanks for sharing your results!

      1. 13: 23954 (I’m no longer keeping track of intermediate-based times) 45013 seconds and 249GB of the 251GB available on the machine I was using. I’m now using memoization which speeds things up quite a bit if there is enough memory.

Leave a Reply to Hector Cancel reply

Your email address will not be published. Required fields are marked *