dwheatley
• Posts: 1246
Joined: Nov 16, 2009
January 4th, 2012 at 6:29:10 PM permalink
A millionaire opened a bank account by depositing an integral number of dollars. His second deposit was also an integral number of dollars. Thereafter, each deposit was the sum of the previous two deposits. His 20th deposit was exactly one million dollars. What were his first two deposits?

Note that interest doesn't matter.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
downtowner
• Posts: 45
Joined: Dec 7, 2011
January 4th, 2012 at 7:15:56 PM permalink
I got it by calculation to get close and then trial and error in Excel. There may be more than one answer. Mine is somewhat non-intuitive.
CrystalMath
• Posts: 1911
Joined: May 10, 2011
January 4th, 2012 at 7:51:12 PM permalink
I got an answer also. I just tried all possible positive deposit amounts for the first deposit and calculated the necessary second deposit. Only one answer yields integers.
I heart Crystal Math.
weaselman
• Posts: 2349
Joined: Jul 11, 2010
January 4th, 2012 at 8:09:03 PM permalink
2584D1 + 4181D2 = 1000,000

There is one integral solution for D1 and D2.
"When two people always agree one of them is unnecessary"
boymimbo
• Posts: 5994
Joined: Nov 12, 2009
January 4th, 2012 at 8:28:12 PM permalink
Let Dn be the nth deposit.

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.
----- You want the truth! You can't handle the truth!
downtowner
• Posts: 45
Joined: Dec 7, 2011
January 4th, 2012 at 8:51:12 PM permalink
I used ratio analysis based on the golden mean and then played around with the non-integer results until I found the answer. All told it took about thirty minutes. I figured there had to be multiple answers if I could find it that easily. I must be lucky. Oh boy, I can't wait to take this luck to Las Veags next week.

Do you have the answer? Can I PM you with my two numbers and see if I am correct?
dwheatley
• Posts: 1246
Joined: Nov 16, 2009
January 5th, 2012 at 6:12:14 AM permalink
The analytic way to finish this off is to use the extended Euclidean Algorithm to solve the linear Diophantine equation some of the other posters have found. You get the general solution, for which only one pair of integer solutions are both positive.

154 and 144

There is also a shortcut that uses the fact that the two coefficients are in the Fibonacci sequence.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
Nareed
• Posts: 11413
Joined: Nov 11, 2009
January 5th, 2012 at 6:28:21 AM permalink
Isn't 42 the answer to everything? :P
Donald Trump is a fucking criminal
downtowner
• Posts: 45
Joined: Dec 7, 2011
January 5th, 2012 at 7:07:57 AM permalink
I divided 1,000,000 by the golden mean. Then continued to divide each answer by the same. the last two results were 173 and 107. That wasn't correct. So then I took the integer of the first first result [ int(1000000/1.618034) ] and started subtracting using that number. The result was two numbers. They didn't work either. But when I reversed them in order of bank deposit they did work. And they are the correct two numbers. Why did this work? Was it luck. The chances are pretty slim that it could be luck. Understanding why this worked may be a bigger challenge for someone than the original puzzle.
pacomartin
• Posts: 7895
Joined: Jan 14, 2010
January 5th, 2012 at 9:24:00 AM permalink
Quote: dwheatley

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

 0 11 22 0 89 17,711 1 144 28,657 1 233 46,368 2 377 75,025 3 610 121,393 5 987 196,418 8 1,597 317,811 13 2,584 514,229 21 4,181 832,040 34 6,765 1,346,269 55 10,946 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
weaselman
• Posts: 2349
Joined: Jul 11, 2010
January 5th, 2012 at 9:33:24 AM permalink
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.
"When two people always agree one of them is unnecessary"
downtowner
• Posts: 45
Joined: Dec 7, 2011
January 5th, 2012 at 10:10:36 AM permalink
OK, 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?
pacomartin
• Posts: 7895
Joined: Jan 14, 2010
January 5th, 2012 at 11:00:08 AM permalink
Quote: weaselman

Is 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.
EdCollins
• Posts: 1739
Joined: Oct 21, 2011
January 5th, 2012 at 11:51:19 AM permalink
Fyi: I solved this in just a minute or two, which is all the time it took me to write a quick & dirty BASIC program to "brute force" the answer. (Not as elegant as figuring it out on my own, I know, but "time is money" and this was certainly the fastest way for me to solve it.)

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
weaselman
• Posts: 2349
Joined: Jul 11, 2010
January 5th, 2012 at 11:59:50 AM permalink
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";'`
"When two people always agree one of them is unnecessary"
cardshark
• Posts: 239
Joined: Nov 30, 2009
January 5th, 2012 at 12:08:10 PM permalink
I used the Solver in Excel - took all of 30 seconds!
downtowner
• Posts: 45
Joined: Dec 7, 2011
January 5th, 2012 at 12:10:57 PM permalink
Quote: downtowner

OK, 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???
weaselman
• Posts: 2349
Joined: Jul 11, 2010
January 5th, 2012 at 1:10:46 PM permalink
I am not sure what you mean by "continue subtracting". "Continue subtracting" what from what.
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 ...
"When two people always agree one of them is unnecessary"
downtowner
• Posts: 45
Joined: Dec 7, 2011
January 5th, 2012 at 1:47:01 PM permalink
1,000,000 / 1.618033989 = 618,033.9887

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
pacomartin
• Posts: 7895
Joined: Jan 14, 2010
January 5th, 2012 at 3:58:46 PM permalink
Quote: downtowner

The 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.
downtowner
• Posts: 45
Joined: Dec 7, 2011
January 5th, 2012 at 4:43:15 PM permalink
It wasn't random. The average ratio between consecutive Fibonachi numbers is the golden ratio or mean. So I figured that the ratio between 1,000,000 and the next number down should be about there. I figured I would start there and subtract down and then try a few numbers around there to find the answer. It worked better than I thought. It sounds like it worked better than it should have from what you say.
pacomartin
• Posts: 7895
Joined: Jan 14, 2010
January 5th, 2012 at 5:42:35 PM permalink
Quote: cardshark

I 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.
downtowner