I have an imaginary bank account with an initial balance $x$. I can only withdraw $0\% < w\% < 100\%$ (of the current balance) or deposit $0\% < d\% < 100\%$ (of the current balance) at a time, but I can do either one as many times as I want, and in any order. I'm given a target balance $y$ and I have to figure out how many withdraws and how many deposits I have to make to reach the target balance. I also have to state whether the target balance is in fact reachable.
Example:
If $x = 1000, w = 10\%, d = 20\%$ and $y = 972$, then I'd have to make $1$ deposit and $2$ withdraws.
I'm trying to figure out a good way to solve this problem with different values of $x$ and $y$, but also with different values of $w$ and $d$ if that doesn't make the problem more difficult.
What I've got so far:
- Order of withdraws/deposits does not matter.
- The formula is $x \times (1 + d)^a \times (1 - w)^b = y$, and then I have to solve for $a$ and $b$.
Algorithm 1 (which I'm not sure works, but also doesn't have a stopping condition for when there is no solution):
while current balance $\neq y$ do
if current balance $< y$ then
deposit and increment deposit counter
else
withdraw and increment withdraw counter
Algorithm 2 (which also doesn't have a stopping condition for when there is no solution):
Using the formula above, we can derive $a=\frac{\ln {\frac{y}{x\times (1-w)^b}}}{\ln {(1+d)}}$
Then check for every $b \in \{0,1,2,\ldots\}$ whether the resulting $a$ (according to the formula above) is an integer, and if it is, then $a$, $b$ is a solution.
Questions:
- Is the solution always unique? Does it depend on $w$ and $d$?
- Will Algorithm 1 always find a solution if it exists (is it correct)?
- Are there better ways of finding a solution (maybe even a closed form solution)?
- How can I know if there is no solution?
This is not homework. I found this problem in an old programming competition. I found it interesting and thought I'd take a closer look at it. Any help is greatly appreciated, but I'm in no hurry.