Mythical tree problem

The mythical tree problem is a combinatorial problem created by Harvey Friedman.

In the problem, the tree has a strange growth pattern. In the first stage, the tree grows k branches, forming k treetops. In the next stage, one of the treetops forms k+1 branches, increasing the number of treetops. The problem asks: what is the maximum number of branch segments a tree starting at k branches grow at once, during the tree's final stage of growth, provided that a squirrel can go from the root to any treetop without navigating more than n branch segments?

Friedman considers the ternary function V(k,m,n) defined as follows:

V(1,n,m) = n

V(k+1,n,1) = V(k,n+1,n+1)

V(k+1,n,m+1) = V(k,V(k+1,n,m)+1,V(k+1,n,m)+1).

Define seg(n,k) as the maximum number of branch segments as above. Friedman has shown that seg(n,k) = V(n,k,k).

From that, he has shown that:

• n = 4 and k = 2 corresponds to seg(4,2) = 22,539,988,369,406 segments (there was a misprint in his work: there are exactly 41*2³⁹ - 2 branch segments, not 40*2³⁹ - 2)
• n = 4 and k = 3 corresponds to a value seg(4,3) > 2²⁹⁵
• n = 5 and k = 2 corresponds to a value seg(5,2) > 2 ↑↑ 2²⁹⁵
• The growth rate of the number of segments as a function of k can be generalized to be similar to that of the Ackermann function.

External links

• Friedman's posting at FOM

See also

Googology by Harvey Friedmann

Main article: Harvey Friedman

Mythical tree problem · Friedman's vector reduction problem · Friedman's finite ordered tree problem · block subsequence theorem n(4) · Friedman's circle theorem · TREE sequence TREE(3) · subcubic graph number SCG(13) · transcendental integer · finite promise games · Friedman's finite trees · Greedy clique sequence · Bop-counting function