Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to johnstevens77,Bhoddhisatva,scotia,Anonymous,Cornytiv34, for Donating to support the site

Millionaire

cinelli
Lemon Slice
Posts: 550
Joined: November 9th, 2016, 11:33 am
Has thanked: 231 times
Been thanked: 160 times

Millionaire

#67496

Postby cinelli » July 15th, 2017, 1:10 pm

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

Rover110
Lemon Pip
Posts: 65
Joined: November 6th, 2016, 4:06 pm
Has thanked: 29 times
Been thanked: 23 times

Re: Millionaire

#67518

Postby Rover110 » July 15th, 2017, 2:44 pm

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

GoSeigen
Lemon Quarter
Posts: 4351
Joined: November 8th, 2016, 11:14 pm
Has thanked: 1590 times
Been thanked: 1581 times

Re: Millionaire

#67540

Postby GoSeigen » July 15th, 2017, 4:24 pm

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

jfgw
Lemon Quarter
Posts: 2540
Joined: November 4th, 2016, 3:36 pm
Has thanked: 1097 times
Been thanked: 1147 times

Re: Millionaire

#67544

Postby jfgw » July 15th, 2017, 4:54 pm

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.

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Millionaire

#67712

Postby Gengulphus » July 16th, 2017, 5:08 pm

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

cinelli
Lemon Slice
Posts: 550
Joined: November 9th, 2016, 11:33 am
Has thanked: 231 times
Been thanked: 160 times

Re: Millionaire

#68061

Postby cinelli » July 18th, 2017, 9:47 am

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

Cinelli

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Millionaire

#68148

Postby Gengulphus » July 18th, 2017, 2:49 pm

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

cinelli
Lemon Slice
Posts: 550
Joined: November 9th, 2016, 11:33 am
Has thanked: 231 times
Been thanked: 160 times

Re: Millionaire

#69136

Postby cinelli » July 23rd, 2017, 12:02 pm

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


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 5 guests