Note that interest doesn't matter.

There is one integral solution for D1 and D2.

D1 = x

D2 = y

D3 = x+y

D4 = x+2y

D5 = 2x+3y

D6 = 3x + 5y

D7 = 5x + 8y

D8 = 8x + 13y

D9 = 13x + 21y...

D20 = 2584x + 4181y = 1,000,000

There is only one solution that is integral.

Do you have the answer? Can I PM you with my two numbers and see if I am correct?

154 and 144

Answer ^

There is also a shortcut that uses the fact that the two coefficients are in the Fibonacci sequence.

Quote:dwheatleyThere is also a shortcut that uses the fact that the two coefficients are in the Fibonacci sequence.

0 | 0 | 11 | 89 | 22 | 17,711 |
---|---|---|---|---|---|

1 | 1 | 12 | 144 | 23 | 28,657 |

2 | 1 | 13 | 233 | 24 | 46,368 |

3 | 2 | 14 | 377 | 25 | 75,025 |

4 | 3 | 15 | 610 | 26 | 121,393 |

5 | 5 | 16 | 987 | 27 | 196,418 |

6 | 8 | 17 | 1,597 | 28 | 317,811 |

7 | 13 | 18 | 2,584 | 29 | 514,229 |

8 | 21 | 19 | 4,181 | 30 | 832,040 |

9 | 34 | 20 | 6,765 | 31 | 1,346,269 |

10 | 55 | 21 | 10,946 | 32 | 2,178,309 |

I think I have a more elegant solution.

Using the shifting property of Fibonacci sequences: Fm+n = Fm · Fn+1 + Fm-1 · Fn

And the fact that m=19 is specified in the problem then select an n is as large as possible and also so the Fm+n < 1 million.

It is obvious that F30< 1 million , so n=11 is the solution

