Math Puzzle - from NYTimes

Threads: 7
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

CrystalMath

Threads: 8
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

Threads: 20
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

boymimbo

Threads: 17
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

Threads: 7
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

dwheatley

Threads: 25
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

Answer ^

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

Nareed

Threads: 373
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

Threads: 7
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

Threads: 649
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	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

weaselman

Threads: 20
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

Threads: 7
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

Threads: 649
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

EdCollins

Threads: 20
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

Threads: 20
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

cardshark

Threads: 9
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

Threads: 7
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

Threads: 20
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

Threads: 7
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

Threads: 649
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

Threads: 7
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

Threads: 649
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