Valid Sets (The actual NIMO 2012 3.9)

Consider an infinite directed graph where each real number $r$ is associated with a vertex and there is an edge from every $r$ to $f(r)$ . Then the problem wants us to find an induced subgraph with 8 vertices such that

1. the edge from every vertex stays in this subgraph, and
2. the only directed cycles that exist are 1-cycles, i.e. loops.

By condition 1 and the graph's construction, any connected component of the subgraph must have equally many edges and vertices, so it must have exactly one directed cycle, which by condition 2 must be a loop. Ignoring the loop, the connected component would be a tree rooted at the looped vertex. Now it's much easier to see what our selection must look like --- if we select a vertex, we must select all its ancestors, so we're just counting ways to select subtrees containing the roots.

By solving $x = f(x)$ , we find two vertices that have a loop: 0 and 3.

In general, by solving $r = f(x)$ by the quadratic formula we get $x = 1 \pm \sqrt{1+r}$ , so the vertices with edges to $r$ are the vertices $1 \pm \sqrt{1+r}$ (if they exist, which is true if $r \geq -1$ .)

Investigating 3, we find that -1 has an edge to 3 (as does 3 itself), and only 1 has an edge to -1.

Investigating 0, we find that 2 has an edge to 0 (as does 0 itself).

Now, note that for any vertex $r$ satisfying $-1 < r < 3$ , the roots $1 \pm \sqrt{1+r}$ exist and are distinct, and furthermore $-1 = 1 - \sqrt{1+3} < 1 \pm \sqrt{1+r} < 1 + \sqrt{1+3} = 3,$ so there exist two vertices with edges to $r$ and they satisfy exactly the same conditions as $r$ .

Recursively applying this, we discover that 1 and 2 are both roots of (nonintersecting) infinite complete binary trees. We can now completely describe the rooted forest we're selecting subtrees from: 3 has one child (-1), which has one child (1), which has an infinite complete binary tree beneath it; 0 has one child (2), which has an infinite complete binary tree beneath it.

      /\              /\
      \3              \0
       |               |
      -1               2
       |             /   \
       1           -X     X-
     /   \        /  |   |  \
   -X     X-     X   X   X   X
  /  |   |  \   / \ / \ / \ / \
 X   X   X   X  ...         ...
/ \ / \ / \ / \
...         ...

This is a good time to recall that the number of binary trees with $n$ vertices is the $n$ th Catalan number, $C_n = \frac{1}{n+1}\binom{2n}{n}.$ Unfortunately we still have to count subtrees from two separate binary trees simultaneously, which still requires a complicated summation of Catalan numbers if done naïvely. Therefore, we apply an imaginary-vertex hack to take advantage of the symmetry, leaving lots of easy cases:

1. If 3 and -1 and 0 are all selected, we can pretend 1 and 2 are children of an imaginary root vertex; then, we want a 6-vertex binary tree rooted at the imaginary vertex, yielding $C_6 = 132$ sets.
2. If 0 is not selected, we must select 3 and -1, and then get a 6-vertex binary tree from the tree rooted at 1, yielding 132 more sets.
3. If neither 3 nor -1 is selected, we must select 0 and then get a 7-vertex binary tree from the tree rooted at 2, yielding $C_7 = 429$ sets.
4. If 3 is selected but not -1, we must select 0 and then get a 6-vertex binary tree from the tree rooted at 2, yielding 132 more sets.

Our answer is $132 + 132 + 429 + 132 = \boxed{825}$ .

The statement should say $k>0$ . I assume the reader can solve equations of the form $x^2-2x=c$ .

1) says that $S$ should be stable by $f$ and 2) says that there is no trivial cycle. We can conclude that $S$ should contain at least one of the fixed points of $f$ , which are $0$ and $3$ . This also says that all the other $x\in S$ should be such that for some $k$ , $f^k(x)\in\{0,3\}$ .

This says that each $S$ is composed of the nodes of any subtrees of the two trees $T_0$ and $T_3$ , defined as follows:

• the root of $T_0$ is $0$ and the root of $T_3$ is $3$ ;
• the children of $y$ in both trees are all $x$ such that $f(x)=y$ (except if $x=y$ ).

Looking at $T_0$ we have one $x≠0$ such that $f(x)=0$ , namely $2$ , then $\{1+\sqrt3\,1-\sqrt3\}$ , and we stop here. Looking at $T_3$ we have one $x≠3$ s.t. $f(x)=3$ , i.e. $-1$ , then we have a double root $1$ , and then two roots $\{1-\sqrt2,1+\sqrt2\}$

    0             3
    |             |
    2            -1
   / \            |
1+√3  1-√3        1
/ \    / \       / \
...    ...    1+√2 1-√2
              / \   / \
              ...   ...

We want to know the shape of the trees, in fact they are binary and infinite below the nodes 2 and -1. Indeed we can show that if $-1<c<3$ then the equation $f(x)=c$ will have two roots $x_1,x_2$ such that $-1<x_1<x_2<3$ . Doing the math, the condition $x_2<3$ is equivalent to $-1<c$ and the condition $-1<x_1$ is equivalent to $c<3$ .

Then all we have to do is compute the number of subtrees of a given size in a binary tree, then we will be able to enumerate those of the trees $T_0$ and $T_3$ .

The number of subtrees of size $n$ of a infinite binary tree is given by $C(0)=1$ and $C(n+1)=\sum_{k=0}^n{C(k)C(n-k)}$ , which are catalan numbers, but we don't need to know that, I've just computed them manually up to $C(7)$ .

Then the number of subtrees of size $n$ in $T_0$ is $t_0(n)=C(n-1)$ and in $T_3$ it is $t_3(n)=C(n-2)$ , assuming $C(n<2)=1$ . The answer is then the number of ways we can get 8 nodes out of two subtrees of $T_0$ and $T_3$ :

$\sum_{k=0}^8t_0(k)t_3(8-k)=C(7)+2C(6)+2C(5)+2C(4)+2C(2)C(3)=825~~.$