Misplaced Pages

Wheat and chessboard problem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Second Half of the Chessboard) Mathematical problem
By the time that the fifth square is reached on the chessboard, the board contains a total of 31, or 2 5 − 1 {\textstyle 2^{5}-1} , grains of wheat.

The wheat and chessboard problem (sometimes expressed in terms of rice grains) is a mathematical problem expressed in textual form as:

If a chessboard were to have wheat placed upon each square such that one grain were placed on the first square, two on the second, four on the third, and so on (doubling the number of grains on each subsequent square), how many grains of wheat would be on the chessboard at the finish?

The problem may be solved using simple addition. With 64 squares on a chessboard, if the number of grains doubles on successive squares, then the sum of grains on all 64 squares is: 1 + 2 + 4 + 8 + ... and so forth for the 64 squares. The total number of grains can be shown to be 2−1 or 18,446,744,073,709,551,615 (eighteen quintillion, four hundred forty-six quadrillion, seven hundred forty-four trillion, seventy-three billion, seven hundred nine million, five hundred fifty-one thousand, six hundred and fifteen, over 1.4 trillion metric tons), which is over 2,000 times the annual world production of wheat.

This exercise can be used to demonstrate how quickly exponential sequences grow, as well as to introduce exponents, zero power, capital-sigma notation, and geometric series. Updated for modern times using pennies and a hypothetical question such as "Would you rather have a million dollars or a penny on day one, doubled every day until day 30?", the formula has been used to explain compound interest. (Doubling would yield over one billion seventy three million pennies, or over 10 million dollars: 2−1=1,073,741,823).

Origins

The problem appears in different stories about the invention of chess. One of them includes the geometric progression problem. The story is first known to have been recorded in 1256 by Ibn Khallikan. Another version has the inventor of chess (in some tellings Sessa, an ancient Indian Minister) request his ruler give him wheat according to the wheat and chessboard problem. The ruler laughs it off as a meager prize for a brilliant invention, only to have court treasurers report the unexpectedly huge number of wheat grains would outstrip the ruler's resources. Versions differ as to whether the inventor becomes a high-ranking advisor or is executed.

Macdonnell also investigates the earlier development of the theme.

, shatranj, or chess was invented under an Indian king, who expressed his preference for this game over backgammon. The Indians, he adds, also calculated an arithmetical progression with the squares of the chessboard. The early fondness of the Indians for enormous calculations is well known to students of their mathematics, and is exemplified in the writings of the great astronomer Āryabaṭha (born 476 A.D.). An additional argument for the Indian origin of this calculation is supplied by the Arabic name for the square of the chessboard, (بيت, "beit"), 'house'. For this has doubtless a historical connection with its Indian designation koṣṭhāgāra, 'store-house', 'granary' .

Solutions

The sum of powers of two from zero up to a given positive integer power is 1 less than the next power of two (i.e. the next Mersenne number)

The simple, brute-force solution is just to manually double and add each step of the series:

T 64 {\displaystyle T_{64}} = 1 + 2 + 4 + ..... + 9,223,372,036,854,775,808 = 18,446,744,073,709,551,615
where T 64 {\displaystyle T_{64}} is the total number of grains.

The series may be expressed using exponents:

T 64 = 2 0 + 2 1 + 2 2 + ⋯ + 2 63 {\displaystyle T_{64}=2^{0}+2^{1}+2^{2}+\cdots +2^{63}}

and, represented with capital-sigma notation as:

∑ k = 0 63 2 k . {\displaystyle \sum _{k=0}^{63}2^{k}.\,}

It can also be solved much more easily using:

T 64 = 2 64 − 1. {\displaystyle T_{64}=2^{64}-1.\,}

A proof of which is:

s = 2 0 + 2 1 + 2 2 + ⋯ + 2 63 . {\displaystyle s=2^{0}+2^{1}+2^{2}+\cdots +2^{63}.}

Multiply each side by 2:

2 s = 2 1 + 2 2 + 2 3 + ⋯ + 2 63 + 2 64 . {\displaystyle 2s=2^{1}+2^{2}+2^{3}+\cdots +2^{63}+2^{64}.}

Subtract original series from each side:

2 s − s = 2 1 + 2 2 + ⋯ + 2 63 + 2 64 − 2 0 − 2 1 − 2 2 − ⋯ − 2 63 = 2 64 − 2 0 ∴ s = 2 64 − 1. {\displaystyle {\begin{aligned}2s-s&=\qquad \quad {\cancel {2^{1}}}+{\cancel {2^{2}}}+\cdots +{\cancel {2^{63}}}+2^{64}\\&\quad -2^{0}-{\cancel {2^{1}}}-{\cancel {2^{2}}}-\cdots -{\cancel {2^{63}}}\\&=2^{64}-2^{0}\\\therefore s&=2^{64}-1.\end{aligned}}}

The solution above is a particular case of the sum of a geometric series, given by

