IMO2010趣题：用有限次操作得到2010^(2010^2010)枚硬币

下面这个问题来自于 IMO 2010 中的第 5 题。桌子上有 B₁、 B₂、 B₃、 B₄、 B₅、 B₆共六个盒子，初始时每个盒子里面都有一枚硬币。允许以下两种操作：

(1) 选择一个非空的盒子 B_j（1 ≤ j ≤ 5），从 B_j里拿走一枚硬币，然后在 B_j+1里添加两枚硬币。

(2) 选择一个非空的盒子 B_k（1 ≤ k ≤ 4），从 B_k里拿走一枚硬币，然后交换 B_k+1和 B_k+2里面的硬币数（这两个盒子里的硬币数都有可能是 0 ）。

是否有可能通过有限次操作，使得最后 B₁、 B₂、 B₃、 B₄、 B₅都是空的，并且 B₆里面恰好有 2010 ^ (2010 ^ 2010) 枚硬币（符号 ^ 表示乘方）？

我们把操作 1 简记作 [a, b] → [a – 1, b + 2] 。反复使用操作 1 便能把 [a, 0] 变成 [0, 2a] 。我们不妨把它视作一个新的复合操作，叫做 M1 。不断使用 M1 和换位，我们便可以把 [a, 0, 0] 变成 [0, 2^a, 0] ：

[a, 0, 0] → [a – 1, 2, 0] → [a – 1, 0, 4] → [a – 2, 4, 0] → [a – 2, 0, 8] → … → [1, 0, 2^a] → [0, 2^a, 0]

不妨把这个新的复合操作叫做 M2 。不断使用 M2 和换位，我们可以把 [a, 0, 0, 0] 变成 [0,^a2, 0, 0] （其中^a2 表示 2 的 a 次超级幂，也就是）：

[a, 0, 0, 0] → [a – 1, 2, 0, 0] → [a – 1, 0, 4, 0] → [a – 2, 4, 0, 0] → [a – 2, 0, 16, 0] → [a – 3, 16, 0, 0] → [a – 3, 0, 65536, 0] → … → [1, 0,^a2, 0] → [0,^a2, 0, 0]

我们把这个复合操作叫做 M3 。

好了。现在，我们先把初始局面 [1, 1, 1, 1, 1, 1] 变成 [0, 0, 140, 0, 0, 0] ：

[1, 1, 1, 1, 1, 1] → [0, 2, 2, 2, 2, 3] → [0, 2, 1, 1, 8, 3] → [0, 2, 1, 1, 0, 19] → [0, 1, 19, 0, 0, 0] → [0, 1, 1, 36, 0, 0] → [0, 1, 1, 1, 0, 140] → [0, 0, 140, 0, 0, 0]

然后，我们调用一次 M3 ，便会得到 [0, 0, 0,¹⁴⁰2, 0, 0] 。¹⁴⁰2 是一个非常非常非常非常大的数，它远远大于我们题目中提到的数。接下来，不断对¹⁴⁰2 所在的盒子使用操作 2 ，每次都能白白耗掉一枚硬币，直到这个盒子里只剩下 2010 ^ (2010 ^ 2010) / 4 枚硬币，此时局面变为 [0, 0, 0, 2010 ^ (2010 ^ 2010) / 4, 0, 0] 。最后，两次使用 M1 操作，便能得到我们想要的最终局面 [0, 0, 0, 0, 0, 2010 ^ (2010 ^ 2010)] 。

答案来自http://michaelnielsen.org/polymath1/index.php?title=Imo_2010，叙述时有改动。很多简单的问题都可以迅速产生出一些连乘方也难以表达的巨大数字。对此感兴趣的读者不妨看看这里：3857 925 1738 4009