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?

(fivethirtyeight)

Solution:

“Being able to measure” a given length of time might mean being able to tell when that length of time has passed from the get-go, or more liberally, being able to produce a sequence of events such that that length is the period between some two of them. (Oliver Roeder clarified on Twitter that the latter interpretation was intended; but the solution provided by the contributor of the puzzle assumed the former.) We’ll find answers for both interpretations of the problem. Also, in the problem statement it is clearly assumed that there is not a “length” of zero hours.

With 1 rope, we can measure 2 durations: 1/2 and 1 hour.

With 2 ropes (call them 1 and 2), we can measure 5 durations from the start:

  • 4 half-hour-multiple durations.

  • Measure 3/4hr: light both ends of 1 and one end of 2; at 1/2hr, light the other end of 2.

This allows us also to measure 1/4hr, so there are 6 in all.

With 3 ropes (1, 2, and 3) we get 11 durations from the start:

  • 6 half-hour-multiple durations.

  • Using two of the ropes to measure 3/4hr, we get 3 more durations for each of the ways of using rope 3 from there.

  • Measure 7/8hr: proceed as in measuring 3/4hr, and light 3 at the start and 3/4hr.

  • Measure 9/8hr: proceed as in measuring 3/4hr, and light 3 at 1/2hr and 3/4hr.

If we count durations between extinguishings as well, we get 15 in all.

With 4 ropes we have 23 durations from the start:

  • 8 half-hour-multiples.

  • Using one pair to measure 3/4hr, we have 5 options for the other two ropes starting from there (the half-hour multiples).

  • Using three ropes to measure 7/8 gives 3 options for the remaining rope starting from there.

  • Using three ropes to measure 9/8hr similarly gives 3 new options starting from there.

  • Measure 15/16hr: proceed as in measuring 7/8hr, and light 4 at the start and 7/8hr.

  • Measure 19/16hr: proceed as in measuring 7/8hr, and light 4 at 1/2hr and 7/8hr.

  • Measure 21/16hr: proceed as in measuring 7/8hr, and light 4 at 3/4hr and 7/8hr. (Alternatively, proceed as in measuring 9/8hr, and light 4 at 1/2hr and 9/8hr.)

  • Measure 23/16hr: proceed as in measuring 9/8hr, and light 4 at 3/4hr and 9/8hr.

If we count durations between extinguishings as well, there are 34 in all.

These figures are confirmed by the Python program below. A natural question is whether there is a closed-form expression for N ropes. I haven’t found one, and I would be interested to know if you have!

Number of Ropes Intervals from Start All Intervals
1 2 2
2 5 6
3 11 15
4 23 34
5 48 78
6 101 174
7 218 386
8 473 844


Code (Python):


# Rope Burning Riddler from fivethirtyeight.com

def explore(situation):

	ropes = situation[0]
	time = situation[1]

	# Find unextinguished ropes and make a list of those 
	# with at least 1 unlit end.
	allextinguished = True
	ropestochoose = []
	for r in range(N):
		if ropes[r][1] == 0 or ropes[r][1] > time:
			allextinguished = False
			if not ropes[r][0] ==2:
				ropestochoose.append(r)
	if allextinguished:
		# No descendent situations, so tally the intervals
		for rope in ropes:
			time = rope[1]
			if not time in times:
				times.append(time)
		# Comment-out the following block to ignore 
		# periods between extinguishings
		for rope1 in ropes:
			for rope2 in ropes:
				time = abs(rope1[1]-rope2[1])
				if not time in times:
					times.append(time)
		return
	# A choice is to (0) do nothing, (1) ignite a first 
	# end if unignited (2) ignite (both first and) 
	# second end if unignited. The choice for a particular 
	# rope R (0 to len(ropestochoose)-1) is (choices//3**R)%3 
	# (think of choices as a base-3 numeral).
	for choices in range(1,3**len(ropestochoose)):
		# We will modify a copy of ropes
		newropes = list(ropes)
		for r in range(len(ropestochoose)):
			rope = newropes[ropestochoose[r]]
			choice = (choices//3**r)%3
			if rope[0] == 0:
				# No ends lit
				if choice == 1:
					rope = [1,time+1]
				elif choice == 2:
					rope = [2,time+.5]
			elif rope[0] == 1:
				# One end already lit
				if choice == 2:
					rope = [2,time+.5*(rope[1]-time)]
			newropes[ropestochoose[r]] = rope
		# This will prevent redundantly exploring equivalent situations
		newropes.sort(reverse=True)	
		# Find time of next extinguishing
		nexttime = min([rope[1] for rope in newropes if rope[1] > time])
		newsituation = [newropes,nexttime]
		if newropes == ropes or newsituation in already_explored:
			continue
		already_explored.append(newsituation)
		explore(newsituation)

# Main program

# Numbers of ropes to do
MinRopes = 1
MaxRopes = 6

for N in range(MinRopes,MaxRopes+1):
	# ropes is a list of pairs. each pair is: [ends-lit 
	# (0, 1, or 2), time (has been or will be) extinguished].
	# We start with extinction time 0 as a dummy value.
	ropes = [[0,0]]*N
	time = 0
	situation = [ropes,time]

	# Keep track of the situations we have already processed
	already_explored = [situation]

	# This is our list of the durations we can measure
	times = []

	# Recursively explore the achievable situations
	explore(situation)

	# Done. Tidy up and finish.
	if 0 in times:
		# 0 is not a duration per problem statement.
		times.remove(0)
	times.sort()
	print(N,"ropes measure",len(times), "intervals")
	# print(times)