a + a r + a r 2 + a r 3 + ⋯ + a r n − 1 = ∑ k = 0 n − 1 a r k = a 1 − r n 1 − r , {\displaystyle a+ar+ar^{2}+ar^{3}+\cdots +ar^{n-1}=\sum _{k=0}^{n-1}ar^{k}=a\,{\frac {1-r^{n}}{1-r}},}

where a {\displaystyle a} is the first term of the series, r {\displaystyle r} is the common ratio and n {\displaystyle n} is the number of terms.

In this problem a = 1 {\displaystyle a=1} , r = 2 {\displaystyle r=2} and n = 64 {\displaystyle n=64} .

Thus,

∑ k = 0 n − 1 2 k = 2 0 + 2 1 + 2 2 + ⋯ + 2 n − 1 = 2 n − 1 {\displaystyle {\begin{aligned}\sum _{k=0}^{n-1}2^{k}&=2^{0}+2^{1}+2^{2}+\cdots +2^{n-1}\\&=2^{n}-1\end{aligned}}}

for n {\displaystyle n} being any positive integer.


The exercise of working through this problem may be used to explain and demonstrate exponents and the quick growth of exponential and geometric sequences. It can also be used to illustrate sigma notation. When expressed as exponents, the geometric series is: 2 + 2 + 2  + 2 + ... and so forth, up to 2. The base of each exponentiation, "2", expresses the doubling at each square, while the exponents represent the position of each square (0 for the first square, 1 for the second, and so on.).

The number of grains is the 64th Mersenne number.

Second half of the chessboard

A chessboard with each square labeled with the number of wheat grains according to the problem. A red line divides the chessboard in half.
An illustration of Ray Kurzweil's second half of the chessboard principle. The letters are abbreviations for the SI metric prefixes.

In technology strategy, the "second half of the chessboard" is a phrase, coined by Ray Kurzweil, in reference to the point where an exponentially growing factor begins to have a significant economic impact on an organization's overall business strategy. While the number of grains on the first half of the chessboard is large, the amount on the second half is vastly (2 > 4 billion times) larger.

The number of grains of wheat on the first half of the chessboard is 1 + 2 + 4 + 8 + ... + 2,147,483,648, for a total of 4,294,967,295 (2 − 1) grains, or about 279 tonnes of wheat (assuming 65 mg as the mass of one grain of wheat).

The number of grains of wheat on the second half of the chessboard is 2 + 2 + 2 + ... + 2, for a total of 2 − 2 grains. This is equal to the square of the number of grains on the first half of the board, plus itself. The first square of the second half alone contains one more grain than the entire first half. On the 64th square of the chessboard alone, there would be 2 = 9,223,372,036,854,775,808 grains, more than two billion times as many as on the first half of the chessboard.

On the entire chessboard there would be 2 − 1 = 18,446,744,073,709,551,615 grains of wheat, weighing about 1,199,000,000,000 metric tons. This is over 1,600 times the global production of wheat (729 million metric tons in 2014 and 780.8 million tonnes in 2019).

Use

Carl Sagan titled the second chapter of his final book "The Persian Chessboard" and wrote, referring to bacteria, that "Exponentials can't go on forever, because they will gobble up everything." Similarly, The Limits to Growth uses the story to present suggested consequences of exponential growth: "Exponential growth never can go on very long in a finite space with finite resources."

See also

References

  1. In the period 2020–21 this was an estimated 772.64 million metric tonnes, "Global Wheat Production Statistics since 1990". Retrieved 2022-05-25.
  2. "A Penny Doubled Every Day for 30 Days = $10.7M" – via www.bloomberg.com.
  3. "Doubling Pennies". Mathforum.org. Retrieved 2017-08-09.
  4. Clifford A. Pickover (2009), The Math Book: From Pythagoras to the 57th Dimension, New York : Sterling. ISBN 9781402757969. p. 102
  5. Tahan, Malba (1993). The Man Who Counted: A Collection of Mathematical Adventures. New York: W.W. Norton & Co. pp. 113–115. ISBN 0393309347. Retrieved 2015-04-05.
  6. Macdonell, A. A. (1898). "The Origin and Early History of Chess". Journal of the Royal Asiatic Society of Great Britain & Ireland. 30 (1): 117–141. doi:10.1017/S0035869X00146246. S2CID 163963500.
  7. Kurzweil, Ray (1999). The Age of Spiritual Machines: When Computers Exceed Human Intelligence. New York: Penguin. p. 37. ISBN 0-670-88217-8. Retrieved 2015-04-06.
  8. "Encyclopedia Britannica: Grain, unit of weight". 29 April 2004. Retrieved 2 March 2017.
  9. "FAOSTAT". faostat3.fao.org. Archived from the original on 11 January 2019. Retrieved 2 March 2017.
  10. Sagan, Carl (1997). Billions and Billions: Thoughts On Life And Death At the Brink Of The Millennium. New York: Ballantine Books. p. 17. ISBN 0-345-37918-7.
  11. Meadows, Donella H., Dennis L. Meadows, Jørgen Randers, and William W. Behrens III (1972). The Limits to Growth, p. 21, at Google Books. New York: University Books. ISBN 0-87663-165-0. Retrieved 2015-04-05.

External links

Categories: