Wheat and chessboard problem

The wheat and chessboard problem is usually described as placing grain of wheat (or rice) in an 8 x 8 chessboard that is like the following.

A chessboard with 64 squares

However, a more colorful description of the problem is:

Sessa, an ancient Indian minister, had made a brilliant invention. So the ruler wanted to give him a prize. He could have anything he wished, the ruler said. Sessa requested that one grain of wheat be put in the first square of an 8 by 8 chessboard. Two grains of wheat in the second square. Four grains of wheat in the third square and so on. In general, the number of grains of wheat in one square is always the double of the previous square. The ruler laughed it off as an insignificant prize for Sessa’s achievement and the ruler granted his wish. Later the court treasurers reported that the entire grain reserve of the kingdom was not sufficient to fulfill the request! Basically Sessa was asking for the ruler’s kingdom and more!

The problem appears intuitively simple. There are only 64 squares on the chessboard. Surely the ruler of a kingdom would be able to fill the 64 squares with grains in the manner that was requested. Upon closer examination, the growth in grains of wheat is actually phenomenal. The total number of grains needed would be

1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 + … (all the way to the 64th term)

which turns out to be 18,446,744,073,709,551,615. This would be over 18 Quintillion grains of wheat! Or over 18 million times 1 trillion grains of wheat! This story with the Indian minister Sessa is an excellent illustration of exponential grow.

When something is growing according to a multiplicative constant (e.g. doubling, tripling) at each step, the quantity can get to be out of control pretty fast. For example, when bacteria count doubles in every minute, the population would be 18 quintillion in just one hour. Note that each term in the above sum is a power of 2.

2^0+2^1+2^1+2^3+2^4+\cdots+2^{63}

In the wheat and chessboard problem, the base of the exponentiation is 2, hence the doubling in each step. If something is growing in a linear fashion, the increase in each step is an addition of a constant and not the multiplying of a constant. Say, you put one grain of wheat in the first square, 101 grains of wheat in the second square, 201 grains of wheat in the third square and so on. Each square would have 100 more grains than the previous square. Then it would be easy for the ruler to fulfill this request.

1 + 101 + 201 + 301 + … + 6301 = 201,664

The number 201,664 is surely doable. For example, assuming that the population of the kingdom is 200,000, if everyone in the kingdom skips one meal, there would be more than enough grains of wheat to fulfill this request. This is actually a cruel way to treat the citizens. But it is just an illustration that 201,664 is a tractable problem.

The number 201,664 surely is a far cry from 18 qunintillion! So exponential growth can dwarf linear growth, depending on the multiplier, by as much as a factor of 18 quintillion. The exponential growth in the wheat and chessboard problem is also illustrated in the game called Tower of Hanoi. The following shows a game set.

8-disk Tower of Hanoi (Wikipedia)

The exponential story is discussed in this blog post in a companion blog.

\copyright 2017 – Dan Ma

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s