The problems below were posed by my Design and Analysis of Algorithms professor. Although we did not spend much time on the solution or its implications, I figured over-analyzing it might be in order if I wanted to read back on this in the future and think of the productivity wasted on this post.

The initial problem

Given a special candle of unknown length that burns up in one hour regardless of the orientation it is placed in (i.e. whether the candle is lit upside down or right side up or some other degree of rotation), how can you use this candle as a timer to know when 30 minutes have passed? The density of the candle's wax varies along the whole length, so two equal lengths will burn up in different times (you aren't allowed to measure the length of the candle anyway). Assume the wick is present on both ends of the candle (meaning you can light two fires at once), and that you are able to light a fire or split the candle with no loss of relative time. Remember: you need the timer to start immediately, so the goal is to use the candle as a timer, not to be left with a candle timer. This is a variation of the burning rope problem but uses the more environmentally conscious alternative to setting ropes on fire: burning candles.

The initial solution

Light both ends of the candle. It is trivial to see how we can measure 30 minutes using a single candle and two fires. Regardless of how long the candle is, we simply need the information that the whole candle will burn in one hour; this means that the amount of wax present is only able to fuel one hour of burn time with one fire going. Thus, burning two fires using both ends of the candle means using the same amount of fuel but twice as fast. Therefore, once the two fires meet and the candle runs out of wax, 30 minutes have passed.

Blackouts are inconvenient

Say you found a stash of more one-hour candles. What if you had the same problem as above, but now wanted to measure 45 minutes? We already know how to achieve 30 minutes using one candle, so going for 45 minutes with two candles should not be a tall order. The solution is as follows: light the two ends of the first candle as above, but also light one end of a second candle. Once the first candle burns out in 30 minutes, we are left with 30 minutes remaining on the second burning candle. Light the unlit end in order to get this candle to use fuel twice as fast, so that it burns out in 15 minutes. This gives us 45 minutes of total light we wanted.

What happens if we wanted to get 15 minutes using only one candle? Turns out, this is the hardest of the problems encountered so far. Since we only have one candle, it'd be impossible to get any amount of time less than 30 minutes without having to split the candle into two or more parts. Thus, the solution lies in breaking this one candle into two pieces of candle. The non-intuitive part of it all is that the length of the two pieces do not matter in this solution. In fact, length does not play a role in finding the solution to any amount of time, which is why the seemingly unknown length is irrelevant to the whole thing. We now have two (unequal) child parts of the same candle. The first step of the solution is to light both ends of both candles, so that there are 4 fires burning at the same time. You can sort of see a pattern now: one fire equals an hour of light, two fires give half that time, etc. The caveat to burning four fires is knowing what to do after the first of the two pairs of fires burn out earlier than the other (which it will, as the two unequal pieces imply that one has to be shorter). The solution is simple: the moment the first child candle burns out, take the other candle and split it into two child pieces again, and make sure both ends are lit for each. Since we are assuming there is no wasted time in splitting candles and lighting fires, the candles will all eventually burn out completely in 15 minutes. Simply explained, the whole candle will burn out in 15 minutes because you will always have four fires burning simultaneously. This is similar to the 30 minutes solution: at any time, your candle will be burning two fires, so it runs out of fuel twice as fast. In this solution, your candle is running out of fuel 4 times as fast, and therefore your fuel lasts a fourth of an hour. In general, if you had multiple children candles, you split a remaining candle every time one of them burns out in order to maintain the same number of fires alive to consume the total fuel.

The table below shows the general pattern of parts and fires needed to achieve a given burning time in minutes for one candle. Parts, in this case, means the number of parts you are splitting the initial candle into, and does not account for the times you recursively break up the child candles.

Parts Fires Time
1 1 60
1 2 30
2 3 20
2 4 15
3 5 12
3 6 10

What time is it?

