The wheat and chessboard problem (sometimes expressed as the rice and chessboard problem) 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 calculation. 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 264 − 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). 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 536 million pennies, or over 5 million dollars: 229 = 536,870,912.)
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.
[According to al-Masudi's early history of India], 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 [sic] (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 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:
… excerpt ends here. Continue reading the full article.
