digitális matek

Chess and rice – but what a price!

Assume that you are offered a job for one year, you will be paid on a monthly basis, but you can choose how your salary will be calculated. You have two options.

Option one is that you receive 500,-BWP in the first month, 1000,- BWP  in the second, 1500,- BWP in the third — so you get 500,- BWP more in each successive month.

Option two is that you get 10,- BWP in the first month, and your salary will be doubled in each successive month: 20,- BWP in the second month, 40,- BWP in the third, and so on.

Geometric progression

Which option would you choose? In the first case, after the first three months you’ll have 3000,- BWP, but only 70,- BWP in the second case… Which one is the better?  You can get some hints from the following story.

Due to the famous legend about the origin of the chess an Indian guy went to the governor to present his newly discovered game by putting a chess board on the table. After explaining the rules the governor was so excited about this new game that he told the guy: „Name your reward!”.

The man said that he did not ask for too much: his expected reward was the total amount of rice grains when putting one grain on the first square of the chess board, two grains on the second, four on the third, and so on for all 64 squares on the board, doubling always the number of grains. The governor was just laughing at this very modest request — but he was shocked when, after a week, the treasurer reported him that the total amount of rice requested by the modest guy would be an astronomical sum, more than all rice will be produced in many, many centuries!

What is going on here? How can it happen that by simply doubling we arrive at enormously huge numbers in some steps? Going back to our introductory question, based on this story you probably draw the conclusion to ask for the second option when deciding how you should be payed. At least the second example strongly suggests that this is the best choice… Although we don’t know the reason why.

In fact, this is what we call  exponential growth. In the first case, when the salary in each month is 500 more than in the previous month we simply have a sequence of the monthly salaries, which is an arithmetic progression: we discussed it in our previous blog. The starting term a_1 of the progression is 500, and also the difference d is 500, hence our salary a_{12} in the 12th month, at the end of the year will be
a_{12}=a_1+(12-1)d=500+11\cdot 500=12\cdot 500=6000,-BWP. Our yearly earning is the sum of the monthly salaries, which is the sum of the monthly salaries.

We also discussed in our previous blog that the sum of the first 12 terms of the arithmetic progression is S_{12}=12\cdot (a_1+a_{12})/2=6\cdot 6500=39000,-BWP. This is a linear growth, which means that the growth is proportional to the time interval. If you set up a time-salary coordinate system, then you’ll see that the points which represent the monthly salaries are lying on a straight line.

What is the difference in the second case? In fact, we have a completely different progression: the monthly salaries form a so-called geometric progression. While in the arithmetic progression the difference of the consecutive terms is the same, in the geometric progression the  quotient remains unchanged: the ratio of a_2 and a_1 is the same as the ratio of a_3 and a_2, or a_4 and a_3, and so on. This quotient is usually denoted by q and together with the first term a_1 the whole progression is completely determined: every term can be calculated from the previous one simply by multiplying by q.

In our first example, the second way of being paid is related to a geometric progression: the first term is the first month salary, a_1=10, and the quotient is q=2. Hence the consecutive monthly salaries are a_1=10, a_2=q\cdot a_1=20, a_3=q\cdot a_2=q^2\cdot a_1=40, etc. We can easily figure out that after 12 steps the salary in the twelfth month is a_{12}=q^{11}\cdot a_1=2^{11}\cdot 10=2048\cdot 10=20480. The yearly total salary is the sum of these amounts:


So, this exponential growth is rather tricky: in the beginning the monthly salaries are small amounts, but after some steps it starts to increase, and the speed of increase is much greater than in the linear case. Can we imagine the „astronomical sum” the „modest” chess player required as award?

In that case we start with a_1=1 and the quotient is q=2 again. On the 64th square of the chessboard there will be a_{64}=q^{63}\cdot 1=2^{63} rice grains! Let’s try to estimate this number: we use the fact that 2^{10}=1024, so we take the approximate value 2^{10}\approx 1000=10^3, then


and 2^{63}\approx 10^{18}\cdot 2^3=8\cdot 10^{18}, which is a number starting with 8 and continues with 18 zeros! The weight of one rice grain is approximately 0.03 gram, that is 3\cdot 10^{-5} kg. Consequently, the total weight of the rice grains on the 64th square is about 3\cdot 8\cdot 10^{13} kg, that is about 2.4\cdot 10^{11} ton.

However, don’t forget: the chess award was the sum of all rice grains on the chess board…! How can we compute the sum of the terms in a geometric progression? In the case of arithmetic progressions we had a very nice formula for the corresponding sum, discovered by the young Gauss. Is there any way to sum up terms of the form

    \[S_n=a_1+q\cdot a_1+q^2\cdot a_1+\dots+q^{n-1}\cdot a_1,\]

which is the sum of the first n terms of the geometric progression with starting term a_1 and quotient q?

Well, a simple observation will help: let’s multiply the above sum by q to get

    \[q\cdot S_n=q\cdot a_1+q^2\cdot a_1+q^3\cdot a_1+\dots+q^{n-1}\cdot a_1+q^{n}\cdot a_1,\]

and we realize that these two sums have a lot of equal terms: in fact, if we form the difference q\cdot S_n-S_n, then several terms cancel and we arrive at

    \[(q-1) S_n=q\cdot S_n-S_n=q^{n}\cdot a_1-a_1=(q^{n}-1)\cdot a_1.\]

If the quotient q is different from 1, then we can divide by q-1 to get

    \[S_n=a_1\cdot \frac{q^{n}-1}{q-1},\]

a very nice formula. We note that in the case q=1 all terms in S_n are the same, hence S_n=n\cdot a_1.

Now let’s go back to the chessboard: we have to sum up the rice grains on each square from the first to the 64th, that is, we are interested in the sum

    \[S_{64}=1\cdot \frac{2^{64}-1}{2-1}=2^{64}-1.\]

This approximately the double of the above sum, so it is roughly 5\cdot 10^{11} ton. According to Wikipedia, this is about the total mass of the world’s human population! In fact, it is a bit more…

Hence the Indian guy was not just a good chess player, but probably he knew something about exponential growth. The legend did not say anything about his future whether he became the richest person of his time, or his life ended in some dark prison by a sorrow checkmate …for cheating the governor.

Are you ready to solve more problems about geometric progressions? Go to the updated sequences problem sheet.