The general equation for the number of fires $f$ needed to achieve a time $t$ in minutes is then simply $f=\frac{60}t$. The number of parts $p$ needed given $f$ is then $p=\lceil\frac{f}2 \rceil$. Keep in mind that this equation is valid only if we have one candle, and therefore $f\in\mathbb{Z^+}$. If such is the case, then the only exact times we are able to achieve with one candle are the quotients of dividing 60 by any positive integer. We can say that given a candle that normally burns (with a single flame) in $m$ minutes, the set of all solutions are in $\{\frac mz \mid z\in\mathbb{Z^+}\}$. So, knowing how the solution plays out, and how long one candle burns for, let's write a simple Python script to calculate how many parts the initial candle needs to be split into, and how many fires need to be simultaneously lit in order to achieve a desired time. We have two arguments to pass in: burn_rate (the time it takes to burn the whole candle with a single fire) and target_time (a time you'd like to waste playing with candles). The program should output a tuple: the former number will be the parts to split into and the latter will be the number of fires to light between all those parts. These two pieces of information will get you as close to your target_time as possible without exceeding it. The code below demonstrates one way of achieving this.

import math

def candle_waster(burn_rate, target_time):
  fires = math.ceil(burn_rate/target_time)
  parts = math.ceil(fires/2)
  if target_time > burn_rate:
    return "Can't burn candle longer than burn_rate"
  return parts, fires
(2, 4)
(3, 6)
(5, 10)
(1, 2)
Can't burn candle longer than burn_rate

That was the easier part. Let's figure out what times we're able to achieve with more than one candle.

Lots and lots of wax

Suppose now we have two candles that all have the same burn rate of $m$ minutes each. It is simple to see that we are able to achieve a maximum time of $2m$ minutes by using them in succession—that is, burning them one by one until we're done. In fact, these "additive" times are reached simply by adding any times $t_1$ and $t_2$ together such that $t_1, t_2 \in S$, where $S = \{\frac mz \mid z\in\mathbb{Z^+}\}$ (the set of times possible with each candle of burn rate $m$). One can see that $\lvert S \rvert = \infty$ because we haven't defined proper constraints for $z$. For our sake, we can define a maximum number of fires $e$ allowed for each candle (meaning no one candle can have more than $e$ fires ablaze at one time, which limits the magnitude of $S$ to a finite number). Furthermore, let's define $S_{m,e}$ to mean the set of times achievable with a single candle of burn rate $m$ and max fires of $e$:
S_{m,e} = \{\frac mz \mid z\in\mathbb{Z^+}, 1 \leq z \leq e \}
As an example, set $m=60, e=3$. Thus, the two candles are able to produce the times in $S_{60,3}$ individually. This means that, by itself, any one of the two candles can produce any of these times in the set $S_{60,3} = \{60,30,20\}$. Utilizing both of them, however, produces a wider range of possible times.

The set of possible times of using both candles is expanded because you have more choices as to how you go about lighting, splitting, and delaying each candle. One set of possibilities is the option of successively lighting each candle after the last one burns out. Let's call this set of times $T_{sc}$. In our example above, each candle is able to burn for either 60, 30, or 20 minutes each. We see that if we burn the first candle for 60 minutes, then burn the second for 60 minutes, we've produced a new possible time of 120 minutes. Each of the times in $S_{60,3}$ is added to all possible times also in the same set $S_{60,3}$. As such, we are left with $T_{sc}$ containing the set of numbers which result from the Minkowski addition (or direct sum) of $S_{60,3}$ and itself. It's intuitive to see how the times form from successive burning, and we demonstrate it below with all possible cases of said process. Let the first and second candles, along with their remaining burn times, be $c_{1},c_{2},b_{1},b_{2}$, respectively.

Successive burning:

  • (Case 1) $c_{1}$ burns for $b_{1}=60$ minutes, then

    • (1A) $c_{2}$ burns for $b_{2}=60$ minutes $\rightarrow b_{1}+ b_{2} =$ 120 minutes.
    • (1B) $c_{2}$ burns for $b_{2}=30$ minutes $\rightarrow b_{1}+ b_{2} =$ 90 minutes.
    • (1C) $c_{2}$ burns for $b_{2}=20$ minutes $\rightarrow b_{1}+ b_{2} =$ 80 minutes.
  • (Case 2) $c_{1}$ burns for $b_{1}=30$ minutes, then

    • (2A) $c_{2}$ burns for $b_{2}=60$ minutes $\rightarrow b_{1}+ b_{2} =$ 90 minutes.
    • (2B) $c_{2}$ burns for $b_{2}=30$ minutes $\rightarrow b_{1}+ b_{2} =$ 60 minutes.
    • (2C) $c_{2}$ burns for $b_{2}=20$ minutes $\rightarrow b_{1}+ b_{2} =$ 50 minutes.
  • (Case 3) $c_{1}$ burns for $b_{1}=20$ minutes, then

    • (3A) $c_{2}$ burns for $b_{2}=60$ minutes $\rightarrow b_{1}+ b_{2} =$ 80 minutes.
    • (3B) $c_{2}$ burns for $b_{2}=30$ minutes $\rightarrow b_{1}+ b_{2} =$ 50 minutes.
    • (3C) $c_{2}$ burns for $b_{2}=20$ minutes $\rightarrow b_{1}+ b_{2} =$ 40 minutes.

