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\ne 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\ne 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<\cdots <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}+\cdots +2+1=2^k.$$ This completes the induction step.