Japan 2007

Consider a general problem with cards $1$, $2$, $\dots$, $n$. Let $F_n$ be the number of choices when there are $n$ cards. $F_1=1$ and $F_2=2$ are trivial. Let $k\ge 3$. We will consider $F_k$. If card $k$ is not chosen, the number of ways is trivially $F_{k-1}$.

Consider the case where card $k$ is chosen. If any card other than $k$ is chosen, we cannot choose $1$. And if we remove the card $k$ and decrease the numbers on other cards by $1$, we get a proper choice from cards $1$, $\dots$, $k-2$. On the other hand, if we have a proper choice from $1$, $\dots$, $k-2$, we get a choice with $k$ and some other cards among $1$, $\dots$, $k-1$. If no card other than $k$ is chosen, there is trivially only $1$ way. Therefore, the number of proper choices with card $k$ is $F_{k-2}+1$.

So we get a relation $F_k=F_{k-1}+F_{k-2}+1$. Calculate the sequence by this relation we get $F_{15}=1596$.