Wheat and chessboard problem

From Wikipedia, the free encyclopedia

The wheat and chessboard problem is a mathematical problem with the following idea: Say that you have a chessboard in front of you. If you were to place a grain of wheat on the first square, two on the second, four on the third, eight on the fourth and so on, each time doubling the amount of grains, how many grains of wheat would you need to cover the entire board?

Chessboard

To solve this, you must observe that a chess board is an 8x8 square, containing 64 cells. If you are to double the amount each time, then add them you get the series:

$T_{64} = 1 + 2 + 4 + \cdots + 2^{63} = \sum_{i=0}^{63} 2^i = 2^{64} - 1$

which equals 18,446,744,073,709,551,615.

This problem (or a variation of it) is usually shown to math students to demonstrate the quick growth of exponential sequences.

1 Origin of the problem
2 Variations
3 Second Half of the Chessboard
4 See also
5 External links
6 References

[edit] Origin of the problem

While the story behind the problem changes from person to person, the fable usually follows the same idea:

When the creator of the game of chess (in some tellings, an ancient Indian mathematician, in others, a legendary brahmin named Sessa or Sissa) showed his invention to the ruler of the country, the ruler was so pleased that he gave the inventor the right to name his prize for the invention. The man, who was very wise, asked the king this: that for the first square of the chess board, he would receive one grain of wheat (in some tellings, rice), two for the second one, four on the third one and so forth, doubling the amount each time. The ruler, who was not strong in math, quickly accepted the inventor's offer, even getting offended by his perceived notion that the inventor was asking for such a low price, and ordered the treasurer to count and hand over the wheat to the inventor. However, when the treasurer took more than a week to calculate the amount of wheat, the ruler asked him for a reason for his tardiness. The treasurer then gave him the result of the calculation, and explained that it would be impossible to give the inventor the reward. The ruler then, to get back at the inventor who tried to outsmart him, told the inventor that in order for him to receive his reward, he was to count every single grain that was given to him, in order to make sure that the ruler was not stealing from him.

The amount of wheat is approximately 80 times what would be produced in one harvest, at modern yields, if all of Earth's arable land could be devoted to wheat. The total of grains is approximately 0.0031% of the number of atoms in 12 grams of carbon-12 and probably more than 200,000 times the estimated number of neuronal connections in the human brain (see large numbers).

[edit] Variations

The problem also takes another setting, this time the Roman empire. When a brave general came back to Rome, the Caesar asked him to name a price for the services he had offered to his country. When the general asked for an exorbitant price, the Caesar, not wanting to sound cheap, or that he was going to go back on his word, made him an offer; the next day, the general was to go to the treasury, and grab a one gram gold coin, the next day, a two gram gold coin, and each day, the weight of the coin would double, and the general could take it, as long as he was able to carry it by himself. The general, seeing a good opportunity to make money quickly, agreed. However, by the end of the 18th day, the general was not able to carry any more coins. The general only received a small fraction of what he had asked the Caesar.

Another version places two merchants together. One merchant offers the other a deal; that for the next month, the merchant was going to give $10,000 to the other one, and in return, he would receive 1 cent the first day, 2 cents the second, 4 cents in the third, and so on, each time doubling the amount. The second merchant agreed, and for the first three weeks, he enjoyed the fortunes that the first merchant was "unwittingly" giving him, but by the end of the month, the second merchant was broke, while the first merchant was incredibly rich.

[edit] Second Half of the Chessboard

An illustration of the principle.

In technology strategy, the Second Half of the Chessboard is a phrase, coined by Ray Kurzweil^[1], in reference to the point where an exponentially growing factor begins to have a significant economic impact on an organization's overall business strategy.

It turns out that while the amount of rice on the first half of the chessboard is very large but economically viable for the emperor of India to provide, the amount on the second half is so vastly larger that it would be impossible for any emperor, or even the entire world, to provide it.

Specifically, the total number of grains of rice on the first half of the chessboard is 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 ... + 2,147,483,648, for a total of exactly 2³² − 1 = 4,294,967,295 grains of rice, or about 100,000 kg of rice, with the mass of one grain of rice being roughly 25 mg[2]. This total amount is about 1/1,200^th of total rice production in India per annum (in 2005) [3].

The total number of grains of rice on the second half of the chessboard is 2³² + 2³³ + 2³⁴ ... + 2⁶³, for a total of 2⁶⁴ − 2³² grains of rice. On the 64th square of the chessboard alone there would be exactly 2⁶³ = 9,223,372,036,854,775,808 grains of rice, or more than a billion times as much on the entire first half of the chessboard.

In total, on the entire chessboard there would be exactly 2⁶⁴ − 1 = 18,446,744,073,709,551,615 grains of rice.