2
$\begingroup$

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.

  • 2
    If you have an *imaginary* bank account don't try to square it, or else you may risk going bankrupt. :)2012-02-29

1 Answers 1

1

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.

  • 0
    I still have unanswered questions, but I'll just keep exploring on my own. Thanks.2012-03-07