The Lemon Fool

An eccentric millionaire decided to open a bank account. She deposited x whole pounds. On day 2 she deposited y whole pounds. On day 3 she deposited x+y pounds. On subsequent days the amount added to the account was the sum of the previous two days’ deposits. On day 20 she deposited one million pounds. What are x and y?

Cinelli

By brute force,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
154, 144

cinelli wrote:An eccentric millionaire decided to open a bank account. She deposited x whole pounds. On day 2 she deposited y whole pounds. On day 3 she deposited x+y pounds. On subsequent days the amount added to the account was the sum of the previous two days’ deposits. On day 20 she deposited one million pounds. What are x and y?

Cinelli

It's a multiple of a Fibonacci number presumably. No time to consider now though...

GS

Both x and y follow the Fibonacci series. The 20th deposit is 2484x + 4181y.

1000000 and 2484 are both divisible by 8 so 4181y must also be divisible by 8. Since 4181 and 8 have no common factors, y must be divisible by 8.

Let z = y/8
4181y = 33448z

We can, therefore, say that 1000000 = 2484x + 33448z.

Brute force is easy from here, giving x = £154 and z = £18 as a unique answer.

x = £154, y = £18 * 8 = £144.

Julian F. G. W.

cinelli wrote:An eccentric millionaire decided to open a bank account. She deposited x whole pounds. On day 2 she deposited y whole pounds. On day 3 she deposited x+y pounds. On subsequent days the amount added to the account was the sum of the previous two days’ deposits. On day 20 she deposited one million pounds. What are x and y?

Wrote out my solution before looking at others. It's essentially jfgw's, but with a further step added to reduce the brute force from checking out 30 possibilities to just 2. Spoiler...

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

On day 1, she deposited 1*£x + 0*£y.

On day 2, she deposited 0*£x + 1*£y.

On day 3, she deposited 1*£x + 1*£y.

On day 4, she deposited 1*£x + 2*£y.

On day 5, she deposited 2*£x + 3*£y.

On day 6, she deposited 3*£x + 5*£y.

And so on.

Looking down the columns of coefficients, it doesn't take long to see that the well-known Fibonacci numbers are involved here and little longer to prove that, if we define them by F(0)=0, F(1)=1, F(n)=F(n-2)+F(n-1) for n>=2, then for N>=2:

On day N, she deposited F(N-2)*£x + F(N-1)*£y.

So we know that F(18)*£x + F(19)*£y = £1,000,000, with x and y positive whole numbers. Calculating the values of F(0), F(1), ..., F(19), or cheating by looking them up on https://oeis.org/A000045, they are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181

So 2584x + 4181y = 1000000.

Since 2584x and 1000000 are both multiples of 8, 4181y must be one as well, which means it must be a multiple of 8*4181 = 33448, the least common multiple of 8 and 4181. There are only 30 multiples of 33448 under 1000000, which is a manageable number of possibilities to check out, but that would be a bit tedious... To reduce that tedium, also note that 2584x is a multiple of 17 and 1000000 has remainder 9 when divided by 17, so 4181y must be a multiple of 33448 and have remainder 9 when divided by 17. As it happens, 33448 also has remainder 9 when divided by 17, so 4181y might be 33448.

If another multiple 33448n of 33448 has the same remainder when divided by 17, then 33448n - 33448 = 33448(n-1) is a multiple of 17, and since 17 is prime and does not divide 33448, that means that n-1 must be a multiple of 17. So the next conceivably possible multiple of 33448 is 33448*18 = 602064, and then the next one after that is 33448*35 = 1170680, which is too big. So 4181y is either 33448 (y=8) or 602064 (y=144).

Then 2584x is 966552 or 397936 respectively, which makes x= 374.0526... or 154 respectively. Since x is a whole number, that means the only solution is x=154, y=144.

Gengulphus

Well solved. But here is a further challenge - does anyone have a method which does not involve brute force?

Cinelli

cinelli wrote:But here is a further challenge - does anyone have a method which does not involve brute force?

Yes, there are number-theoretical methods for solving such equations - i.e. ones of the form Ax + By = C, where A, B and C are known whole numbers and x and y are unknown whole numbers. If a solution exists (it doesn't always, e.g. 4x + 6y = 11 doesn't have a solution, because the left hand side is even and the right hand side odd), it's not unique as a solution over all the integers - in particular, if (x,y) is a solution, so is (x+nB,y-nA) for any integer n. But if the problem is well-chosen, as in this case, it can be unique as a solution over the positive integers.

I don't really have the time to write out the general method right now, but if you'd like some hints, it involves Euclid's algorithm for determining the greatest common divisor of two integers and some extensions of it to perform other calculations, in particular ones to do with solving ax MOD m = b for x and with the Chinese Remainder Theorem (see https://en.wikipedia.org/wiki/Chinese_remainder_theorem). The first step is to calculate the greatest common divisor D of A and B and see whether it divides C: if it doesn't, there are no solutions because the left hand side of Ax + By = C is divisible by D and the right hand side isn't. Otherwise set a = A/D, b = B/D and c = C/D, and you have ax + by = c with a and b having no common factor (i.e. greatest common divisor = 1, or a and b are 'coprime' in mathematical jargon). That sets you up to use the Chinese Remainder Theorem to determine the solutions MOD ab - and that's as good as it gets, since the above observation also says that if (x,y) is a solution, so is (x+nb,y-na) for any integer n.

Gengulphus

Another method

.

.

.

.

.

.

.

.

.

.

Here we have a Fibonacci sequence with the well known relationship F(n+2) = F(n) + F(n+1). But there is another important relationship between the terms of the sequence: the ratio F(n+1)/F(n) approaches a limit as n increases. The limit is phi, the golden ratio, = (1+sqrt(5))/2 = 1.618034. Successive F(n+1)/F(n) values are alternately above and below phi. Moreover convergence to the limit is very quick – by the 18th term of any Fibonacci sequence the error between the calculated ratio and phi is only 0.00003%. Given that F(20) is 1,000,000, F(19) will be approximately 1,000,000/phi = 618033.99, very close to the integral value we know it must be. Given that F(19) is 618,034 we can work backwards to give all the terms of the sequence until x = F(1) = 154 and y = F(2) = 144.

Cinelli