Fie \( n \in \mathbb{N} \), \( n \ge 6 \). Aratati ca \( A = \{1,...,n\} \) se poate partitiona în \( 3 \) multimi cu acelasi numar de elemente si aceeasi suma a elementelor daca si numai daca \( 3|n \).
Olimpiada Judeteana 2008
Partitie cu aceeasi suma a elementelor
Moderators: Laurian Filip, Beniamin Bogosel, Filip Chindea
-
Filip Chindea
- Newton
- Posts: 324
- Joined: Thu Sep 27, 2007 9:01 pm
- Location: Bucharest
Partitie cu aceeasi suma a elementelor
Life is complex: it has real and imaginary components.
Problema este cunoscuta.
Faptul ca \( n \vdots 3 \) e cat se poate de clar. Acum pentru \( n=6k \) si \( n=6k+3 \) sa construim submultimi care sa respecte ipoteza. Vom construi inductiv submultimi pentru \( n=6k \) si \( n=6k+3 \) adaugand repetat cate 6 elemente. Pentru \( A=\{1,2,...,6\} \) facem partitia \( M=\{1,6\},N=\{2,5\},P=\{3,4\}. \) Apoi, prin inductie dupa \( k, \) \( A=\{1,2,...,6k\} \) se poate partitiona in 3 submultimi disjuncte \( M,N,P \) ai \( |M|= |N|=|P| \) si \( S_{M}=S_{N}=S_{P}. \) Adugam elementele \( 6k+1,6k+2,...,6k+6. \) Avem \( 6k+1+6k+6=6k+2+6k+5=6k+3+6k+4. \) Punem elementele \( 6k+1,6k+6 \) in \( M, \) \( 6k+2,6k+5 \) in \( N \) si \( 6k+3,6k+4 \) in \( P. \) Suma elementelor ramane egala, cardinalul creste cu 2 si am realizat deci o partitie ca in enunt si pentru \( A=\{1,2,...,6k+6\}. \)Analog se trateaza cazul \( n=6k+3, \) unde pentru \( n=9 \) putem partitiona multimea \( A=\{1,2,...,9\} \) in \( M=\{1,5,9\},N=\{2,6,7\},P=\{3,4,8\}. \)(Am notat prin \( S_{X} \) suma elementelor multimii nevide \( X \))
Faptul ca \( n \vdots 3 \) e cat se poate de clar. Acum pentru \( n=6k \) si \( n=6k+3 \) sa construim submultimi care sa respecte ipoteza. Vom construi inductiv submultimi pentru \( n=6k \) si \( n=6k+3 \) adaugand repetat cate 6 elemente. Pentru \( A=\{1,2,...,6\} \) facem partitia \( M=\{1,6\},N=\{2,5\},P=\{3,4\}. \) Apoi, prin inductie dupa \( k, \) \( A=\{1,2,...,6k\} \) se poate partitiona in 3 submultimi disjuncte \( M,N,P \) ai \( |M|= |N|=|P| \) si \( S_{M}=S_{N}=S_{P}. \) Adugam elementele \( 6k+1,6k+2,...,6k+6. \) Avem \( 6k+1+6k+6=6k+2+6k+5=6k+3+6k+4. \) Punem elementele \( 6k+1,6k+6 \) in \( M, \) \( 6k+2,6k+5 \) in \( N \) si \( 6k+3,6k+4 \) in \( P. \) Suma elementelor ramane egala, cardinalul creste cu 2 si am realizat deci o partitie ca in enunt si pentru \( A=\{1,2,...,6k+6\}. \)Analog se trateaza cazul \( n=6k+3, \) unde pentru \( n=9 \) putem partitiona multimea \( A=\{1,2,...,9\} \) in \( M=\{1,5,9\},N=\{2,6,7\},P=\{3,4,8\}. \)(Am notat prin \( S_{X} \) suma elementelor multimii nevide \( X \))
Last edited by mumble on Mon Mar 10, 2008 8:28 pm, edited 1 time in total.