Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
I still have unanswered questions, but I'll just keep exploring on my own. Thanks. –  SuprDewd Mar 7 '12 at 0:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.