Quote: We say that f is a straight permutation or order n if and only if for each k=1,2,...,n-1 we have that |f(k)-f(k+1)| 2. Find all values of n such that there are less than 2003 straight permutations of order n. (A permutation's order is the number of elements that permutation has). this is not a very difficult one Tn is the number of straight permutation or order n we can prove that Tn+1=Tn+Tn-2.

I think that you misunderstood the problem. The answer you are giving is not correct, and the problem is not that simple. Only the 6 guys who went to the IMO solved it in the contest, so it actually separated the team from the other competitiors. I wouldn't call this problems easy

You are right I misunderstood the problem Tn is only the number permutation that begin with 1. However, I still don't think that this one is very difficult,I'll find out the solution soon.

Valentin Vornicu wrote: We say that f is a straight permutation or order n if and only if for each k=1,2,...,n-1 we have that |f(k)-f(k+1)| \leq 2. Find all values of n such that there are less than 2003 straight permutations of order n. (A permutation's order is the number of elements that permutation has). As I promised,here is my result Sn= the number straight[/i] permutation or order n S1=1 S2=2 S3=6 Sn=Sn-1+Pn-2 P1=4 P2=6 P3=8 Pn=Pn-1+Pn-3+2 with n<=17 Sn<2003

again I must tell you that you are wrong. Keep trying though - remember in the TST you had this problem and other two in only 4 hours. I still don't think it's easy

Sorry because I'm not very good at English so I can't post the full solution. Anyway, Iwant to see your solution!!

well for one you have not got the right result. for second the recurrence relationships are not correct. please check your solution. it is easy to make mistakes I will post later my solution (in a couple of hours).

hi! silversunboy, u can see sol at : http://ajorza.tripod.com/math.htm

silversunboy wrote: Quote: We say that f is a straight permutation or order n if and only if for each k=1,2,...,n-1 we have that |f(k)-f(k+1)| 2. Find all values of n such that there are less than 2003 straight permutations of order n. (A permutation's order is the number of elements that permutation has). My solution is based on my first result: Tn is the number of straight permutations of order n that start by 1 we can prove that Tn+1=Tn+Tn-2. T1=1 T2=1 T3=2 Sn is the number of straight permutations of order n we have Sn=2Tn+ 2(Tn-2+..+T1) S1=1 S2=2 S3=6 S4=12 S5=20 <=> Sn=Sn-1+2Tn-2+2Tn-3+2 It was just a mistake of calculating,when I try to shorten the result I made a mistake. Now I know for sure that my solution is right. Thanks.

Quote: My solution is based on my first result: Tn is the number of straight permutations of order n that start by 1 we can prove that Tn+1=Tn+Tn-2. you solution is based on a false fact . Please compute with your recurrence T5 and also compute it manually. See that the results differ . I think that Andrei Jorza's solution, although finds correct n, is also flawed , but I need to check it some more. It's easy to miss some cases here.

Sorry it was a mistake in typing Tn+1=Tn+Tn-2+1 not Tn+1=Tn+Tn-2

well you now (after so many trials) have got the recurrence right. Still no justification however. Think how many things could have got wrong with this problem in contest So you see that it is not an easy problem .

H..m I'm afraid to say that I must agree with you. How about your solution? do you have a short solution??

i think i solve it too... but in a different way...[an ugly way i think cause i worked almost 3 hours at it] i found smth like this: T_2n+1=n.(4n ² +3n+5)/3+2 T_2n+2=n.(4n ² +9n+11)/3+4

i think i solve it too... but in a different way...[an ugly way i think cause i worked almost 3 hours at it] i found smth like this: T_2k+1=k.(4k ² +3k+5)/3+2 T_2k+2=k.(4k ² +9k+11)/3+4 n=22??

The main ideea is to look where $n$ is positioned. In that idea let us denote by $x_n$ the number of all the straight permutations and by $a_n$ the number of straight permutations having $n$ on the first or on the last position, i.e. $\sigma(1)=n$ or $\sigma(n)=n$. Also let us denote by $b_n$ the difference $x_n-a_n$ and by $a_n'$ the number of permutations having $n$ on the first position, and by $a_n''$ the number of permutations having $n$ on the last position. From symmetry we have that $2a_n'=2a_n''=a_n'+a_n''=a_n$, for all $n$-s. Therefore finding a recurrence relationship for $\{a_n\}_n$ is equivalent with finding one for $\{a_n'\}_n$. One can simply compute: $a_2'=1$, $a_3'=2$, $a_4'=4$. Suppose that $n\geq 5$. We have two possibilities for the second position: if $\sigma(2)=n-1$ then we must complete the remaining positions with $3,4,\ldots,n$ thus the number of ways in which we can do that is $a_{n-1}'$ (because the permutation $\sigma': \{1,2,\ldots, n-1\}\to\{1,2,\ldots,n-1\}$, $\sigma'(k)=\sigma(k+1)$, for all $k$, $1\leq k\leq n-1$, is also a straight permutation). If on the second position we have $n-2$, $\sigma(2)=n-2$, then $n-1$ can only be in the last position of the permutation or on the third position, i.e. $\sigma(3)=n-1$ or $\sigma(n)=n-1$. If $\sigma(n)=n-1$, then we can only have $\sigma(n-1)=n-3$ thus $\sigma(3)=n-4$ and so on, thus there is only one permutation of this kind. On the other hand, if $\sigma(3)=n-1$ then it follows that $\sigma(4)=n-3$ and now we can complete the permutation in $a_{n-3}'$ ways (because the permutation $\sigma': \{1,2,\ldots, n-3\}\to\{1,2,\ldots,n-3\}$, $\sigma'(k)=\sigma(k+3)$, for all $k$, $1\leq k\leq n-3$, is also a straight permutation). Summing all up we get the recurrence: \[ a_n'=a_{n-1}'+1+a_{n-3}' \Rightarrow a_n=a_{n-1}+a_{n-3}+2,\ \forall \ n\geq 5. \eqno(1) \] The recurrence relationship for $\{b_n\}$ can be obtained by observing that for each straight permutation \break $\tau: \{1,2,\ldots,n+1\}\to\{1,2,\ldots,n+1\}$ for which $2\leq \tau^{-1}(n+1)\leq n$ we can obtain a straight permutation $\sigma: \{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ by removing $n+1$. Indeed $n+1$ is "surrounded" by $n$ and $n-1$, so by removing it, $n$ and $n-1$ become neighbors, and thus the newly formed permutation is indeed straight. Now, if $\tau^{-1}n\in\{1,n+1\}$ then the newly formed permutation $\sigma$ was counted as one of the $a_{n}$-s, minus the two special cases in which $n$ and $n-1$ are on the first and last positions, and also minus the permutations which begin or end with a sequence of the form $n..n-2..n-1..n-3...$ thus $n$ and $n-1$ not being neighbors. If $\tau^{-1}(n)\nin\{1,n+1\}$ then certainly $\sigma$ was counted with the $b_n$-s. Also, from any straight permutation of $n$ elements, not having $n$ and $n-1$ in the first and last position, thus $n$ certainly being neighbor with $n-1$, we can make a straight $n+1$-element permutation by inserting $n+1$ between $n$ and $n-1$. Therefore we have obtained the following relationship: \[ b_{n+1} = a_n - 2-a_{n-3} +b_n = a_{n-1}+b_n ,\ \forall \ n\geq 4 \ \Rightarrow \] \[ b_n= a_{n-2}+a_{n-3}+\cdots + a_2 + b_3 \Rightarrow x_n = a_n + a_{n-2}+a_{n-3}+\ldots + a_2 + b_3, \ \forall \ n\geq4. \] It is obvious that $\{x_n\}_n$ is a "fast" increasing sequence, so it is easy to compute the first terms using the relationships obtained above, which will prove that the number that we are looking for is $n=16$.