0

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/...)

Cjen1
  • 259
  • 1
    Usually in these problems you have more than one rope. – lulu Jan 20 '20 at 16:09
  • 1
    @lulu The first answer here gives an approach with one rope. – almagest Jan 20 '20 at 16:22
  • @almagest Thanks! I guess the point is that the rules are not clear, and are certainly not universal. sometimes it is specified that you can only light a rope at its ends, for instance. – lulu Jan 20 '20 at 16:41
  • @almagest almost, I was hoping it was possible to do without relighting... I'll update the question to be more clear. – Cjen1 Jan 20 '20 at 16:49
  • @Cjen1 Given that the rope does not burn uniformly, I don't see how you could hope to do it without relighting. To get 1/4 of the time you need four flames moving along the rope at all times. That inevitably involves a chance of relighting being required. – almagest Jan 20 '20 at 16:54
  • @almagest that was unfortunately what I was thinking the answer was... – Cjen1 Jan 20 '20 at 16:56

1 Answers1

1

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.

antkam
  • 15,363