A candle burns for an hour, and $M$ burnt candles can make a new candle. For how long can $N$ candles keep the room lit?

Question

There is a solution to a puzzle about candles, which I can't follow.

Here is the puzzle:

Imagine there are $N$ candles. Each of the candles takes $1$ hour to burn. Out of burnt $M$ candles you can make one new candle. What is the longest you can keep the room lit?

The book I have gives such solution:

If we take into account that after making a new candle, the number of burnt out candles reduces by $M-1$ and that finally we will still have one unused burnt out candle left, the answer can be computed using $$N + \frac{N-1}{M-1}$$

Specifically what is confusing me is why could we use $N-1$ as numerator and $M-1$ as denominator, based on this explanation: "If we take into account that after making a new candle, the number of burnt out candles reduces by $M-1$ and that finally we will still have one unused burnt out candle left..." ?

Can someone help? I am not a professional mathematician also and please explain in understandable terms, so far none of the answers have managed this.

Answer 1

To make the text solution clearer, I will assume that $M - 1$ divides $N- 1$. Otherwise, it should be

$$N + \left\lfloor \frac{N-1}{M-1} \right\rfloor.$$

It should be clear that an optimal strategy has at any time only one candle used to lit up the room.

Hence, we may proceed as follows: First, we use up all the $N$ candles one by one. This gives us $N$ hours and $N$ burnt candles, corresponding to the first term.

Obviously, to keep going, we take $M$ of those burnt candles and make a new candle out of them. When that one is burnt out, we gained one extra hour and used up $M$ burnt candles which now resulted in $1$ burnt candle. Abstractly, and this is what is meant by the solution, for every new hour we gain we use up $M-1$ burnt candles and are always left with (at least) one burnt up candle (namely, the last candle we lit).

Now, just to be really explicit here, let $H$ be the number of new hours gained. The above text says

$$N - H \cdot (M-1) \geq 1 \implies H \leq \frac{N-1}{M-1}.$$

And since $M-1$ divides $N-1$, the inequality can be attained.

Further comments: To expand on why the inequality turns into an equality, let's imagine that the first $N$ hours passed and we are left with those $N$ burnt candles. Let $H = (N-1) / (M -1)$. This is a positive integer since $M- 1 $ divides $N-1$. Now, leaving one candle aside, we can group the other $N-1$ burnt candles into $H$ groups of size $M-1$. For each of the $H$ groups, we can form a new candle with the set-aside candle and thus gain one hour from the new candle and are left again with a burnt candle. So, we gain in total $H$ more hours.

Answer 2

It's a question of how many hours can you burn N candles. And how quickly are new candles added to the "pool" of candles.

When M divides N exactly. N=4, M=2, t=0
N=3, M=2, t=1
N=3, M=2, t=2
N=2, M=2, t=3
N=2, M=2, t=4
N=1, M=2, t=5
N=1, M=2, t=6
N=0, M=2, t=7

When M doesn't divide N exactly. N=3, M=2, t=0
N=2, M=2, t=1
N=1, M=2, t=2
N=1, M=2, t=3
N=0, M=2, t=4

In general, t = f(N,M) = N + floor(N/M)

Depending on your definition of the floor function. You'll notice the positive variant here looks very familiar. https://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Quotients

and in fact it's this more generally. https://en.wikipedia.org/wiki/Hermite%27s_identity

If you replace floor(N/M) with the appropriate definition you'll get t = f(N, M) = N + (N-1)/(M-1)

Answer 3

Let $f(x) := \lfloor x/M \rfloor + \text{mod}(x, M)$. This function counts how many burnt candles are created from lighting $x$ new candles.

Therefore, the total number of hours we can light the room is $$N+\lfloor N/M \rfloor + \sum_{i=1}^\infty \left\lfloor \frac{f^{\circ i}(N)}M \right \rfloor$$

All that is left to prove is

$$\left \lfloor \frac{N-1}{M-1} \right \rfloor = \left \lfloor \frac N M \right \rfloor + \sum_{i=1}^\infty \left\lfloor \frac{f^{\circ i}(N)}M \right \rfloor$$

but

$$\left \lfloor \frac{N-1}{M-1} \right \rfloor - \left \lfloor \frac N M \right \rfloor = \left \lfloor \frac{\lfloor N/M \rfloor + \text{mod}(N,M)}M \right \rfloor + \sum_{i=2}^\infty \left\lfloor \frac{f^{\circ i}(N)}M \right \rfloor$$

if and only if

$$\left \lfloor \frac{N-1}{M-1} \right \rfloor - \left \lfloor \frac {N + \lfloor N/M \rfloor} M \right \rfloor = \sum_{i=2}^\infty \left\lfloor \frac{f^{\circ i}(N)}M \right \rfloor$$

Now, can you apply the trick recursively to prove the recurrence?

Answer 4

This is really more of an addendum to @MXXZ's answer. I obtained an ostensibly different result using a another approach and was a little perplexed until I could show them equivalent.

An important point is that when we end, we have at least one (and fewer than $m$) burned candles.

Suppose that we gain $H$ new hours, then we have burned $N+H$ candles and in doing so made $H$ new candles. Hence we must have $H = \lfloor {N+H \over m} \rfloor = {N+H \over m} - {k \over m}$, with $k \in \{0,...,m-1\}$.

Since we end with at least one burned candle, we see that $k \in \{1,...,m-1\}$.

Equivalently, $(m-1)H = N-k = N-1 - (k-1)$ or $(k-1) + (m-1)H = N-1$, or ${k-1 \over m-1} + H = {N -1 \over m-1}$. Since $k-1 \in \{0,...,m-2\}$, we see that $H = \lfloor {N-1 \over m-1} \rfloor$ which is the same as @MXXZ's answer.