2015 Kazakh NMO 5. Find all possible permutations of so that when then we have and when then we have . Here .
Let denote the number of such permutations for . Let’s work out the value of 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, . 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 ? There are possible permutations, hence the prospect of writing out numbers just to check the case seems excessive. So 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 , we could realise that the case of has very much in common with the case . 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 far away enough from where the number “5” is, the values of , and will not change.)
More generally, it seems like a good idea to think about where the largest number 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, is either in the last position or the second-to-last position. We can consider these cases separately.
Case 1: is in the last position.
In that case, the first numbers occupy the first spots, i.e. this is exactly the case of ! Clearly sticking the number 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 .
Case 2: is in the second-to-last position.
It seems reasonable, after inserting the largest number, to ask, where can we place , the next largest number? One option is to place it right at the end:
Here, the first numbers occupy the first spots, hence by the same argument used in Case 1, there are permutations that satisfy the given conditions.
The other option for is to be placed 2 spots before ; this is because the number 2 spots after must be larger than it, and the only such number is . 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 ,
(There is a minor technicality here: we have to work out what the relation means when : this is because the relation above will give , but the question has limited the domain of to . This is fairly easy to get over: we can either drop the condition 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 .)
After we have either established that or extended the sequence to get , we can conclude that where is the Fibonacci sequence with . QED.
(Note: Is there a need to go further to say that
My own sense is that the Fibonacci sequence is well known enough that the last step is not necessary.)