IMC 2008 ziua 1 problema 6

[Beniamin Bogosel]

Pentru o permutare \( \sigma=(i_1...i_n) \) a lui \( (1,2,...,n) \) definim \( D(\sigma)=\sum_{k=1}^n|i_k-k| \). Fie \( Q(n,d) \) numarul permutarilor \( \sigma \) ale lui \( (1,2,...,n) \) pentru care \( D(\sigma)=d \). Demonstrati ca daca \( d\geq 2n \) atunci \( Q(n,d) \) este numar par.

IMC 2008

[Beniamin Bogosel]

Ideea de rezolvare e mai complicata, si nu se vede daca nu ai mai facut asa ceva inainte...

Se considera determinantul \( \Delta(x)=|\ x^{|i-j|}\ |_{1\leq i,j \leq n} \), adica elementul de pe linia \( i \) si coloana \( j \) este egal cu \( x^{|i-j|} \).

Folosind definitia determinantului, obtinem ca \( \Delta(x)=\sum_{\sigma \in S_n}x^{D(\sigma)}(-1)^{Inv(\sigma)} \), unde \( Inv(\sigma) \) este numarul inversunilor lui \( \sigma \).. Astfel \( Q(n,d) \) are aceeasi paritate cu coeficientul lui \( x^{d} \) in \( \Delta(x) \). \( (\circ) \).

Calculam acum in alt mod pe \( \Delta(x) \):
Pentru \( k \) de la \( n \) la 2 (descrescator) scadem din linia \( k \) linia \( k-1 \) inmultita cu \( x \). Obtinem un determinant care are pe diagonala principala \( 1-x^2 \) in afara de coltul stanga sus unde este 1[/tex] si toate elementele care nu sunt pe prima linie sau pe diagonala principala sunt 0[/tex]. Astfel, se arata simplu ca \( \Delta(x)=(1-x^2)^{n-1} \). De aici se observa clar ca pentru \( d\geq 2n \) coeficientul lui \( x^d \) in \( \Delta(x) \) este 0. Din \( (\circ) \) rezulta ca pentru \( d\geq 2n\ Q(n,d) \) este numar par.

[Laurentiu Tucaa]

Probabil se poate face mai simplu ,tot ce trebuie aratat este ca numarul permutarilor \( \sigma \) ,care au \( D(\sigma)=d\ge 2n ,\sigma^2=e \) este par .Pt ca pt o permutare \( \sigma,\sigma^2\not=e =>\sigma\not=\sigma^{-1} \) iar \( D(\sigma^{-1})=D(\sigma) \) deci pe acestea le putem grupa in cupluri de forma \( (\sigma,\sigma^{-1}) \).