Page 1 of 1
Cristian Calude, Problema 2.
Posted: Thu Nov 06, 2008 11:05 pm
by Laurian Filip
a) Fie M multimea matricelor patratice simetrice de ordinul n \( ( n \in \mathbb{N}^*, n\geq 2 ) \) cu proprietatea ca au toate elementele egale cu 3 sau -3, iar produsul elementelor de pe diagonala principala este \( -3^n \). Sa se afle n pentru care numarul elementelor multimii M este mai mic decat 2008.
b) Fie \( S_n \) multimea permutarilor de ordinul n, unde \( n \in \mathbb{N}^* \). Sa se arate ca:
i) \( \sum_{\sigma \in S_n}m(\sigma)=\frac{n!}{2} \cdot C_n^2 \), \( \forall n \geq 2 \).
ii) \( \sum_{\sigma \in A_n}m(\sigma)=\sum_{\sigma \in S_n-A_n}m(\sigma)=\frac{n!}{4} \cdot C_n^2 \), \( \forall n\geq4 \).
(Am notat cu \( m(\sigma) \) numarul inversiunilor permutarii \( \sigma \) si \( A_n \) multimea permutarilor pare din \( S_n \))
Re: Cristian Calude, Problema 2.
Posted: Sun Nov 23, 2008 10:52 pm
by Theodor Munteanu
\(
\[
\displaylines{
{\rm Pentru n = 2k: avem pe diagonala principala un numar impar de numere } \cr
{\rm egale cu - 3}{\rm .} \cr
{\rm Astfel putem avea 1,3,5,}...{\rm ,2k - 1numere egale cu - 3}{\rm .} \cr
{\rm Pentru 2i + 1 numere,din formula perm cu repetitii avem } \cr
\frac{{{\rm (2k)!}}}{{{\rm (2i + 1)!(2k - (2i + 1))!}}} = C_{2k}^{2i + 1} ,i = \overline {1,k - 1} {\rm deci din regula sumei} \cr
{\rm avem}\sum\limits_{{\rm i = 1}}^{{\rm k - 1}} {{\rm C}_{{\rm 2k}}^{{\rm 2i + 1}} } = 2^k {\rm posibilitati}{\rm .} \cr
{\rm Independent de aceasta putem alege pt numerele de sub diag principala} \cr
{\rm (care sunt }\frac{{{\rm n(n - 1)}}}{{\rm 2}})\sum\limits_{i = 1}^{\frac{{n(n - 1)}}{2}} {C_{\frac{{n(n - 1)}}{2}}^i } = 2^{\frac{{n(n - 1)}}{2}} ; \cr
{\rm Astfel din regula produsului avem 2}^{\frac{{\rm n}}{{\rm 2}}} \cdot 2^{\frac{{n(n - 1)}}{2}} = 2^{\frac{{n^2 }}{2}} {\rm moduri de alegere ale lui} \cr
{\rm 3 si - 3 adica tot atatea matrici}{\rm .} \cr
{\rm Acum 2}^{\frac{{{\rm n}^{\rm 2} }}{2}} \le 2008 \Leftrightarrow \frac{{n^2 }}{2} \le [\log _2 2008] = 10{\rm deci n} \le {\rm 4 deci n = 2,n = 4}{\rm .} \cr
{\rm Pentru n impar procedam analog si gasim n = 1,n = 3}{\rm .} \cr}
\]
\)
La punctul b)
Posted: Sun Nov 23, 2008 11:04 pm
by Theodor Munteanu
Fie \( \sigma \in S_n,\tau \in S_n \) cu \( \tau(k)=\sigma(n-k+1)
\sigma(i)>\sigma(j) \leftrightarrow \tau(n-i+1)>\tau(n-j+1) \) si n-i+1>n-j+1 deci \( \m(\sigma)+m(\tau)=C_n^2=\frac{n(n-1)}{2} \)
Deci \( \sum_{\sigma \in S_n}m(\sigma)=\frac{n!}{2} \cdot C_n^2 \)
ii)Din faptul ca avem un numar de permutari pare egal cu cel de permutari impare rezulta concluzia.