Prove solution formula of the Water Bottles problem

Question

Problem

There are n water bottles that are initially full of water. You can exchange m empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers n and m, return the maximum number of water bottles you can drink.

Solution

$(int)Math.Ceiling((((double)n * m) / (m - 1)) - 1)$

My question

First, we will drink $n$ water bottles, after that we will exchange $n$ water bottles for $n/m$ full bottles and will drink them, then we will exchange the $n/m$ empty water bottles for $n/m^2$ and so on. So, at the end the number of water bottles we will drink will be $n + n/m + n/m^2 + n/m^3 + ... = n(1 + 1/m + 1/m^2 + 1/m^3 + ...)$.

Now, the $1/m + 1/m^2 + 1/m^3 + ...$ is a sum of an infinite geometric series, so $1/m + 1/m^2 + 1/m^3 + ... = (1/m) / (1 - 1/m) = 1 / (1 - m)$.

So, the number of drinked bottles will be $n(1 + 1/m + 1/m^2 + 1/m^3 + ...) = n(1 + 1/(1 - m)) = (n*m)/(m-1)$.

Where I am stuck

After that we also need to remove all the decimal part from the value of the $(n*m)/(m-1)$ or even subtract $1$ if the $(n*m)/(m-1)$ is an integer. And I do not understand this part.

Subconsciously I understand that there is such $k$ that starting with that $k$ all terms of the infinite geometric sequence $n/m^k$ are too small and hence do not make sense in context of the problem. Since we can not drink less than one bottle, i.e. drinking decimal bottles does not make sense. But I struggle to prove in any meaningful mathematical way that the sum of those terms will be decimal part of $(n*m)/(m-1)$ or $1$ if $(n*m)/(m-1)$ is an integer.

Also, it will be sum not only of those terms, but sum of those terms along with empty bottles which were not exchanged for a single full bottle yet. $p$ empty bottles equal $p*(1/m)$ in mathematical sense, so there are at most $m-1$ empty bottles which will never be exchanged for a full bottle, but which will add up to a decimal part of $(n*m)/(m-1)$ or even $1$ if $(n*m)/(m-1)$ is an integer.

And that complicates proving the last point even more. I want to somehow prove that sum of those not exchanged empty bottles and geometric series terms will be a decimal part of $(n*m)/(m-1)$ or $1$ if $(n*m)/(m-1)$ is an integer.

Answer 1

Suppose you drink in the end a total of $d$ bottles, the answer to the question.

You are going to end up with at least $1$ and no more than $m−1$ empty bottles: when you stop, you must have just emptied a bottle and not have enough empty bottles to get a new full bottle.

You started with $n$ full bottles, so acquired $d-n$ extra full bottles by handing over $m(d-n)$ empty bottles. So looking at the empty bottle you have left, $$1 \le d-m(d-n) \le m-1.$$ Assuming $m>1$, this implies $$\frac{mn}{m-1} -1 \le d \le \frac{mn}{m-1}-\frac{1}{m-1}.$$

You can write this as $d = \left\lceil \frac{mn}{m-1} - 1\right\rceil$ rounding up as in your question or as $d = \left\lfloor \frac{mn-1}{m-1} \right\rfloor$ rounding down - they give the same $d$.

Answer 2

You are overcomplicating the problem.
I have $n$ bottles, I divide them into $k$ groups of $m$ bottles each, and a remaining group of $r$ bottles, where $n = km+r, 0 \le r<m$. I drink $km$ bottles, to get $k$ bottles back. This observation is enough to perform induction.

Let $f(n,m)$ be the number of bottles you can drink if you have $n$ bottles, and get a new one after emptying $m$ bottles. You want to prove $$P(n): f(n,m) = \left \lceil \frac{nm}{m-1} - 1 \right \rceil$$ Assume this is true $\forall k<a$. Then $$\begin{align}f(a,m) &= \left\lfloor \frac{a}{m} \right\rfloor \cdot m + f\left(a - \left\lfloor \frac{a}{m} \right\rfloor\cdot (m-1), m\right) \\ &= \left\lfloor \frac{a}{m} \right\rfloor \cdot m + \left \lceil \frac{am}{m-1} - \left\lfloor \frac{a}{m} \right\rfloor\cdot m - 1 \right \rceil \\ &= \left \lceil \frac{am}{m-1} - 1 \right \rceil \end{align}$$

For the base case, prove it for $n=1,2,3, \ldots, m-1$, which is obvious since for $1\le k\le m-1$, $$k(m-1) = km-k \ge km-(m-1) > km-(m-1)-k = (k-1)(m-1)$$