8
$\begingroup$

Today I heard a rumor that my bank will go bankrupt soon. So I went to my bank, and indeed I found out that they have introduced some weird new rules that clearly indicate that there is something wrong with this bank.

  • I am allowed to withdraw exactly 300 Euro from my account.
  • I am allowed to deposit exactly 132 Euro into my account.
  • I am allowed to do such withdrawals and deposits as often as I like.
  • I am not allowed to do any other transactions with my account.

On my bank account, there are currently 1000 Euro. I am certainly not willing to deposit any additional money into the bank account, but I am willing to play around with the money that currently is on the account.

Question: What is the largest amount of money that I can withdraw from the bank?

$\endgroup$
1
  • 2
    $\begingroup$ What kind of bills/coins does the ATM accept and produce? If it only gives you 100-€ bills, you'll have problems to deposit 132 € after using your existing coins. $\endgroup$ Mar 8, 2015 at 22:42

4 Answers 4

13
$\begingroup$

The GCD of 300 and 132 is $12$. So the quantity you can take out is always a multiple of $12$. In theory we can take out at most $83\cdot 12=996$, leaving four in the bank.

Every day make sure you deposit exactly nine times and withdraw exactly $4$ times. This is possible as long as you have $16$ or more dollars in the bank. After this we end up having $12$ less than at the beginning of the day in the account.

So if we do this $83$ days at the end we will have $83\times 12=996$ less coins in the account than at the beginning, so we will leave only $4$ dollars in the bank.

$\endgroup$
3
  • 2
    $\begingroup$ Ehm, I must be missing something, but why not do all this in a single day? $\endgroup$ Mar 9, 2015 at 2:10
  • 1
    $\begingroup$ You can do it in a singe day if you want. I just wrote it that way because I thought it was clearer. $\endgroup$
    – user10001
    Mar 9, 2015 at 2:11
  • 1
    $\begingroup$ Aaaah, wow, my bad. Still though, wouldn't risk it if you're afraid of your bank going bankrupt ;-) $\endgroup$ Mar 9, 2015 at 2:26
11
$\begingroup$

The answer is

996 euros

because what you need to do is find non-negative integers $a$ (number of withdrawals) and $b$ (number of deposits) such that $1000-300a+132b$ (amount left at the end) takes the minimal possible non-negative value.

$1000-300a+132b$ is always a multiple of 4, and we can make it exactly 4 by setting $a$ to be 13 and $b$ to be 22. So 4 is the minimal possible value of the amount left in the bank, which means the answer to your question is 996 - although the answer to the title of your question is yes ;-)

More explicitly, here's exactly what you need to do:

  • withdraw 900 euros ($a=3$, $b=0$), leaving 100 euros in your account
  • deposit 792 euros ($a=3$, $b=6$), leaving 892 euros in your account
  • withdraw 600 euros ($a=5$, $b=6$), leaving 292 euros in your account
  • deposit 660 euros ($a=5$, $b=11$), leaving 952 euros in your account
  • withdraw 900 euros ($a=8$, $b=11$), leaving 52 euros in your account
  • deposit 924 euros ($a=8$, $b=18$), leaving 976 euros in your account
  • withdraw 900 euros ($a=11$, $b=18$), leaving 76 euros in your account
  • deposit 528 euros ($a=11$, $b=22$), leaving 604 euros in your account
  • withdraw 600 euros ($a=13$, $b=22$), leaving 4 euros in your account (the minimum possible)
  • take your 996 euros and run!
$\endgroup$
5
  • $\begingroup$ Isn't 1000 also divisible by 4? You can have zero money left in the bank as well. $\endgroup$
    – user88
    Mar 8, 2015 at 22:54
  • 2
    $\begingroup$ Not with the given parameters. He only wants to deal with the 1000 in the account. Since the lowest number divisible by 300 that you can reach with 132 additions is 3300, it'll never happen. $\endgroup$
    – Josh
    Mar 9, 2015 at 3:58
  • $\begingroup$ Can't he simply withdraw 240 Euros 4 times? Shouldn't a problem I guess since it's under 300 Euro limit. $\endgroup$
    – Robert hue
    Mar 9, 2015 at 6:38
  • $\begingroup$ @Roberthue " withdraw exactly 300" He can withdraw no more nor less than 300. $\endgroup$
    – Shelvacu
    Mar 9, 2015 at 6:55
  • $\begingroup$ @shelvacu got it. And also sorry for typo in my earlier comment. It was suppose to be 250 Euro. $\endgroup$
    – Robert hue
    Mar 9, 2015 at 8:41
5
$\begingroup$

First, this problem can be simplified into $(250,75,33)$ instead of $(1000,300,132)$.

If we deposit 22 times and withdrawl 13 times, we will have exactly 1 left in the bank which when you remove my simplification is \$4 which means you withdrew \$996 of you \$1000.

This will require withdrawing everything you can, depositing everything you can, and then repeating.

$$250=75w-33d$$

$$w=(250+33d)/75 = 10/3+11d/25$$

Trying for values of d, the remaining balence value for 22 is the smallest for any value less than 10,000 deposits. This seems to be because there are no integer solutions for the equation above.

$\endgroup$
0
1
$\begingroup$

Same answer but a different approach.

It is easier to first ignore the balance limit of $\\\$1000$, so that the order of deposits and withdrawals doesn't matter. The amount of money left in the bank after the whole process will be $1000+132d \mod 300$, as we're attempting to make a maximum withdrawal. This function has a cycle of length $25$, since $132*25=3300$. Checking these $25$ possibilities, the best that can be achieved is with $22$ deposits, giving a total balance of $\\\$3904$ and corresponding to $13$ withdrawals.

The last step is to find an order for these deposits and withdrawals such that the balance doesn't go over $\\\$1000$, but this is easily achieved by alternating the maximum possible number of withdrawals and deposits, as detailed in other answers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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