FOM: Mythical Tree/High School

[Harvey Friedman]

Here is another high school problem. It is closely related to what is
needed for the lower bounds in the recent decreasing sequence of algebraic
sets work.

There was a Mythical Tree which simply got too big to survive. It wasn't
that it grew very tall. In fact, a squirrel could get to any top of the
tree from its root using exactly four branches.

The tree had a very peculiar growth pattern. It started its life in a
rather ordinary way: its root grew two branches.

At that point in its development, there were only two treetops - the tops
of those first two branches.

Next, one of the treetops grew three branches. Next after that, one of the
treetops grew four branches. And so on.

How many total number of branches could the Mythical Tree have grown?

ANSWER: At least 8,390,655. [I think this is exact].

The story of the Mythical Tree got wilder as time went on. In a second
version of the story, the Mythical Tree started its life off with its root
growing three branches. Then some treetop grew four branches, etcetera. How
many branches could the Muthical Tree have grown under this second version
of the story?

ANSWER: At least 2^8192.

Every time the story was told with the root growing one more branch at the
beginning, the lower bound got exponentially larger.

Finally, the story was told with a squirrel getting up to any top of the
tree from the root using exactly five branches. But with the root growing
only 2 branches. Then how many branches could the Myuthical Tree have grown?

ANSWER: At least an exponential stack of 2's of height 2^4096.

As the height of the tree is increased, the level of the Ackerman hierarchy
moves up and the argument is the number of branches out of the root at the
beginning of the Mythical Tree's life.

These lower bounds are quite "close" to the upper bounds. The exact answer
can be given by a recursion equation.