Ukrajina 2008

a. To begin, we form $2^{2007}$ different sequences satisfying the given conditions. For all the sequences let $a_1=0$. Let each successive member of the sequence be "by 0 greater" or "by 1 greater" than the preceding one. Thus we obtain $2^{2007}$ different sequences. It's easy to show that $a_k\le k-1$ for each of these sequences. To prove that the number of sequences is greater than $2^{2007}$, one sequence will be enough, which is not in the list of $2^{2007}$ sequences, but satisfies the given conditions. E.g., it can be a sequence: $(0,0,2,2,...,2)$.

b. Let's name some random non-decreasing sequence of non-negative integers $a_1\le a_2\le ...\le a_n$ obeying $a_k\le (k-1)$, $k=1,n$ as fine. Note that a random fine sequence with $(n+1)$ members can be obtained from fine sequence with $n$ members if you add a member $a_{n+1}$ for which $a_n\le a_{n+1}\le n$ is true. Similarly, if we remove the last member of some sequence with $(n+1)$ members, we obtain fine sequence with $n$ members.

Let the number of fine sequences with $n$ members be $x_n$. We can obviously build at least two different fine sequences with $(n+1)$ members if we assign the two allowable possibilities for $a_{n+1}$: they will be $a_n$ or $(a_n+1)$. Similarly, proceeding analyzing, we find $x_{n+m}\ge 2^m{x}_n$. Now you only have to find out the number of sequences for a small value of $n$. $x_1=1$ as there is only one such a sequence: $(0)$. Again you'll easily find that $x_2=2$ because only sequences $(0,0)$ and $(0,1)$ can be regarded as fine. Thus we have an assessment $x_{2008}\ge 2^{2006}{x}_2=2^{2007}$, but it is not enough. To obtain a sequence with 3 members, we may add one of the numbers $0,1,2$ to the sequence $(0,0)$, and one of the numbers $0,1$ to the sequence $(0,1)$. I.e., $x_3=5$ and $x_{2008}\ge 2^{2005}{x}_3=5\cdot 2^{2005}>2^{2007}$. After that we continue calculating the number of fine sequences for small values of $n$: $(0,0,0)\to 0,1,2,3$, $(0,0,1),(0,1,1)\to 1,2,3$, $(0,0,2),(0,1,2)\to 2,3$. I.e. in all we obtain 14 different fine sequences and therefore $x_4=14$ and $x_{2008}\ge 2^{2004}{x}_4=14\cdot 2^{2004}>5\cdot 2^{2005}$. As one of these fine sequences ends in $0$, we can add $0,1,2,3,4$. As three of the sequences end in $1$, we can add $1,2,3,4$. As five of the sequences end in $2$, we can add $2,3,4$: as another five end in $3$, we can add $3,4$. So in all we have $5\cdot 1+3\cdot 4+5\cdot 3+5\cdot 2=42$, which implies the first proven assessment: $x_{2008}\ge 2^{2003}{x}_5=42\cdot 2^{2003}>32\cdot 2^{2003}=2^{2008}$.