The wheat and chessboard problem is a mathematical problem expressed in textual form as: 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 equals 18,446,744,073,709,551,615 —about 2,000 times annual world production—much more than most expect. 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.
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 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.
Solutions
The simple, brute-force solution is just to manually double and add each step of the series: The series may be expressed using exponents: and, represented with capital-sigma notation as: It can also be solved much more easily using: A proof of which is: Multiply each side by 2: Subtract original series from each side: The solution above is a particular case of the sum of a geometric series, given by where is the first term of the series, is the common ratio and is the number of terms. In this problem , and. 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: 20 + 21 + 22 + 23 + ... and so forth, up to 263. The base of each exponentiation, "2", expresses the doubling at each square, while the exponents represent the position of each square. The number of grains is the 64th Mersenne number.
Second half of the chessboard
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 larger. The number of grains of wheat on the first half of the chessboard is, for a total of 4,294,967,295 grains, or about 279 tonnes of wheat. The number of grains of wheat on the second half of the chessboard is, for a total of 264 − 232 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 263 = 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 264 − 1 = 18,446,744,073,709,551,615 grains of wheat, weighing about 1,199,000,000,000 metric tons. This is about 1,645 times the global production of wheat.
Use
titled the second chapter of his final bookThe Persian Chessboard and wrote that when referring to bacteria, "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."
