Million Dollar Bank Prize - MPMP

README.md

This problem is from the series of Matt Parker's Maths Puzzles and the video

Million Pound Bank Prize

A bank is offering a promotion! Patrons are able to open an account and make a single deposit on the first and second days. Each day the account earns the previous day's balance in interest. The bank stipulates that if the account ever holds exaclty one million pounds then the account holder will be able to withdraw the one million pounds. In order to reduce risk the bank adds a clause that states that only the account holders that take the longest amount of time to earn the million pounds will be able to withdraw it.

For example: If the account holder deposited 1 pound on the first day and 2 pounds on the second day they would grow their investment as follows

Days	Balance
1	1
2	1 + 2 = 3
3	3 + 1 = 4
4	4 + 3 = 7
⋮	⋮
27	439204
28	710647
29	1149851

Since the balance went over one million pounds, and will only grow larger, the account holder can never win and their 3 pound investment is forfeit.

Suppose instead there were two account holders, Alice and Bob. If Alice deposited one pound and then 999,999 pounds, and Bob deposited 400,000 pounds and then 200,000 pounds, then Alice would achieve the milllion pounds but Bob would reach the million pounds one day after Alice, meaning Alice would not be able to withdraw the prize. Similarly if anyone reached the million after Bob, he would not be able to withdraw either.

Insights

We can derive the balance on day n, write B(n), with the following recurrence relation:

• B(1) = d₁; the balance on the first day is the value of the first deposit,
• B(2) = d₁ + d₂; the balance on the second day is the sum of the two deposits,
• B(n) = B(n - 1) + B(n - 2) for n > 2; the balance on subsequent days earns interest equal to the previous day's balance.

It is not immediately obvious whether two starting values will generate exactly the target balance, however if we only want to consider the sequences that do, we can ensure this by starting at one million and working backwards.

Firstly we can rearrange the recurrence relation to realise the following:

• B(n - 2) = B(n) - B(n - 1)

So if the balance on day t is the target balance, T, that is B(t) = T, and the balance on the day prior was S, that is B(t - 1) = S, we can calculate a new sequence, R(n), which looks like the bank balances in reverse, that is:

• R(1) = T
• R(2) = S
• R(n) = R(n - 2) - R(n - 1)

At any point, we can calculate deposits that wil generate the target balance; we can choose k, and then if we deposit R(k) pounds on the first day and R(k + 1) pounds on the second day, we will reach the target balance on the kth day.

We now have to ask whether R(k) and R(k + 1) are valid deposits; they could be negative values for example. If the bank allows the account to become overdrawn, then we can fix some S, and follow the sequence for as long as we like, choosing some k such that R(k) and/or R(k + 1) are arbitrarily large negative numbers (this comes from the relationship between R and the fibonacci sequence, which grows arbitrarily large). We could then withdraw money on the first and second days and eventually the balance would reach the target and we would also win the prize!

It would be foolish perhaps to allow this situation to occur thus we should assume the bank will not allow the accounts to become overdrawn. Instead, we should choose the largest k such that R(k) and R(k + 1) are both positive. We can use reasoning from the original accounts to see that all the balances R(i) where i < k must also be positive and that these will be valid deposits.

We now have an algorithm for searching for the longest time that we can generate the target in:

• For each second last balance S in [0, T), we can calculate the largest k such that R(k) and R(k + 1) are both positive.
• The maximum k over all S is the longest time to reach the target, and the values R(k) and R(k + 1) for this S and k are the initial deposits that generate the target balance.

If we remember the deposits we can use those values to win the competition.

If we graph the maximum k against S for fixed T, we can see that the maximum seems to live at the exact same place; somewhere around 0.618·T.

This is no coincidence, as we can see that the longest sequence will occur when the ratio between R(k) and R(k + 1) is as close as possible to that of R(k + 1) and R(k + 2).

If these ratios are equal, and S < T, then we will never reach a point where R(k) < R(k + 1), that is if we knew that the longest time any other person would take is i days, we would be able to beat it by choosing our deposits carefully.

The question remains, when will the ratios be equal, well, if we fix T, we want to choose S such that S / T = (T - S) / S. We can simplify this by making the substitution c := S / T and we have c = (1 - c) / c, which we can solve to find solutions c = (-1 ± √5) / 2, we can discard c = (-1 - √5) / 2 as it is negative and we need to have a positive balance, giving us the value c = (-1 - √5) / 2 ≈ 0.618!

The constant c is φ - 1, where φ is the golden ratio. This relationship occurs due to R being very similar to the fibonacci sequence.

Now, given a target T, we can follow the sequence R' defined by the following recurrence relation:

• R'(1) = T
• R'(2) = c·T
• R'(n) = R'(n - 2) - R'(n - 1) = c^n-1·T

Then for arbitrarily large k, R'(k) and R'(k + 1) are valid initial deposits that will generate the target balance after k days.

If the bank does not allow fractional deposits, then the maximum number of days can be found by iterating R where S = round(c·T).

deposits.py

from math import sqrt

c = (-1 + sqrt(5)) / 2

def longestTime(target):
  """
  This method iterates the sequence R (in the explanation) that will generate
  the longest sequence of *integer* balances that reaches the target, and
  returns the largest k such that R(k) > R(k + 1), and also the initial deposits
  to generate this longest sequence.

  The sequence R can be understood to be the bank balance with time running in
  reverse. 
  """
  # now = R(k + 1) and before = R(k + 2)
  now, before = target, round(c * target)
  k = 0
  while now > before:
    now, before = before, now - before
    k += 1
  return k, now, before

target = 1000000
days, depositA, depositB = longestTime(target)
print('Any account holder wishing to win the competition should:')
print()
print('\tDeposit {} pounds on the first day,'.format(depositA))
print('\tand deposit {} pounds on the second day.'.format(depositB))
print()
print('If they do this they will reach exactly', target, end=' ')
print('pounds after', days, 'days.')