John Fremlin's blog: Doubling and shuffling grains to make a pile

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⁶⁴ 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^be 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³³, and then using the reapplication rule we have to evaluate 2³³+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³³+4, 0). This is by the reapplication rule greater than exponentiation repeated 2³² times, or 2 ↑ ↑ 2³² in Knuth's notation.

Is this clearly greater than c = 2010^20102010? Suppose we take log base 2. Then log₂ c < 11 2010²⁰¹⁰ and log₂ log₂ c < 4 + 11 . 2010 < 25 000.

But log₂ log₂ 2 ↑ ↑ 2³² is just 2 ↑ ↑ (2³² - 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.