ELMO SL 2012 C6

Consider a directed graph $G$ with $n$ vertices, where $1$ -cycles and $2$ -cycles are permitted. For any set $S$ of vertices, let $N^{+}(S)$ denote the out-neighborhood of $S$ (i.e. set of successors of $S$ ), and define $(N^{+})^k(S)=N^{+}((N^{+})^{k-1}(S))$ for $k\ge2$ .

For fixed $n$ , let $f(n)$ denote the maximum possible number of distinct sets of vertices in $\{(N^{+})^k(X)\}_{k=1}^{\infty}$ , where $X$ is some subset of $V(G)$ . Show that there exists $n>2012$ such that $f(n)<1.0001^n$ .

Linus Hamilton.