3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. So you cannot drink $\frac {nm}{m-1}$ bottles, but can drink at least $\frac {nm}{m-1}-1$. There is only one such integer. $\endgroup$
    – Henry
    Mar 2 at 16:38
  • $\begingroup$ @Henry, and along with infinite geometric sequence those $1$ to $m-1$ empty bottles may result in even one full bottle. But I do not know how to prove that there will be at most $1$ "fake" bottle and that if $(𝑛∗𝑚)/(𝑚−1)$ is integer such a bottle guaranteed to be. $\endgroup$
    – iloveseven
    Mar 2 at 16:42
  • $\begingroup$ IMO there are some quirks: "You can exchange m empty water bottles for one full water bottle." One single full bottle? If $m=n$ and you did drink $n$ bottles, you should get in exchange of $m$ empty bottles a full one -- but there are none left and the process stalls. Altogether you may drink $n$ bottles only, there are no more than $n$. $\endgroup$
    – m-stgt
    Mar 2 at 17:04
  • 1
    $\begingroup$ @m-stgt If $m=n>1$ the you empty all $m=n$ full bottles and have that number of empty bottles, which you exchange for $1$ full bottle and empty that, leaving you with $1$ empty bottle. You have drunk $m+1=n+1$ full bottles $\endgroup$
    – Henry
    Mar 2 at 18:08

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ You need to add that a $d$ always exists since $\left\lfloor \frac{mn}{m-1} - 1\right\rfloor$ and $\left\lfloor \frac{mn-1}{m-1} \right\rfloor$ can never be equal as that would imply $\left \{ \frac{mn}{m-1} \right \} < \frac{1}{m-1}$. $\endgroup$
    – D S
    Mar 2 at 18:29
  • $\begingroup$ @DS, what does the curly braces mean? Sorry, I forgot it. I mean these: {. $\endgroup$
    – iloveseven
    Mar 2 at 21:18
  • 1
    $\begingroup$ @iloveseven $\{x\}=x-\lfloor x\rfloor$ i.e. the fractional part of $x$ $\endgroup$
    – Henry
    Mar 2 at 21:20
  • $\begingroup$ @DS, I just take difference of boundaries $((\frac{mn}{m-1} - \frac{1}{m-1}) - (\frac{mn}{m-1} - 1)) = \frac{m - 2}{m-1}$. Since $m$ is integer and $m > 1$, the difference is less than $1$ and hence only a single integer (which is $d$) is possible. What do you think? $\endgroup$
    – iloveseven
    Mar 2 at 21:26
  • 1
    $\begingroup$ $d$ is an integer because of the question as you only have integer bottles. $\left\lceil \frac{mn}{m-1} - 1\right\rceil$ and $\left\lfloor \frac{mn-1}{m-1} \right\rfloor$ are integers because they are each rounded to an integer $\endgroup$
    – Henry
    Mar 2 at 21:47
2
$\begingroup$

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)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .