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]
My solution uses a recursive approach: adding one rope at a time and seeing how the set of measurable time intervals increases. Let’s start by answering simple question that will give us the key insight needed to solve the problem:
Suppose we the ability to measure a time interval $\tau$ and nothing else. We can imagine this as two beeps that occur exactly $\tau$ apart. Using a single rope, what new intervals of time can we now measure? There are several things we can do:
- Measure the time elapsed between both beeps (don’t use the rope at all). This allows us to measure $\tau$.
- Starting at the first beep, light one side (or both sides) of the rope and measure the time elapsed between when the rope is fully burnt and the second beep. This measures $|\tau-1|$ or $|\tau-\tfrac{1}{2}|$ depending on how many sides were lit.
- Starting at the second beep, light one side (or both sides) of the rope and measure the time elapsed between the first beep and when the rope is fully burnt. This measures $\tau+1$ or $\tau+\tfrac{1}{2}$ depending on how many sides were lit.
- If $\tau < 1$, we can also do the following thing: light one side at the first beep and light the second side at the second beep. The rope will be fully burnt at $\tfrac{1+\tau}{2}$, which means we can measure either $\tfrac{1+\tau}{2}$ or $\tfrac{1-\tau}{2}$ depending on whether we start counting at the first beep or the second beep.
Let’s call $f:\mathbb{R}\to2^{\mathbb{R}}$ the map from $\tau$ to the set of times you can measure when you add one rope. Based on the above, we have, for example: $f(0.6) = \{0.1, 0.2, 0.4, 0.6, 0.8, 1.1, 1.6\}$. Now let’s generalize to multiple measurements. If the set of times we can measure is $\{\tau_1,\dots,\tau_m\}$, then adding one rope will allow us to measure:
\[
f(\tau_1) \cup f(\tau_2) \cup \dots \cup f(\tau_m)
\]Note that in order for this to be true, the list $\{\tau_1,\dots,\tau_m\}$ must include all the times that can be measured without needing the rope. For example, if we can independently measure $0.5$ and $0.7$, then we can also measure $0.2$ and $1.2$, so these should also be included in the original list!
If we call $S_k$ the set of times we can measure using $k$ ropes, we can compute $S_{k+1}$ by applying $f$ to every element of $S_k$ and taking the union of the resulting sets. The result for the first few values of $k$ is:
\begin{align}
S_1 &= \left\{\frac{1}{2},1\right\} \\
S_2 &= \left\{\frac{1}{4},\frac{1}{2},\frac{3}{4},1,\frac{3}{2},2\right\} \\
S_3 &= \left\{\frac{1}{8},\frac{1}{4},\frac{3}{8},\frac{1}{2},\frac{5}{8},\frac{3}{4},\frac{7}{8},1,\frac{5}{4},\frac{3}{2},\frac{7}{4},2,\frac{5}{2},3\right\} \\
S_4 &= \left\{\frac{1}{16},\frac{1}{8},\frac{3}{16},\frac{1}{4},\frac{5}{16},\frac{3}{8},\frac{7}{16},\frac{1}{2},\frac{9}{16},\frac{5}{8},\frac{11}{16},\frac{3}{4},\frac{13}{16},\frac{7}{8},\frac{15}{16},1,\dots\right.\\
&\qquad\qquad\left.\frac{9}{8},\frac{5}{4},\frac{11}{8},\frac{3}{2},\frac{13}{8},\frac{7}{4},\frac{15}{8},2,\frac{9}{4},\frac{5}{2},\frac{11}{4},3,\frac{7}{2},4\right\}
\end{align}The pattern that emerges is quite interesting. The set $S_N$ consists of:
- $\tfrac{1}{2^N},\tfrac{2}{2^N},\tfrac{3}{2^N},\dots,1$. (a total of $2^N$ numbers)
- $1+\tfrac{1}{2^{N-1}},1+\tfrac{2}{2^{N-1}},1+\tfrac{3}{2^{N-1}},\dots,2$. (a total of $2^{N-1}$ numbers)
- $2+\tfrac{1}{2^{N-2}},2+\tfrac{2}{2^{N-2}},2+\tfrac{3}{2^{N-2}},\dots,3$. (a total of $2^{N-2}$ numbers)
- $\dots$
- $(N-2)+\tfrac{1}{2^2},(N-2)+\tfrac{2}{2^2},\dots,(N-1)$. (a total of $2^2$ numbers)
- $(N-1)+\tfrac{1}{2},N$. (a total of $2$ numbers)
In total, we can measure $2^N+2^{N-1}+\dots+2^2+2$ different times, which sums to $2^{N+1}-2$. This is therefore the total number of times that we can measure using $N$ ropes. In the case $N=4$, we can measure $30$ different times.
$\displaystyle
\text{With }N\text{ ropes, we can measure }\,2^{N+1}-2\,\text{ different times.}
$
The intuition behind the structure of the sets $S_k$ is that the numbers less than $1$ get divided in half when we add a rope, and the numbers greater than $1$ get shifted up or down by $1$ or $\tfrac{1}{2}$. This affords us more resolution for times closer to zero. The largest time we can measure with $N$ ropes is simply $N$ hours, obtained by burning the ropes sequentially. The shortest time we can measure is $\tfrac{1}{2^N}$ hours, obtained by simultaneously burning one rope on both ends and the remaining ropes on one end. Each time a rope burns out, light the other end of one of the remaining ropes. When there is only one rope left, it will burn for $\tfrac{1}{2^N}$ hours.
Note: my solution is incomplete (see comments below!)
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…
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.
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.
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.
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
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
Nice. Interesting that we both maxed out around N=7. I did get 8 after some tweaking, but I was surprised at how quickly the execution times blow up.
Yes – that’s why I stopped at 7. Did we get the same totals for 5-7?
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.
Thanks, Peter. I’ll have to fix the bug in my program. Having your recipe for the missing value will make it easier.
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
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!
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.