Irish Mathematical Olympiad

There are several different solutions:

Solution 1: The function $f: \{1, \dots, 2008\} \to \{1, \dots, 2008\}$ given by $f(i) = a_i$ is a bijection. Let us consider its inverse $f^{-1}: \{1, \dots, 2008\} \to \{1, \dots, 2008\}$. The condition that $i \in \{a_1, \dots, a_i\}$ for $i \ge 2$ is equivalent to $f^{-1}(i) \in \{1, \dots, i\}$ for all $i \ge 2$. Therefore, there are two choices for $f^{-1}(2)$, two choices for $f^{-1}(3)$ (since one of $\{1, 2, 3\}$ has been 'used already' for $f^{-1}(2)$), two choices for $f^{-1}(4)$, ..., two choices for $f^{-1}(2008)$. Thus there are $2^{2007}$ possibilities for the function $f^{-1}$. Therefore there are $2^{2007}$ such sequences.

Solution 2: We will say that a 2008-tuple is good if it has the required properties. Let $A = (a_1, ..., a_{2008})$ be a good 2008-tuple. Let $S_A = \{i : 2 \le i \le 2008 \text{ and } a_i \neq i\}$. We will show that $A \mapsto S_A$ is a bijection between the set of good 2008-tuples and the set of subsets of $\{2, ..., 2008\}$.
First we observe that the function $i \mapsto a_i$ is a bijection from $\{1, ..., 2008\}$ to itself.
Lemma: If $A$ is good then for each $i = 1, ..., 2008$, either $a_i = 1$ or $a_i \ge i$.
Proof: This is obvious for $i = 1$ and $i = 2$. Suppose that $i \ge 3$ and $a_i \in \{2, ..., i - 1\}$. Property (a) implies in particular that $a_i \neq a_j$ for $j = 1, 2, ..., a_i - 1$. That is,
$$a_i \notin \{a_1, a_2, ..., a_{a_i - 1}\}.$$
Therefore we must have $a_{a_i} = a_i$. Therefore $i = a_i$ (bijectivity again) which contradicts our assumption that $a_i < i$. $\square$
Now suppose that $A$ is a good 2008-tuple and that $S_A = \{n_1, n_2, ..., n_k\}$ where $n_1 < n_2 < \dots < n_k$. Clearly $a_i = i$ for all $i \notin S_A \cup \{1\}$. So for $i \in S \cup \{1\}$ we must have $a_i \in S \cup \{1\}$ also. That is to say, $i \mapsto a_i$ is a bijection $S_A \cup \{1\} \to S_A \cup \{1\}$. Now the lemma above clearly implies that $a_1 = a_{n_1}, a_{n_j} = n_{j+1}$ for $j = 1, ..., k-1$ and $a_{n_k} = 1$. In other words $A$ is determined by the set $S_A$. So $A \mapsto S_A$ is an injection.
Now suppose that $S = \{n_1, ..., n_k\} \subset \{2, ..., 2008\}$. Let $a_i = i$ for all $i \notin S$. Define $a_1 = n_1, a_{n_j} = n_{j+1}$ for $j = 1, ..., k-1$ and let $a_{n_k} = 1$. Then is easily seen that $A = (a_1, ..., a_{2008})$ is good and clearly $S_A = S$. Therefore $A \mapsto S_A$ is a surjection. $\square$

Solution 3: (By induction.) We claim that, for integers $n \ge 2$,

the number of bijections $f: \{1, \dots, n\} \to \{1, \dots, n\}$ such that $i \in \{1, \dots, f(i)\}$ for all $i \ge 2$, is $2^{n-1}$. Let us call such functions good. This easily checked for $n=2$. Suppose that the statement is true for some $n=2, \dots, k$ where $k \ge 2$. Now consider a good function $f: \{1, \dots, k+1\} \to \{1, \dots, k+1\}$. There are 2008 possible choices for $f(1)$. If $f(1)=1$ then we must have $f(i)=i$ for all $i$, so there is one such function. If $f(1)>1$, then $f(i)=i$ for $i=2, \dots, f(1)-1$. Now it is easy to see that the number of possible such functions $f$ is the same as the number of good functions from $\{1, \dots, k-f(1)\}$ to itself. The induction hypothesis implies that there are $2^{k-f(1)-1}$ of these. Therefore, the number of good functions on $\{1, \dots, k+1\}$ is
$$1+2^{k-1}+2^{k-2}+\dots+2+1=2^k.$$
This completes the induction step.