Solution
This one generated a fair bit of interest.
The numbers that arrived in my inbox were:
144
162
256
384
448
2560
4096
12288
2^29
2^65
2^321
And the best: 2^16385 = 2^2^14, by Stephen Meskin, Mark Rickert, Jim Guilford, and Joseph DeVincentis.
Here is the path to this 4933-digit number. We need two subroutines:
A. (... a, b ...) → (... 0, 2a + b ...)
Just repeat 10 type 1 moves.
B. (... a, 0, 0 ...) → (... 0, 2^a, 0 ...)
Use type 1 and then repeat the pair of A, type 2.
|
1
|
1
|
1
|
1
|
1
|
|
|
1
|
0
|
3
|
1
|
1
|
type 1
|
|
1
|
0
|
2
|
3
|
1
|
type 1
|
|
1
|
0
|
2
|
0
|
7
|
A
|
|
1
|
0
|
1
|
7
|
0
|
type 2
|
|
1
|
0
|
1
|
0
|
14
|
A
|
|
1
|
0
|
0
|
14
|
0
|
type 2
|
|
0
|
2
|
0
|
14
|
0
|
type 1
|
|
0
|
1
|
14
|
0
|
0
|
type 2
|
|
0
|
1
|
0
|
16384
|
0
|
B
|
|
0
|
0
|
16384
|
0
|
0
|
type 2
|
|
0
|
0
|
0
|
2^16384
|
0
|
B
|
|
0
|
0
|
0
|
0
|
2^16385
|
A
|
As for six boxes, the best known result is
2 * 2^(2^^(2^^(2^(14))))
Here, 2^^x means 2^(2^(2^(...^2))), with x many 2s. This was found by Joseph DeVincentis. The factor of 2 and the base of 2 hardly change it, so it is close to 2^^(2^^16384). I guess we can use the horrible word ginormous for this.
One last subroutine:
C. (...n, 0, 0, 0...) → (...0, 2^^n, 0, 0)
Proof:
(n, 0, 0, 0,) → (n − 1, 2, 0, 0)
→ (n − 1, 0, 2^2, 0) → (n − 2, 2^2, 0, 0)
→ (n − 2, 0, 2^2^2, 0) → (n − 3, 2^2^2, 0, 0) ... (0, 2^^n, 0, 0)
Now start by treating the last 5 boxes as in the third-last line in the 5-box case: (0 0 2^14 0 0)
|
1
|
0
|
0
|
2^14
|
0
|
0
|
5-box case
|
|
0
|
2
|
0
|
2^14
|
0
|
0
|
type 1
|
|
0
|
1
|
2^14
|
0
|
0
|
0
|
type 2
|
|
0
|
1
|
0
|
2^^2^14
|
0
|
0
|
C
|
|
0
|
0
|
2^^2^14
|
0
|
0
|
0
|
type 2
|
|
0
|
0
|
0
|
2^^2^^2^14
|
0
|
0
|
C
|
|
0
|
0
|
0
|
0
|
2^2^^2^^2^14
|
0
|
B
|
|
0
|
0
|
0
|
0 |
0
|
2 * 2^2^^2^^2^14
|
A
|
For n = 4, the maximum value is 28. For n = 3, it is 7.
This problem is well studied and the two solutions above are the best known, but there is no proof of optimality. See this 2010 post by Terence Tao to the polymath blog; and in particular, Michael Nielsen's wiki.
UPDATE
Richard Stong has found, and proved, a general formula for a(n), the maximum number of coins obtainable. It is a rather beautiful formula involving a palindrome.
Recall Knuth's UpArrow notation:
a↑b is ab
a↑↑b is a^(a^(a^(...^a))) with b many a-terms
aa↑↑a↑b is a a↑↑ (a a↑↑ (a ...)) with b many a-terms. And so on.
Let f_n(x) = 2a↑↑...a↑x, with n arrows, and let f_0(x) = 2x.
Example:
f_0(x) = 2x,
f_1(x) = 2^x,
f_2(x) = 2a↑a↑x = 2^2^...^2 with x copies of 2, etc.
Let F_n be the composition of f_0, f_1, ..., f_(n − 4).
Let G_n be similar composition, but with the terms in the opposite order.
Then a(n) = G_n(F_n(7)), a formula due to Richard Stong.
For n = 3, this is 7
For n = 4, this is 2 × 2 × 7 = 28
For n = 5, this is f0(f1(f1(f0(7)))) = 2 2^(2^(2 7))
For n = 6, this is f0(f1(f2(f2(f1(f0(7)))), which was worked out, above
For n = 7, f0(f1(f2(f3(f3(f2(f1(f0(7))))))
And so on.
I created an OEIS entry for the sequence 1, 3, 7, 28, ... and there is a link there to Richard's notes.
I really did not expect there to be a uniform formula for the general case, so this was a pleasant surprise.
[Back to Problem 1233]
© Copyright 2017 Stan Wagon. Reproduced with permission.