## [Soln] 2015 Kazakhstan NMO Problem 5

2015 Kazakh NMO 5. Find all possible $\{ x_1, x_2, \dots, x_n \}$ permutations of $\{ 1, 2, \dots, n \}$ so that when $1 \leq i \leq n - 2$ then we have $x_i < x_{i+2}$ and when $1 \leq i \leq n - 3$ then we have $x_i < x_{i+3}$. Here $n \geq 4$.

Let $A_n$ denote the number of such permutations for $n$. Let’s work out the value of $A_4$ manually:

1234     2134     3124     4123
1243     2143     3142     4132
1324     2314     3214     4213
1342     2341     3241     4231
1423     2413     3412     4312
1432     2431     3421     4321

(Note: See how the permutations are systematically listed out? When going through all cases, always find a systematic way of listing the cases out.) Hence, $A_4 = 5$. As we are going through the cases from left to right, we could have noticed that the more we had larger numbers at the front, the more the permutations would not satisfy the given conditions. Something to keep in mind.

How about $A_5$? There are $5! = 120$ possible permutations, hence the prospect of writing out $120 \times 5 = 600$ numbers just to check the $n = 5$ case seems excessive. So $n = 4$ is probably going to be the only concrete example we can work out; we will have to reason out the larger cases.

As we are thinking about smart ways to compute $A_5$, we could realise that the case of $n = 5$ has very much in common with the case $n = 4$. The only difference is the additional number “5”: we have to decide where to put it, and after we have put it, we need to check that the conditions are still satisfied “near” the number 5. (For a position $i$ far away enough from where the number “5” is, the values of $x_i$, $x_{i+2}$ and $x_{i+3}$ will not change.)

More generally, it seems like a good idea to think about where the largest number $n$ can be placed. It can’t be placed to far in front; in fact, it can’t be placed before the last 2 positions, if not no possible number can go into the slot 2 places after it:

Hence, $n$ is either in the last position or the second-to-last position. We can consider these cases separately.

Case 1: $n$ is in the last position.

In that case, the first $n-1$ numbers occupy the first $n-1$ spots, i.e. this is exactly the case of $n-1$! Clearly sticking the number $n$ on at the end does not cause the conditions to be violated, hence the number of permutations that satisfy the given conditions in this case is exactly $A_{n-1}$.

Case 2: $n$ is in the second-to-last position.

It seems reasonable, after inserting the largest number, to ask, where can we place $n-1$, the next largest number? One option is to place it right at the end:

Here, the first $n-2$ numbers occupy the first $n-2$ spots, hence by the same argument used in Case 1, there are $A_{n-2}$ permutations that satisfy the given conditions.

The other option for $n-1$ is to be placed 2 spots before $n$; this is because the number 2 spots after $n-1$ must be larger than it, and the only such number is $n$. However, this causes the 3-space-apart condition to fail (as in the diagram below)! Hence there are no possible permutations in this sub-case.

In summary, we have, for all $n$,

$A_n = A_{n-1} + A_{n-2}$

(There is a minor technicality here: we have to work out what the relation means when $n = 5$: this is because the relation above will give $A_5 = A_4 + A_3$, but the question has limited the domain of $n$ to $n \geq 4$. This is fairly easy to get over: we can either drop the condition $n \geq 4$ and say that the condition is (vacuously) true if the indices are too large, or we can use the arguments above to work out the value of $A_5$.)

After we have either established that $A_5 = 8$ or extended the sequence to get $A_3 = 3$, we can conclude that $A_n = F_{n+1}$ where $\{F_i\}$ is the Fibonacci sequence with $F_1 = F_2 = 1$. QED.

(Note: Is there a need to go further to say that

$A_n = F_{n+1} = \displaystyle\frac{(1+ \sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5}}?$

My own sense is that the Fibonacci sequence is well known enough that the last step is not necessary.)