F30 = F19 · F12 + F18 · F11 (the shifting property for m=19, n=11

832,040 = 4181*144+ 2584*89 which is easily verified

But I want the left hand side to equal to 1 million or an additional 1000000 - 832040 = 167960

But 167960 is an integral multiple of 2584 or 167960 / 2584 =65

So increase the 89 by 65

832,040 = 4181*144+ 2584*89

167,960 = 2584 *65

1,000,000 = 4181*$144+ 2584*($89+$65)

So the first deposit must be ($89+$65) = $154 and the second must be $144

Quote:pacomartin

But 167960 is an integral multiple of 2584 or 167960 / 2584 =65

Is this just a coincidence?

If it is, I don't see how this is more elegant - you just got lucky, if not for that, you'd end up with the same kind of equation - 4181*x + 2584*y = 167690.

The numbers are a little smaller, which is good, but for this to work, you have to be sure that the actual deposit values are greater than 88 and 143 respectively, which to me does not seem obvious a priori.

Or is there some reason to believe that one of the amounts is itself a Fibonacci number, that I am missing? If there is such a reason, then, of course, this solution is way more elegant.

I took 1,000,000 and divided it by the golden mean, 1.618033989. That gave me 618,033.9887. I then started with 1,000,000 and subtracted 618,034 (I rounded the previous non-integer). Continue subtracting and the last two numbers are 144 and 154. Should this have worked or was I lucky?

Quote:weaselmanIs this just a coincidence?

Or is there some reason to believe that one of the amounts is itself a Fibonacci number, that I am missing? If there is such a reason, then, of course, this solution is way more elegant.

No, there was no reason to believe that one of the amounts is itself a Fibonacci number. If the difference had not been a multiple of 2584, then I would have had to iterate it again. I would find a Fibonacci number smaller than 167,960 (F25) which would imply that n=6.

But eventually the difference has to be a multiple of either 4181 or 2584 or there is a null solution. We assume that there is no "null solution" or the question wouldn't be in the NY Times. When I started the problem I expected to iterate more than once, but it wasn't necessary.

F30 = F19 · F12 + F18 · F11

832,040 = 4181*144+ 2584*89

If the remainder did not have 2584 or 4181 as a divisor then

F26 < 167,960

F26 = F19 · F7 + F18 · F6

Do the difference again

======================================================

The more brute force way is to set up a simple spreadsheet to test for divisors until you find the first one to work.

i'th | 1,000,000 | |
---|---|---|

4,181 | 2,584 | |

1 million-i*4181 | test if number is divisor of 2584 | |

1 | 995,819 | test fail |

2 | 991,638 | test fail |

3 | 987,457 | test fail |

4 | 983,276 | test fail |

5 | 979,095 | test fail |

… | ||

144 | 397,936 | test pass |

When the test passed the divisor was 154

Probably the simplest test would be GCD function (Greatest Common Divisor). Test if GCD(number to the left, 2584) = 2584.

If the test is True then the divisor is (number to the left)/2584 = 154.

Dim Deposit(1 to 20)

FOR deposit_one = 1 TO 1000

.....FOR deposit_two = 1 TO 1000

..........Deposit(1) = deposit_one: Deposit(2) = deposit_two

..........FOR x = 3 TO 20

...............Deposit(x) = Deposit(x-1) + Deposit(x-2)

..........NEXT

..........IF Deposit(20) = 1000000 THEN

...............PRINT "Found it!"

...............PRINT "Deposit #1 ="; deposit_one

...............PRINT "Deposit #2 ="; deposit_two

..........END IF

.....NEXT deposit_two

NEXT deposit_one

The program finds the answer instantly. (Less than half a second.)

Program Output:

Found it!

Deposit #1 = 154

Deposit #2 = 144

Quote:pacomartin

The more brute force way is to set up a simple spreadsheet to test for divisors until you find the first one to work.

Yeah, that's what I did, except, using a perl one-liner instead of a spreadsheet:

perl -e '$n=1000000; while($n > 0) { last unless $n%2584; $n-=4181; } print $n/2584, ",", (1000000-$n)/4181, "\n";'

Quote:downtownerOK, why did mine work?

I took 1,000,000 and divided it by the golden mean, 1.618033989. That gave me 618,033.9887. I then started with 1,000,000 and subtracted 618,034 (I rounded the previous non-integer). Continue subtracting and the last two numbers are 144 and 154. Should this have worked or was I lucky?

Come on people. You guys are much better than me at this stuff. Why did mine work???

What you said gave me this idea though:

We know that F(n) = floor(Phi^n/sqrt(5)) (where phi is the golden ratio).

So Phi^19/sqrt(5) * y + Phi^18/sqrt(5) = 1000000, which is equivalent to

x + phi*y = 387

Now, I am not sure where to go from here, but it seems that there might be some way to solve this analytically without resorting to brute force ...

Round 618,033.9887 to 618,034

1,000,000 - 618,034 = 381,966

618,034 - 381,966 = 236,068

381,966 - 236,068 = 145,898

236,068 - 145,898 = 90,170

.

.

.

The last two numbers (#19 & #20) are 144 & 154

Quote:downtownerThe last two numbers are 144 & 154

G=(1+sqrt(5))/2

So you started this table with Round( 1,000,000/G, 0) = 618,034 and then after that you just took differences until you got the correct answer. And you just had this idea completely out of the blue?

BTW it certainly does give you 144 and 154.

0 | 1,000,000 | |
---|---|---|

1 | 618,034 | 381,966 |

2 | 236,068 | 145,898 |

3 | 90,170 | 55,728 |

4 | 34,442 | 21,286 |

5 | 13,156 | 8,130 |

6 | 5,026 | 3,104 |

7 | 1,922 | 1,182 |

8 | 740 | 442 |

9 | 298 | 144 |

10 | 154 |

The method is not very stable. If you rounded off at the end, instead of the beginning you wouldn't get close.

Quote:cardsharkI used the Solver in Excel - took all of 30 seconds!

I would like you to elaborate. Usually a Solver depends on iteration and they don't work very well when you are truncating to the nearest integer.

I'll repeat what I said earlier. Figuring out if this should have worked or not may be a more difficult puzzle than the original one. Any one up for this challenge?