Discussion between george and MXXZ

Feeds

12:51

A: 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?

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, w...

george

If it is how you say it is, the explanation in the book is pretty bad no? (n-1)/(m-1) doesn't immediately follow from what is written in the book, you have to get there via that inequality. The book says it like it follows immediately. Also in the solution (n-1)/(m-1) is directly used but you ended up with <=. Does that change anything?

MXXZ

Concerning the inequality, it at first only gives you the fact that $N + \frac{N-1}{M-1}$ is an upper bound on the number of hours. But again, because of the divisbility condition, you can get that it is in fact an equality by following the argument above. If you need further clarification on that, let me know.

Whether the solution is bad really depends on what the audience of the book is. If it is supposed to be an advanced book, then it is somewhat expected that they will leave simple calculations out. I will say though that the solution is very compressed even by those standards.

george

"because of the divisbility condition, you can get that it is in fact an equality by following the argument above."- why divisibility implies equality? no this is not advanced book :(

MXXZ

I expanded on that in my answer.

george

Let's follow like this. 1) You burn N candles and get N hours. 2) Now you have N burnt candles 3) Now you take out one burnt candle for some reason. 4) You have N-1 burnt candles now and you divide them on M-1 and get say H 5) Now you have H new candles and also one burnt candle from step 3. So what ? How do you proceed now?

2 hours later…

MXXZ

14:26

I think you misunderstood what I am saying. Maybe a visual will help: Let's consider $M = 3$ and $N= 9$.

After 2) you have 9 burnt candles. I would separate the burnt candles (represented by "i") as follows:

i | ii | ii | ii | ii

Now, just take the one on the left, the first group of two to form a new candle (represened by "c") which - after an hour - is burnt up:

i | ii | ii | ii | ii -> c | ii | ii | ii -> i | ii | ii | ii

See the pattern? You can just group the one with one of the "ii", get a "c", which in turn burns for an hour, and then get i | ii | ii. Abstractly, with every hour, one "ii" disappears and you are left with one burnt candle. Now how many groups did you have? $4 = 8 / 2…

george

14:57

@MXXZ well yes and no, I can see how that works, but Why did you choose to group them in this manner :
i | ii | ii | ii | ii. And not some other combination. Say group them in three. Or initially separate two candles out instead of one. Thats the main question.

In other words i want a proof why your approach works instead of plugging in concrete numbers as you did :) how the author arrived at the solution of (n-1)/(m-1).

MXXZ

15:42

Okay, let's review what I proved. I showed that you can lit the room for at most $N + (N-1) / (M-1)$. So, the only thing we need to do afterwards is just to give one strategy attaining the $N + (N-1) / (M-1)$ bound. And I gave one in one of my initial comments. Here I just plugged the numbers in for the thing I did.

MXXZ

15:53

You don't really need the groupings and maybe formulating it like this helps (I hope I am not repeating myself too much but I don't see how I can be more clear): After all $N$ candles are burnt up, you have no other choice than to create a new candle using $M$ burnt ones. After an hour, that one will be burned.

You used $M$ burnt candles and are left with one burnt candle after the hour. And to keep the room lit, you repeat the above. So, with every hour, the number of burnt candles you have decreased by $M-1$. Thus, you can keep going until you are left with less than $M$ candles.

Let that point in time (after the $N$ initial hours) be $H$. $H$ is the smallest integer such that $N - H * (M-1) < M$. Solving for $H$ gives you $H > (N - M) / (M-1) = (N - 1) / (M - 1) - 1$. $(N - 1) / (M - 1)$ is an integer and thus $H = (N - 1) / (M - 1)$.

I hope this makes it clear, otherwise I am having a hard time in further helping you.

george

16:39

I will look into this tomorrow thanks for trying

last day (15 days later) »

all rooms