# Methods of solving a problem regarding withdrawing and depositing from a bank account.

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:

1. Is the solution always unique? Does it depend on $w$ and $d$?
2. Will Algorithm 1 always find a solution if it exists (is it correct)?
3. Are there better ways of finding a solution (maybe even a closed form solution)?
4. 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.

-
If you have an imaginary bank account don't try to square it, or else you may risk going bankrupt. :) – Andrea Mori Feb 29 '12 at 17:22

First, $x$ and $y$ are not independent variables, you only care about $\frac yx$
If we take the log of your equation, we get $$a \log(1+d) + b \log(1-w)=\log \frac yx$$
It seems you want an exact solution with $a,\ b$ both naturals. When you use a computer to check for an exact solution you need to be careful because small errors will prevent it being found. In your case, you are right for $\frac yx = 0.972$, but suppose you were asked about $\frac yx= 0.97199999999?$
A solution will be unique unless there is a way to have $a \log(1+d) + b \log(1-w)=0$, in which case a series of $a$ deposits and $b$ withdrawals leaves you back where you started. If $d=25\%$ and $w=20\%$, one deposit and one withdrawal take you back to start.