Thus, $T_{sc} = \{120,90,80,60,50,40\}$ given two candles, with $m=60, e=3$. The other option of discovering time possibilities is the idea of simultaneously burning the candles. This method is a bit trickier. Recall that towards the start of this post was a solution for 45 minutes that involved two candles: the first candle was lit on one end and the second was lit on both ends. Both burned for 30 minutes (until the second one burned out) and the first one was left with 30 remaining minutes of wax (30 minutes have also passed at this point). We ensured the remaining one had two fires ablaze and thus burned twice as fast with 30 minutes of fuel left, which means it burned for 15 minutes. The 30 minutes from the simultaneous burning and the 15 from the remainder burning produced 45 total minutes. This was possible because we were able to reduce the first candle's burn rate down by any attainable time of the second candle, and from there we solved the sub-problem of getting 15 minutes using an $m=30$ candle. Let $T_{sim}$ be the set of times that result from simultaneously burning both candles and adding on the time possibility set of the remaining candle. Each case of these simultaneously burnings are outline below.

Simultaneous (then remainder) burning:

  • (Case 1) Light $c_{1}$ with 1 fire ($b_{1}=60$) along with

    • (1A) $c_{2}$ with 1 fire ($b_{2}=60$) $\rightarrow$ $c_{2}$ burns out; $b_{1}=0$ remains.
      • $b_{2} + S_{b_{1},e=3} = 60+\{0\} = \{60\}$
    • (1B) $c_{2}$ with 2 fires ($b_{2}=30$) $\rightarrow$ $c_{2}$ burns out; $b_{1}=30$ remains.
      • $b_{2} + S_{b_{1},e=3} = 30+\{30,15,10\} = \{60,45,40\}$
    • (1C) $c_{2}$ with 3 fires ($b_{2}=20$) $\rightarrow$ $c_{2}$ burns out; $b_{1}=40$ remains.
      • $b_{2} + S_{b_{1},e=3} = 20+\{40,20,\frac{40}3\} = \{60,40,33\frac13\}$
  • (Case 2) Light $c_{1}$ with 2 fires ($b_{1}=30$) along with

    • (2A) $c_{2}$ with 1 fire ($b_{2}=60$) $\rightarrow$ same as case 1B.
    • (2B) $c_{2}$ with 2 fires ($b_{2}=30$) $\rightarrow$ $c_{2}$ burns out; $b_{1}=0$ remains.
      • $b_{2} + S_{b_{1},e=3} = 30+\{0\} = \{30\}$
    • (2C) $c_{2}$ with 3 fires ($b_{2}=20$) $\rightarrow$ $c_{2}$ burns out; $b_{1}=10$ remains.
      • $b_{2} + S_{b_{1},e=3} = 20+\{10,5,\frac{10}3\} = \{30,25,23\frac13\}$
  • (Case 3) Light $c_{1}$ with 3 fires ($b_{1}=20$) along with

    • (3A) $c_{2}$ with 1 fire ($b_{2}=60$) $\rightarrow$ same as case 1C.
    • (3B) $c_{2}$ with 2 fires ($b_{2}=30$) $\rightarrow$ same as case 2C.
    • (3C) $c_{2}$ with 3 fires ($b_{2}=20$) $\rightarrow$ $c_{2}$ burns out; $b_{1}=0$ remains.
      • $b_{2} + S_{b_{1},e=3} = 20+\{0\} = \{20\}$

