Problema 4 ONM 2007
Posted: Mon May 19, 2008 4:52 pm
a) Pentru o multime finita de numere naturale \( S \) se noteaza cu \( S+S \) multimea tuturor sumelor \( x+y \) cu \( x,y \in S \). Fie \( m=|S| \), cardinalul lui \( S \). Aratati ca
\( |S+S|\leq \frac{m(m+1)}{2} \)
b) Fie m un numar intreg strict pozitiv. Notam cu \( C(m) \) cel mai mare numar intreg \( k \geq 1 \), pentru care exista o multime \( S \), formata din exact \( m \) numere intregi, astfel incat \( \{1,2,\ldots,k\}\subseteq S\cup(S+S) \). De exemplu \( C(3)=8 \), cu \( S=\lbrace1,3,4} \). Aratati ca
\( \frac{m(m+6)}{4}\leq C(m) \leq \frac{m(m+3)}{2} \).
\( |S+S|\leq \frac{m(m+1)}{2} \)
b) Fie m un numar intreg strict pozitiv. Notam cu \( C(m) \) cel mai mare numar intreg \( k \geq 1 \), pentru care exista o multime \( S \), formata din exact \( m \) numere intregi, astfel incat \( \{1,2,\ldots,k\}\subseteq S\cup(S+S) \). De exemplu \( C(3)=8 \), cu \( S=\lbrace1,3,4} \). Aratati ca
\( \frac{m(m+6)}{4}\leq C(m) \leq \frac{m(m+3)}{2} \).