2
$\begingroup$

well known riddle: given two ropes that each take an hour to burn (they do not burn uniformly or identically, necessarily) measure 45 minutes. solution: light 3 out of the 4 ends, and then light the 4th end when the first rope is totally burned up.

generalization (and the topic of discussion):

1) given an infinite number of such ropes, which times are measurable? Assume you can light each rope only a finite number of times.

2) additionally, what is the optimal strategy to measure a given amount of time, i.e. the fastest way to measure?

attempt at solution:

intro: take the base 2 representation of any amount of time you wish to measure, where 1 represents 1 hour. to measure the time to the left of the decimal point burn the appropriate number of ropes sequentially. to the right of the decimal it gets trickier. for numbers less than 1 I believe it is possible to measure any finite linear combination of elements of the form "sum(1/2^i)" where i ranges from a natural number to infinity. I will sketch an algorithm/proof below.

gaps: first define the number of gaps g(x) as the number of sequences of consecutive 0's bounded by 1's in the base 2 representation. for example g(.010101) = 2 and g(.0100010101) =3. Now actually modify this definition slightly - we do not count gaps bounded on the left by a 1 in the 1/2 slot, e.g. g(.101) = 0 and g(.10010101) = 2. the intuition here is that measuring 1/2 is as simple as measuring 1 - we can instantly measure 1/2 by burning 2 ends of one rope, whereas smaller numbers require some lead up time, e.g. you must measure 1/2 before you can measure 1/4.

measurement sequence: note that to measure 1/2^k for k > 1 you must first measure 1/2, 1/4,.., 1/2^(k-1) convince yourself of this or tell me why I am wrong. from now on I will refer to the sequence of measurements 1/2, 1/4,.., 1/2^k as the "measurement sequence" for 1/2^k.

sketch of an algorithm that takes approximately n hours to measure x, where x<1 and g(x)=n:

1) rewrite x as a sum of numbers with 0 gaps, e.g. .010101 = .01 + .0001 + .000001

2) to measure 1/2^k takes 1-(1/2^k) amount of time, so it seems you should start the "measurement sequence" (1/2, 1/4, ..., 1/2^k) for the smallest number first. Likewise you should start the measurement sequence for the 2nd smallest number a tad later, and so on.

3) You now have g(x) "measurement sequences" that you need to time correctly. continuing with the example: you want to measure .01 immediately followed by .0001 immediately followed by .000001 (note, it seems you should measure the smallest number last since it will have the most expensive "measurement sequence"). notice, the measurement sequence for .0001 should start .00001 after the measurement sequence for .000001. We can time this delay using a measurement sequence for .00001 - let's call this a coordination sequence since it allows us to coordinate a delay between two measurement sequences.

4) we started out with 3 measurement sequences, and obtain two coordination sequences - one coordination sequence to make sure the 2nd measurement sequence starts .00001 after the 1st, and one coordination sequence to make sure the 3rd measurement sequence starts .001 after the 2nd. Now we need to coordinate the two coordination sequences with a "coordination^2" sequence - convince yourself or tell me I'm wrong.

5) convince yourself that for g(x) = n we get n measurement sequences, which we need to coordinate with n-1 coordination sequences, which we need to coordinate with n-2 coordination^2 sequences... which we need to coordinate with 1 coordination^(n-1) sequence, and that the whole process of coordinating and finally measuring takes a little less than n hours.

Under this algorithm, it seems we can measure any time, except times x such that g(x)=infinity. Is there a faster algorithm for measuring different times? Have I properly classified the set of measurable times? Thanks. I know my explanation is not super clear; ready to clarify any points.

$\endgroup$
0
$\begingroup$

"We can time this delay using a measurement sequence for .00001" -- this is not obvious for me... However, I agree that the set of measurable times consists of times which have finite binary expansion. Indeed:

on one hand, we can only light an end at a time measured by other ropes, and since the rope is burned up at the time $(t_1+t_2+1)/2$ (where $t_1$ and $t_2$ are the times when the ends were lighted), any one rope allows us to go only one binary digit deeper, so no numbers with infinite binary expansion can be measured by arbitrary large but finite number of ropes (infinite number of ropes with finite time won't help, too);

on the other hand, with $k$ ropes we can easily measure the time $1-2^{-k}$ from the moment when we begin burning the first of these $k$ ropes, so if we measure $g(x)$ such intervals one after another (in any order) while simultaneously burning $g(x)$ whole ropes one after another, the latter process will be exactly $x$ longer than the former, so any number $x$ with finite binary expansion can be measured.

$\endgroup$

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.