Thus, $T_{sim} = \{60,45,40,33\frac13,30,25,23\frac13,20\}$ given two candles, with $m=60, e=3$. We have then that given these two candles, we're about to produce the final set of times $T$:
T = S_{60,3} \cup T_{sc} \cup T_{sim}=\{120,90,80,60,50,45,40,33\frac13,30,25,23\frac13,20\}
Now, what would happen with three candles? The short story is, the successive times of three candles with the same burn rate and max fires is simply the direct sum of our previous times of 2 candles $T$ with another $S_{60,3}$. Similarly, the possible simultaneous times of this group would utilize the same procedure we used for $S_{60,3}$, except now we find all possible cases using the expanded set of times $T$ instead. Let's define a few functions back in Python to help us figure out all the times given a number of candles, a burn_rate, and max_fires. The function times_succession() accepts two sets and returns the direct sum of those two sets. The function times_simul() accepts two sets and max fires, and returns the set of times as described in our simultaneous and remainder burning above. times_of_one_candle() simply returns the set of times possible with one candle given its burn rate and max fires.

def times_succession(set_one, set_two):
    t_sc = set([])

    for x in set_one:
        for y in set_two:
            t_sc |= {round(x + y, 4)}

    return t_sc

def times_simul(set_one, set_two, max_fires):
    t_sim = set([])

    for x in set_one:
        for y in set_two:
            if x >= y:
                remaining_time = x - y
                t = times_succession({round(y, 4)}, times_of_one_candle(remaining_time, max_fires))
                t_sim |= t

    return t_sim

def times_of_one_candle(burn_rate, max_fires):
    s = set([])

    for x in range(1, max_fires + 1):
        s |= {burn_rate / x}

    return s

We now have functions that return all the subsets needed for our equation in order to find all the possible sets given the correct parameters. Let's write a function all_times(), which takes in our three arguments candles, burn_rate, and max_fires and calls our helper functions to return the set of all times that we are able to achieve with these constraints.

def all_times(candles, burn_rate, max_fires):
    if candles == 0 or burn_rate == 0 or max_fires == 0:
        return set([])
    if candles == 1:
        return times_of_one_candle(burn_rate, max_fires)

    times = set([])

    s = times_of_one_candle(burn_rate, max_fires)
    times |= s

    for c in range(1, candles):
        t_sc = times_succession(times, s)
        t_sim = times_simul(times, s, max_fires)
        times |= (t_sc | t_sim)

    return times

s = sorted(all_times(2, 60, 3), reverse=True)
print('{}\nMagnitude: {}'.format(s, len(s)))
s = sorted(all_times(3, 60, 4), reverse=True)
print('{}\nMagnitude: {}'.format(s, len(s)))
s = sorted(all_times(4, 100, 5), reverse=True)
print('{}\nMagnitude: {}'.format(s, len(s)))
s = sorted(all_times(5, 100, 6), reverse=True)
print('{}\nMagnitude: {}'.format(s, len(s)))
s = sorted(all_times(6, 200, 5), reverse=True)
print('{}\nMagnitude: {}'.format(s, len(s)))
[120.0, 90.0, 80.0, 60.0, 50.0, 45.0, 40.0, 33.3333, 30.0, 25.0, 23.3333, 20.0]
Magnitude: 12
[180.0, 150.0, 140.0, 120.0, 110.0, 105.0, 100.0, 93.3333, 90.0, 85.0, 83.3333, ...]
Magnitude: 100
[400.0, 350.0, 333.3333, 325.0, 300.0, 283.3333, 275.0, 266.6667, 266.6666, ...]
Magnitude: 2414
[500.0, 450.0, 433.3333, 425.0, 420.0, 400.0, 383.3333, 375.0, 370.0, 366.6667, ...]
Magnitude: 30885
[1200.0, 1100.0, 1066.6667, 1050.0, 1040.0, 1000.0, 966.6667, 950.0, 940.0, ...]
Magnitude: 75430

The magnitude of each set displayed is simply the number of possible times. At this point, it's trivial to search for a time goal by reversing the process such that the script gives us candles, burn_rate, and/or max_fires given an input time goal.

Finally, it is also pretty trivial to imagine how many hours and chances ago I should have stopped trying to dive into this problem, but we both know those attempts were futile.