The trunk of the sky-high tree branches into two at a height of one foot. In the following, we consider the part between two branches as a branch, on which there is no further branching. Every branch of the sky-high tree is straight and ends one foot higher than its end closer to the ground. We consider the children of a branch to be the branches starting from the higher end of the branch, which are also considered siblings to each other. Every branch of the sky-high tree has at least two children, and if it does not have exactly two children, then it has a sibling who has exactly two children. Siblings always have a different number of children. If a branch has more than two children, then it has a sibling who has exactly one child less than it. How many branches start from the branches at a height of $n$ feet?
Let's write down how many children each branch (and the trunk) has. Let $X$ be a branch (or the trunk) that has $x$ children. Let $y$ be the maximum number written on the children of $X$. Let $z$ be the maximum of the positive integers less than $y$ that do not appear on the children of $X$. The number $z$ must exist because 1 cannot appear on any branch. Then $z+1$ appears on one of the children of $X$. If $z>1$, then $z+1>2$, so $z$ appears on one of the children of $X$. This is a contradiction, so $z=1$. Therefore, the numbers $2,3, \ldots, y$ all appear on the children of $X$. The siblings have different numbers of children, so there is exactly one of each. Thus, the number of children of $X$ is $y-1$, so $y=x+1$. Therefore, the numbers written on the children of $X$ are $2,3, \ldots, x+1$.

Let's introduce a directed graph among the branches, where there are two types of edges: one type is a "vertical" edge, which leads from a branch labeled $x$ to its child labeled $x+1$, and the other type is a "horizontal" edge, which leads from a branch labeled $x$ to its sibling labeled $x-1$, if $x>2$. It can be seen that in the graph, there is exactly one way to reach the trunk of the tree from each branch, because from each branch, there is exactly one way to reach each of its children. From each branch, exactly one vertical and exactly one horizontal edge starts, except for the 2-labeled branches, from which only a vertical edge starts.

The number of branches starting at height $n$ is equal to the number of 2-labeled branches starting at height $n+1$, because every branch has exactly one 2-labeled child. Let's select a 2-labeled branch $X$ starting at height $n+1$. There is exactly one path in the graph from the trunk of the tree to $X$. Let's call finite sequences consisting of + and - signs (+/-) sequences. The path can be described by a (+/-) sequence, where + represents a vertical edge and - represents a horizontal edge. The (+/-) sequence uniquely determines $X$. It can be seen that with each +, the number on the current branch increases by one, and with each -, it decreases by one, as we move along the path according to the sequence. The number 2 appears on both the first and the last branch of the path, so the number of + and - signs is the same. The path from the trunk to $X$ contains $n+1$ vertical edges, because the height increases by one with each vertical edge, and does not change with horizontal edges. Thus, the number of - signs is also $n+1$. Let's call a (+/-) sequence with $n+1$ + signs and $n+1$ - signs good if for each $i$, the number of + signs among the first $i$ terms is at least as many as the number of - signs. The number on each branch of the path is at least 2, and the number on the first branch is 2, from which it is easy to see that the (+/-) sequence corresponding to $X$ is good. It can also be seen that if the (+/-) sequence is good, then it is not possible to try to move along a horizontal edge from a 2-labeled branch. Thus, the number of good (+/-) sequences is equal to the number of branches starting at height $n$.

The number of good sequences can be calculated by subtracting the number of non-good sequences from the number of all (+/-) sequences with $n+1$ + signs and $n+1$ - signs. The number of all such sequences is $\binom{2 n+2}{n+1}$. Let's take a sequence that is not good. There is a minimal $i$ for which the number of - signs among the first $i$ terms is more than the number of + signs. By minimality, among the first $i-1$ terms, there are at most as many - signs as + signs. This can only happen if among the first $i-1$ terms, there are as many + signs as - signs, and the $i$-th term is -. Let's change all the terms after the $i$-th term, and call this the modified sequence. If we also changed the $i$-th term, the number of + and - signs would not change (because they are equal). Thus, in the modified sequence, there are $n$ + signs and $n+2$ - signs. It can be seen that for a sequence with $n$ + signs and $n+2$ - signs, there is an $i$ for which the number of - signs among the first $i$ terms is more than the number of + signs (because it is more in the entire sequence). Notice that if we change all the terms after the minimal $i$-th term, we get back the original sequence. Thus, the number of non-good sequences is equal to the number of sequences with $n$ + signs and $n+2$ - signs, which is $\binom{2 n+2}{n}$.

Therefore, the number of branches is: $\binom{2 n+2}{n+1}-\binom{2 n+2}{n}$, which is the $(n+1)$-th Catalan number.

Based on the work of Gáspár Attila (Miskolc, Földes Ferenc Gimn., 12th grade)

Note. The majority of the contestants who provided the correct solution arrived at the conclusion that the number of branches starting at height $n$ is the $(n+1)$-th Catalan number by reducing the problem to some known problem. After that, they did not detail the calculation of this.