Wheat and chessboard problem

Last updated December 18, 2024

The wheat and chessboard problem (sometimes expressed in terms of rice grains) 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 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.^[1]

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).^[2]^[3]

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.^[4] 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.^[5]

Macdonnell also investigates the earlier development of the theme.^[6]

[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}

= 1 + 2 + 4 + ..... + 9,223,372,036,854,775,808 = 18,446,744,073,709,551,615

where

T_{64}

is the total number of grains.

The series may be expressed using exponents:

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

and, represented with capital-sigma notation as:

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

It can also be solved much more easily using:

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

A proof of which is:

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

Multiply each side by 2:

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

Subtract original series from each side:

{\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+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$ is the first term of the series, $r$ is the common ratio and $n$ is the number of terms.

In this problem $a=1$ , $r=2$ and $n=64$ .

Thus,

{\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$ 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

In technology strategy, the "second half of the chessboard" is a phrase, coined by Ray Kurzweil,^[7] 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).^[8]

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).^[9]

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."^[10] 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."^[11]

Related Research Articles

In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, the power ⁠ $⁠$ expands into a polynomial with terms of the form ⁠ $⁠$ , where the exponents ⁠ $⁠$ and ⁠ $⁠$ are nonnegative integers satisfying ⁠ $⁠$ and the coefficient ⁠ $⁠$ of each term is a specific positive integer depending on ⁠ $⁠$ and ⁠ $⁠$ . For example, for ⁠ $⁠$ ,

The number $e$ is a mathematical constant approximately equal to 2.71828 that is the base of the natural logarithm and exponential function. It is sometimes called Euler's number, after the Swiss mathematician Leonhard Euler, though this can invite confusion with Euler numbers, or with Euler's constant, a different constant typically denoted $. Alternatively, e can be called Napier's constant after John Napier. The Swiss mathematician Jacob Bernoulli discovered the constant while studying compound interest.$

<span class="mw-page-title-main">Exponential function</span> Mathematical function, denoted exp(x) or e^x

In mathematics, the exponential function is the unique real function which maps zero to one and has a derivative equal to its value. The exponential of a variable ⁠ $⁠$ is denoted ⁠ $⁠$ or ⁠ $⁠$ , with the two notations used interchangeably. It is called exponential because its argument can be seen as an exponent to which a constant number $e \approx 2.718$ , the base, is raised. There are several other definitions of the exponential function, which are all equivalent although being of very different nature.

In mathematics, the factorial of a non-negative integer $,$ denoted by $,$ is the product of all positive integers less than or equal to $.$ The factorial of also equals the product of $with the next smaller factorial: For example, The value of 0! is 1, according to the convention for an empty product.$

In mathematics, a geometric series is a series summing the terms of an infinite geometric sequence, in which the ratio of consecutive terms is constant. For example, the series is a geometric series with common ratio ⁠ $⁠$ , which converges to the sum of ⁠ $⁠$ . Each term in a geometric series is the geometric mean of the term before it and the term after it, in the same way that each term of an arithmetic series is the arithmetic mean of its neighbors.

In mathematics, the geometric mean is a mean or average which indicates a central tendency of a finite collection of positive real numbers by using the product of their values. The geometric mean of ⁠ $⁠$ numbers is the $n$ th root of their product, i.e., for a collection of numbers $a 1, a 2, ..., a n$ , the geometric mean is defined as

In mathematics, the logarithm to base $b$ is the inverse function of exponentiation with base $b$ . That means that the logarithm of a number $x$ to the base $b$ is the exponent to which $b$ must be raised to produce $x$ . For example, since $1000 = 10 3$ , the logarithm base $of 1000 is 3, or log 10 (1000) = 3 . The logarithm of x to base b is denoted as log b (x), or without parentheses, log b x . When the base is clear from the context or is irrelevant it is sometimes written log x .$

<span class="mw-page-title-main">Exponentiation</span> Arithmetic operation

In mathematics, exponentiation is an operation involving two numbers: the base and the exponent or power. Exponentiation is written as $b n$ , where $b$ is the base and $n$ is the power; often said as " $b$ to the power $n$ ". When $n$ is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, $b n$ is the product of multiplying $n$ bases: $In particular, .$

<span class="mw-page-title-main">Exponential growth</span> Growth of quantities at rate proportional to the current amount

