5
$\begingroup$

THis is a question that I remember when I was in the 5th grade that tested our logical reasoning skills. And it is a simple choice knowing that the pennies doubling every day is an exponential function, but I'm trying to figure out how to create a formula for this solution without adding everything up by hand.

I know this has to be some form of a recurrence relation, but I cant figure out how to solve it. so far I have written down

$F(n) = 2F(n-1)$ which wolframalpha solves for me as $c_1 2^{n-1}$ (I don't know what the $c_1$ is, so I assume its a constant).

and then when I plug in

$\sum_{n = 1}^{30} 2^{n-1}$ it spits out $\$1,073,741,823$

Which is wrong because when I sum up all the days I get $10,737,418.23

I think the main problem is the recurrence relation I set up, but its been so long since my discrete math class, I've forgotten completely how to set that up.

$\endgroup$
  • 1
    $\begingroup$ You're really choosing to do this the longest way with the recurrence relation. $\endgroup$ – crf Mar 13 '13 at 5:41
  • $\begingroup$ I don't know what other way to do it besides just counting it out by hand. And I'm more interested in the formula I get at the end than the actual dollar amount. $\endgroup$ – OghmaOsiris Mar 13 '13 at 5:42
  • $\begingroup$ It depends on what your discount rate for money is (as well as what your utility function looks like as a function of money). See en.wikipedia.org/wiki/Exponential_discounting and en.wikipedia.org/wiki/Hyperbolic_discounting. $\endgroup$ – Qiaochu Yuan Mar 13 '13 at 8:18
  • 1
    $\begingroup$ Wolfram is giving you the right answer, but it's 1,073,741,823 cents, rather than 1,073,741,823 dollars (because the first day is one cent, rather than one dollar). After conversion to dollars, it agrees with your addition. $\endgroup$ – Philip C Mar 13 '13 at 10:17
3
$\begingroup$

Wolfram alpha is right, 1 penny is $0.01\$ $ so $c_1=0.01$. As it is a geometric series you could caluclate $c_1 2^{30}-1 $ directly.

$c_1$ is the value you get at the first day.

$\endgroup$
  • $\begingroup$ Gah! I didn't even look at the numbers I got... the first one I got (with constant of 1) was the same number as the second one (with constant of 0.01) with the decimal moved to the left twice... I feel so stupid now, lol. $\endgroup$ – OghmaOsiris Mar 13 '13 at 5:46
3
$\begingroup$

On day one, you receive $\$0.01\cdot 2^0$, on day two, $\$0.01\cdot 2$, and in general, on day $n$, $\$0.01\cdot 2^{n-1}$. Thus the total amount of money is $$ \sum_{n=1}^{30} 0.01\cdot 2^{n-1}=0.01\cdot\sum_{n=0}^{29} 2^{n}=0.01\cdot(2^{30}-1)=\$10,737,418.23. $$ If you haven't seen the identity used in the second equality, that might be worth verifying. So clearly we're better off waiting on the penny than taking the million dollars up front.

$\endgroup$
2
$\begingroup$

You can solve this problem without using Wolfram Alpha, recurrence relations, or anything complicated.

Consider the number of pennies you will get via each method.

A million dollars is 100,000,000 pennies (i.e. $10^8$).

How about a number of pennies which doubles each day? Well, imagine the number of pennies you get in binary. On day 1 you will get 1 (binary) penny. On day 2 you will get 10 (binary) (i.e. 3 pennies), on day three 100 pennies etc., until the 30th day where you will get 100...000 pennies, i.e. 1 with 29 zeroes - each day (numbered $d$) you are gaining a number of pennies being in binary 1 with $d-1$ zeroes.

Now imagine adding them up:

               1
            + 10
           + 100
             ...
+ 10000000...000 (1 with 29 zeroes)
----------------
= 11111111...111 (30 ones)

Now clearly, 11111...11 (30 ones) + 1 will be 1 followed by 30 zeroes, i.e. $2^{30}$. So the number of pennies will be $2^{30}-1$. No arithmetic needed so far.

Now, is this greater or lesser than $10^8$ (what you would have received had you received a million dollars)? Let's do an order of magnitude comparison. It's well known that $2^{10}$ is $1024$ (hence a kilobyte is about a thousand bytes etc.), and $1024$ is roughly $10^3$. So $2^{30}-1$ is roughly $10^{30/10*3}$ i.e. $10^9$. So, roughly speaking you'll be ten times better off taking an amount of pennies that doubles each day.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.