Monday, September 29, 2014

"La variante di Lüneburg" and China's rice production

In 1993, Paolo Maurensig, an Italian writer from Gorizia, wrote a novel entitled "La variante di Lüneburg" (Adelphi, 1995, pp. 164, ISBN 88-459-0984-0). The novel is set in Nazi Germany during World War II and the main theme is the game of chess.

At the beginning of the story, Maurensig tells a legend according to which the game of chess was invented by a Chinese peasant with a formidable gift for mathematics. (There are different versions of this story, as far as I understand, the earliest written record is contained in the Shahnameh and takes place in India, instead.) The peasant asks the king, in exchange for the game he invented, for a quantity of rice equal to that obtained with the following procedure: First one grain of rice should be placed on the first square on the chess board, then two grains on the second square, than four on the third and so on, every time doubling the number of rice grains. The king accepts not realizing what he is agreeing on.

Let's try to calculate how much rice that would be. The series implied by the peasant has a more general form called geometric series and is well known in mathematics:
$$
  s_m = \sum_{k=0}^m x^k
$$
If we calculate the first steps in the sum we obtain:
\begin{eqnarray*}
  s_0 &=& 1 \\
  s_1 &=& 1+x \\
  s_2 &=& 1+x+x^2 \\
  \dots && \\
\end{eqnarray*}
To see how this relates to our problem, we can set $x=2$ and see that the sum will be: $1+ 2+ 4+ 8+ \dots $

If we observe $s_1$ and $s_2$ in the previous equations, we see that we can write the second in terms of the first in two different ways:
\begin{eqnarray*}
  s_2 &=& s_1+x^2 \\
  s_2 &=& 1 + x (1+x) = 1 + x s_1.\\
\end{eqnarray*}

In the first case, we grouped the first two terms in $s_2$, whereas in the second case we group the last two terms and realized that they shared a common factor $x$.

If we continue writing the terms of the sum for higher orders, we realize that what we obtained above is true in general:
\begin{eqnarray*}
  s_{m}   &=& 1+x+\dots+x^m \\
  s_{m+1} &=& 1+x+\dots+x^m+x^{m+1} = s_m+x^{m+1} \\
         &=& 1 + x (1+\dots+x^{m-1}+x^m) = 1 + x s_m, \\
\end{eqnarray*}
which also means that the right-hand side of the last two equations above must be equal:
\begin{eqnarray*}
  s_m+x^{m+1} &=& 1 + x s_m,
\end{eqnarray*}
and, therefore, rearranging:
\begin{eqnarray*}
  s_m &=& \frac{x^{m+1}-1}{x-1}.
\end{eqnarray*}
This is the general solution for the sum of the geometric series. If we want to know how many grains of rice the king will have to give to the peasant, we need to substitute the values of $x$ and $m$. We already saw above that $x$ should be equal to 2. We also know that the chess board has 8 rows and 8 columns, giving 64 squares. Because we start with $s_0$ in the first square, we need to calculate the series for $m=63$, that will correspond to the last square:
$$ s_{63} = \frac{2^{64}-1}{2-1} = 18\,446\,744\,073\,709\,551\,615, $$
which in words would sound something like eighteen quintillions...

In 1999, China produced approximately 198 million tons of rice. Which corresponds to $198\,000\,000\,000\,000$ grams. If we assume for simplicity that the production is constant over the years and that one gram of rice is approximately 50 grains, the king will have to give the peasant the entire rice production in China for more than 18 hundred years.

Needless to say, when the king realized the mistake, he killed the peasant.