Exponential growth occurs when a quantity grows at a rate directly proportional to its present size. For example, when it is 3 times as big as it is now, it will be growing 3 times as fast as it is now.

The square root of 2 is the positive real number that, when multiplied by itself or squared, equals the number 2. It may be written in mathematics as $or . It is an algebraic number, and therefore not a transcendental number. Technically, it should be called the principal square root of 2, to distinguish it from the negative number with the same property.$

A power of two is a number of the form $2 n$ where $n$ is an integer, that is, the result of exponentiation with number two as the base and integer $n$ as the exponent.

<span class="mw-page-title-main">Tetration</span> Arithmetic operation

In mathematics, tetration is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though Knuth's up arrow notation $and the left-exponent x b are common.$

In the mathematical subject of geometric group theory, the growth rate of a group with respect to a symmetric generating set describes how fast a group grows. Every element in the group can be written as a product of generators, and the growth rate counts the number of elements that can be written as a product of length n.

Population dynamics is the type of mathematics used to model and study the size and age composition of populations as dynamical systems.

In mathematical logic, Skolem arithmetic is the first-order theory of the natural numbers with multiplication, named in honor of Thoralf Skolem. The signature of Skolem arithmetic contains only the multiplication operation and equality, omitting the addition operation entirely.

The doubling time is the time it takes for a population to double in size/value. It is applied to population growth, inflation, resource extraction, consumption of goods, compound interest, the volume of malignant tumours, and many other things that tend to grow over time. When the relative growth rate is constant, the quantity undergoes exponential growth and has a constant doubling time or period, which can be calculated directly from the growth rate.

A double exponential function is a constant raised to the power of an exponential function. The general formula is $(where a >1 and b >1), which grows much more quickly than an exponential function. For example, if a = b = 10:$

In combinatorial mathematics, a rook polynomial is a generating polynomial of the number of ways to place non-attacking rooks on a board that looks like a checkerboard; that is, no two rooks may be in the same row or column. The board is any subset of the squares of a rectangular board with m rows and n columns; we think of it as the squares in which one is allowed to put a rook. The board is the ordinary chessboard if all squares are allowed and m = n = 8 and a chessboard of any size if all squares are allowed and m = n. The coefficient of x^k in the rook polynomial R_B(x) is the number of ways k rooks, none of which attacks another, can be arranged in the squares of B. The rooks are arranged in such a way that there is no pair of rooks in the same row or column. In this sense, an arrangement is the positioning of rooks on a static, immovable board; the arrangement will not be different if the board is rotated or reflected while keeping the squares stationary. The polynomial also remains the same if rows are interchanged or columns are interchanged.

A geometric progression, also known as a geometric sequence, is a mathematical sequence of non-zero numbers where each term after the first is found by multiplying the previous one by a fixed number called the common ratio. For example, the sequence 2, 6, 18, 54, ... is a geometric progression with a common ratio of 3. Similarly 10, 5, 2.5, 1.25, ... is a geometric sequence with a common ratio of 1/2.

A mathematical constant is a number whose value is fixed by an unambiguous definition, often referred to by a special symbol, or by mathematicians' names to facilitate using it across multiple mathematical problems. Constants arise in many areas of mathematics, with constants such as $e$ and $π$ occurring in such diverse contexts as geometry, number theory, statistics, and calculus.

References

↑ In the period 2020–21 this was an estimated 772.64 million metric tonnes, "Global Wheat Production Statistics since 1990" . Retrieved 2022-05-25.
↑ "A Penny Doubled Every Day for 30 Days = $10.7M" – via www.bloomberg.com.
↑ "Doubling Pennies". Mathforum.org. Retrieved 2017-08-09.
↑ Clifford A. Pickover (2009), The Math Book: From Pythagoras to the 57th Dimension, New York : Sterling. ISBN 9781402757969. p. 102
↑ 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.
↑ 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.
↑ 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.
↑ "Encyclopedia Britannica: Grain, unit of weight". 29 April 2004. Retrieved 2 March 2017.
↑ "FAOSTAT". faostat3.fao.org. Archived from the original on 11 January 2019. Retrieved 2 March 2017.
↑ 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.
↑ 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

Weisstein, Eric W. "Wheat and Chessboard Problem". MathWorld .
Salt and chessboard problem - A variation on the wheat and chessboard problem with measurements of each square.
Learning materials related to Math Adventures/Wheat and the Chessboard at Wikiversity

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]