Problema cu combinari
Moderators: Filip Chindea, Andrei Velicu, Radu Titiu
-
BogdanCNFB
- Thales
- Posts: 121
- Joined: Wed May 07, 2008 4:29 pm
- Location: Craiova
Problema cu combinari
Pentru \( n>1 \), numarul \( C_{2n}^n \) nu se divide cu 4 daca si numai daca \( n=2^m \).
Fie \( 2^m\leq n<2^{m+1}. \) Din formula lui Legendre exponentul lui \( 2 \) in \( \textrm{C}_{2n}^n \) este egal cu
\( \textrm{e}_2=\sum_{k=1}^{m+1}\lfloor\frac{2n}{2^k}\rfloor-2\sum_{k=1}^{m}\lfloor\frac{n}{2^k}\rfloor \) sau
\( \textrm{e}_2= n-\sum_{k=1}^{m}\lfloor\frac{n}{2^k}\rfloor. \)
Pe de o parte \( \sum_{k=1}^{m}\lfloor\frac{n}{2^k}\rfloor\leq\sum_{k=1}^{m}\frac{n}{2^k}=\frac{(2^m-1)}{2^m}n\leq n-1, \) deci \( \textrm{e}_2\geq 1. \)
Pe de alta parte din ipoteza \( \textrm{e}_2\leq 1 \), astfel ca obtinem \( \lfloor\frac{n}{2^k}\rfloor=\frac{n}{2^k} \forall k=1,2,...,m \) de unde \( n=2^m \) si reciproc.
\( \textrm{e}_2=\sum_{k=1}^{m+1}\lfloor\frac{2n}{2^k}\rfloor-2\sum_{k=1}^{m}\lfloor\frac{n}{2^k}\rfloor \) sau
\( \textrm{e}_2= n-\sum_{k=1}^{m}\lfloor\frac{n}{2^k}\rfloor. \)
Pe de o parte \( \sum_{k=1}^{m}\lfloor\frac{n}{2^k}\rfloor\leq\sum_{k=1}^{m}\frac{n}{2^k}=\frac{(2^m-1)}{2^m}n\leq n-1, \) deci \( \textrm{e}_2\geq 1. \)
Pe de alta parte din ipoteza \( \textrm{e}_2\leq 1 \), astfel ca obtinem \( \lfloor\frac{n}{2^k}\rfloor=\frac{n}{2^k} \forall k=1,2,...,m \) de unde \( n=2^m \) si reciproc.