Variant of the rope burning logic puzzle

puzzle

Given a rope which will burn at a varying rate and can be lit multiple times anywhere along its length. Re-lighting is not possible.

The question is: is it possible to measure a quarter of an hour given only a single rope?

(the reason for this formulation is that I'm trying to map this into parallel searching of random trees [hence the lack of relighting], and I was wondering if this had already been solved for n>2, i.e. trying to measure a quarter/eighth/sixteenth/…)

Best Answer

Assuming the "no re-lighting" restriction means this:

At time $0$, you are allowed to set fire to any finite number of positions, each position $\in [0,1]$ along the rope, simultaneously. However you are not allowed to set more fires at any time $t > 0$.

Then measuring $15$ minutes is impossible. Consider any set of positions $x_1 < x_2 < \dots < x_n$. Then:

  • If $x_1 = 0$, construct a rope that burns instantly beyond $x_2$, and we are now reduced to the remaining rope burning at both ends, measuring $30$ minutes.

  • if $x_1 > 0$, construct a rope that burns instantly beyond $x_1$, and we are now reduced to the remaining rope burning at one end, measuring $60$ minutes.

In other words, for any set of positions determined at time $0$, there exists a rope for which the set of positions measures either $30$ or $60$ minutes, but not $15$ minutes. Since you don't know what rope you're getting to begin with, this proves no algorithm will work for all ropes.

Related Question