@george I don't follow it, either. There is some slick way of avoiding thinking about it recursively, but I don't see it yet. Have you tried examples? The formula seems to be right for the examples I've tried.
@george So if you work out examples, it then becomes clear how to prove the formula inductively — I still will think about where their "explanation" comes from. Let $f(n,m)$ be the number of hours you can light the room with $n$ candles, given that we make one new candle after $m$ are burned. Then $f(n,m) = f(n-m+1,m)+m$ (can you see that?). Now check that with $f(k,m)=k+[(k-1)/(m-1)]$, we have ...
@TedShifrin didn't try examples I was merely a bit angry that author just gave that brief explanation as solution. And i was surprised why i could not see how the solution directly flowed from his explanation
I think they're focusing on what gets you to the stage where you're burning the absolutely last candle. But I don't see an immediate way to justify the $m-1$. But it seems to make sense when you do the inductive step I wrote above.
@TedShifrin yeah i thought so my math got rusty, need to lookup complete induction. Anyway feel free to write up an answer too, maybe will be useful for someone else in future
people who are deep into combinatorics often have a sense of 'explanation' that does not correlate too highly with any intuitive one. e.g. a formula itself might count, or a formula plus a proof that it works might count, even if there is no explanation of where the formula came from. sometimes there is theory that semi justifies this way of thinking (e.g. WZ theory) but not always.
Combinatorial arguments can indeed be very clever, and I am not combinatorially clever. Most of those arguments come from looking at the problem a different way :) That might be the case here.
@george What book is this, anyhow?
I admit, though, having given a valid proof, I would like a nice way to understand the formula.
because i am a symbol pusher, i definitely count a formula plus a proof that it works as an explanation. maybe not the best explanation, but definitely an explanation. even an explanation that might stop me from looking for a better explanation.
We want to think of additional candles as coming from dividing $n-1$ (all but the last candle left burning) into groups which will give additional candles. But each of those groups will in turn lead to further candles, etc. I think that's why there's an $m-1$ rather than $m$, but I don't see it yet.
Let's just focus on that. I have $k$ books. I stack them into groups of $m$. That's $[k/m]$ groups, hence $(k-m[k/m]) + [k/m]$ books in round 2. Now I group those into $m$, etc. There's got to be a nice way to do this.
@TedShifrin Thank you for your feedback. I thought in such way : Since $x=-y\iff y=-x$ and since if $ \frac{y}{x-z}=\frac{y+x}{z}=\frac{x}{y}$, then $y,z≠0$ otherwise the equality would not hold, therefore I thought that, I need only $x+y≠0$ for applying the Fraction Arithmetic . Therefore, I tried to show that, $x+y=0$ can not be possible, which contradicts with the problem statement. Therefore, the Fraction Arithmetic can be applied .
@lone The fraction arithmetic presupposes the fractions all make sense in the first place. The OP is reading a book that allows them NOT to make sense. That's why we move to this system of quadratic equations instead.
i really don't understand the degree to which people bring material from really old books to MSE. i understand why people don't always use the most recent books, or the books regarded as "classics" in some parts of the USA. but copyright considerations (for example) wouldn't explain why people dig into this really old stuff.
and if their instructors are working from templates developed decades ago and nobody has bothered to change, that's... a lot of decades of not changing.
Well, sadly, leslie, as the OP said, even in "modern-day" calculus classes (NOT MINE) and books, people do write crap like this with parametric equations.
@TedShifrin I see at least I will not be suffering by thinking I was too dumb that I didn't realize how from this books explanation the solution followed
i just don't understand how self study would lead one into the 19th century, unless it was self study on the history of the subject, and not trying to learn it in the first instance. and i refuse to believe that people are intentionally teaching out of these books for any good reason.
Well, the first thing you should do, @george, particularly if you're that sort of person, is work out examples, and working the examples leads you to the formula in a reasonable way. But I agree they haven't explained it.
@TedShifrin How did you see the formula from examples, didn't you just assume "k+[(k-1)/(m-1)]" in the induction and you assumed that because the books explanation said so, wasn't that the case?
I have recently been self-studying group theory, and it has inspired me how deeply fundamental the material is. The only other math subject that I find as profound (still an undergrad) is linear algebra. Any other subjects in math that are comparable in this regard? (Topology? Will take it next semester.)
I've checked and it was introduced in 1944 as a covering property by Dieudonne. As a covering property, seems to imply it was known earlier, just not in the standard form
@TedShifrin Also one thing out of curiosity, in this response "Maybe you read it after the last candle had burned out, @george. " it was humor when I said about illumination right ? :) Just asking out of curiosity if I "got" it no big deal
You are down to your last candle burning. So you have $N-1$ to convert and get more to burn. It's the repeated process that leads to dividing $N-1$ by $M-1$ instead of by $M$.
@DavidRaveh topology certainly comes up a lot, although often more as a language for talking about stuff than, like, as a bag of specific tools or theorems that you use. i guess group theory is also like this, it is way more common to encounter groups and use their basic theory/notions than it is to use deep results specific to group theory.
Let's go by example. N = 4 M =2 1) Burn 4 candles (4 hours) 2) Now we have 4 waxes 3) Make 2 New candles 4) Burn those two candles (2 more hours) 5) We have one more new candles due to step 4 6) Burn that one too (1 more hour) 7) We have that final unused and burnt candle
So you get 3 -> 1 new candle plus 1 left over. When the last burning candle is burning out, you light the 1 new candle. You then have the left over candle and the one you just burned. Those two trade to one last new candle.
@TedShifrin Sorry it is getting late here and I need to go to bed soon :( (due to work) It will be best I think if you write up an answer which conceptually explains and justifies use of N-1 and M-1
@TedShifrin Ok I will try. But why is there dark in my room? First step 4 hours it is lit right? When the fourth hour ends I can already use new candle obtained from burning first two candles. Then I can use candle obtained by burning 3rd and 4th candles. And then I can create final new candle and immediately burn it
@TedShifrin Anyway if you don't feel like explaining anymore it is OK too, no big deal
Oh, the first answer really does explain it in a valid way. And now I understand that awkward sentence. Every time you burn $M$, you get a new one, so you have a net loss of $M-1$ candles. So we need to know how many groups of $M-1$ there are in $N-1$.
@TedShifrin Hmm.. Ok I hope tomorrow when I come back to this chat it will be more clear for me. if you write an answer it will be even better potentially for others. Either way, thanks and good luck!
