Posted 2011-08-23 22:00:00 GMT

There is an old story that a munificent king demanded to bounteously
reward a sage: the sage requested that the king give him one grain for
the first square of the chess board, two grains for the second, four
grains for the fourth, and so on doubling the amount each
square. There being 64 squares on the chessboard the munificence of
the monarch was exceeded and he beheaded the sage. Here is an even more
dangerous mechanism which involves only six squares (piles) but vastly more
than 2^{64} profit.

Starting with an ordered set of n piles of grains, you can perform one
of two moves: double a grain by removing one from a pile and adding
two to the pile on the right of it, or shuffle by removing a grain and
then swapping the positions of the two piles immediately on the
right. The objective is to create as many grains as possible. Piles
cannot be created, so the doubling move cannot be used on the
rightmost pile, and the shuffling move cannot be used on the rightmost
or the one just to the left of that. Given six piles each with a
single grain, can you create exactly
2010^{20102010} grains?

This is IMO 2010 problem 5. It seems there are solutions all over the web now including at that polymath link; however, I'm not sure that they convey the glorious magnificence of the system.

Now suppose we define a function f(n, b, e) as the maximum number of grains that one can obtain with n piles, the leftmost containing b grains and the rightmost e grains, and all the rest empty. Surprisingly, this function grows very quickly in n, rather in the manner of Knuth's arrow operator.

Now f(1,h,h) = h, f(2, b, e) = 2b + e. The first indication of fun
comes with f(3, b, e) ≥ 2^{b}e or 2^{b+1}—
with three piles, double all the grains in the middle pile into the
right pile, then use the left pile to swap this pile back into the
middle and double it again.

The real heart is that the swapping rule effectively allows a reapplication of the function f(n-1, ...) to its previous value. This can be extended to n > 3, provided b ≥ 2: spend one grain by doubling to the right and then using one of the new grains to double again to the right to fill the intervening piles with one grain each, and then use these grains to shuffle the pile at the end back into the second from leftmost position, and then use another grain in the leftmost to bring the pile into the first from leftmost. Therefore f(n,b,e) ≥ f(n,b-2,f(n-1,e+4,0)) for n ≥ 4 and b ≥ 2.

With six piles with a single grain 1 1 1 1 1 1, we initially double
to get 2 2 2 0 7, then apply the exponential rule for n = 3 to get 2 2 0 0 28, and
then the repeated exponential (tetration) rule for n = 4 to get 2 0 0
0 2^{33}, and then using the reapplication rule we have to
evaluate 2^{33}+4 0 0 0, in comparison to our target of
2010^{20102010}. As we can waste grains by
shuffling empty piles, we need not worry if we exceed the target.

In other words, we need to get a lower bound for the tetration f(4,
2^{33}+4, 0). This is by the reapplication rule greater than
exponentiation repeated 2^{32} times, or 2 ↑ ↑
2^{32} in Knuth's notation.

Is this clearly greater than c = 2010^{20102010}?
Suppose we take log base 2. Then log_{2} c < 11
2010^{2010} and log_{2} log_{2} c < 4 + 11
. 2010 < 25 000.

But log_{2} log_{2} 2 ↑ ↑ 2^{32} is
just 2 ↑ ↑ (2^{32} - 2) and 2 ↑ ↑ 4 >
65 000 so we have an scale of headroom that is difficult to relate to
quantities in our universe.

From the two rules of moving and adding one to the right, and removing and shuffling, a system is created that makes more grains than one can comfortably represent with exponential notation. Amazing!

Thanks to David B for bringing the problem to my attention, it was a lot of fun, and many thanks to Rob Backhouse for proofreading and improving the method.

Post a comment

Hey John, why did you stop blogging?

Posted 2012-10-30 12:29:40 GMT by kidakaka