[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:

KazakhNMO_2015_5_01

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.

KazakhNMO_2015_5_02In 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.

KazakhNMO_2015_5_03

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:

KazakhNMO_2015_5_04

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.

KazakhNMO_2015_5_05

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.)

Advertisements
This entry was posted in Grade 12, Kazakhstan and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s