Fie \( n \) intreg, \( n \geq 2. \) Determinati multimile \( A \) de \( n \) numere intregi cu proprietatea ca suma elementelor oricarei parti nevide a lui \( A \) nu se divide cu \( n+1 \).
Dan Schwarz
[Mod edit: aceasta se muta la teoria numerelor (aditiva)]
Romanian TST I 2008, Problema 1
Moderators: Laurian Filip, Filip Chindea, maky, Cosmin Pohoata
-
Laurian Filip
- Site Admin
- Posts: 344
- Joined: Sun Nov 25, 2007 2:34 am
- Location: Bucuresti/Arad
- Contact:
-
Beniamin Bogosel
- Co-admin
- Posts: 710
- Joined: Fri Mar 07, 2008 12:01 am
- Location: Timisoara sau Sofronea (Arad)
- Contact:
Fie \( A=\{x_1,x_2,...,x_n\} \). Luam doua elemente \( x_i,x_j \) diferite din \( A \). Consideram submultimile lui \( A
A_1=\{x_i\}, A_1^\prime=\{x_j\} \\
A_2=\{x_i,x_j\} \\ \) si \( A_3,...,A_n \) astfel incat \( A_1,A_1^\prime \subset A_2\subset ...\subset A_n=A \) cu \( |A_i|=i, \text{ cu } i=1..n \)
Atunci oricare doua submultimi \( A_k,A_l \) distincte au sumele diferite modulo \( n+1 \), pentru ca altfel diferenta lor, care este nevida ar forma o submultime cu suma divizibila cu \( n+1 \). Cum sunt \( n \) resturi diferite de 0 rezulta ca fiecare submultime \( A_k \) are cate unul dintre aceste resturi. Astfel \( A_1,A_1^\prime \) au sumele cu acelasi rest modulo \( n+1 \). Deci \( x_i\equiv x_j (\rm{mod } n+1) \)
Deci toate elementele lui \( A \) au acelasi rest modulo \( n+1 \). Fie \( 1\leq k \leq n \) acest rest. Atunci \( pk \) nu este divizibil cu \( n+1 \) pentru \( p=1..n \). Daca \( (k,n+1)=d\neq 1 \), atunci \( p=\frac{n+1}{d}<n+1 \) si \( kp=\frac{k(n+1)}{d}\equiv 0 (\text{mod } n+1) \), ceea ce nu convine. Deci \( (k,n+1)=1 \).
Astfel \( A=\{x_i\in \mathbb{Z},\ i=1..n \ | \ x_i\equiv k (\text{mod } n+1) \text{ cu }(k,n+1)=1\} \). E usor sa se verifice ca toate aceste multimi verifica enuntul.
A_1=\{x_i\}, A_1^\prime=\{x_j\} \\
A_2=\{x_i,x_j\} \\ \) si \( A_3,...,A_n \) astfel incat \( A_1,A_1^\prime \subset A_2\subset ...\subset A_n=A \) cu \( |A_i|=i, \text{ cu } i=1..n \)
Atunci oricare doua submultimi \( A_k,A_l \) distincte au sumele diferite modulo \( n+1 \), pentru ca altfel diferenta lor, care este nevida ar forma o submultime cu suma divizibila cu \( n+1 \). Cum sunt \( n \) resturi diferite de 0 rezulta ca fiecare submultime \( A_k \) are cate unul dintre aceste resturi. Astfel \( A_1,A_1^\prime \) au sumele cu acelasi rest modulo \( n+1 \). Deci \( x_i\equiv x_j (\rm{mod } n+1) \)
Deci toate elementele lui \( A \) au acelasi rest modulo \( n+1 \). Fie \( 1\leq k \leq n \) acest rest. Atunci \( pk \) nu este divizibil cu \( n+1 \) pentru \( p=1..n \). Daca \( (k,n+1)=d\neq 1 \), atunci \( p=\frac{n+1}{d}<n+1 \) si \( kp=\frac{k(n+1)}{d}\equiv 0 (\text{mod } n+1) \), ceea ce nu convine. Deci \( (k,n+1)=1 \).
Astfel \( A=\{x_i\in \mathbb{Z},\ i=1..n \ | \ x_i\equiv k (\text{mod } n+1) \text{ cu }(k,n+1)=1\} \). E usor sa se verifice ca toate aceste multimi verifica enuntul.
Mai jos este schita solutiei mele de la baraj, asemanatoare cu cea de mai sus.
Fie \( A=\{a_1,a_2,\cdots,a_n\} \) o multime care verifica ipoteza. Consideram sumele
\( a_1 \)
\( a_1+a_2 \)
\( \vdots \)
\( a_1+a_2+...a_n \)
Daca exista 2 sume de mai sus congruente intre ele modulo \( n+1 \) e clar ca diferenta lor, care e tot o suma de \( a_i \)-uri va fi divizibila cu \( n+1, \) imposibil. Deci aceste sume sunt egale modulo \( n+1 \) cu \( \{1,2,...,n\} \) (niciuna din ele nu se poate divide cu 0). Sa il luam pe \( a_2 \) si prespunem ca \( a_2\neq a_1 \pmod{n+1} \). Atunci \( a_2 \) este congruent modulo \( n+1 \) cu una din celelalte sume de mai sus. Dar diferenta lor va fi ceva de forma \( a_1+a_3+...+a_i \) divizibila cu \( n+1, \) contradictie. Deci \( a_2=a_1\pmod{n+1}. \) La fel vom considera sumele \( a_2, a_2+a_3,...,a_2+a_3+...+a_n+a_1 \) si analog ca mai sus \( a_3=a_2\pmod{n+1} \) ... si sumele \( a_n, a_n+a_1,\cdots , a_n+\cdots +a_{n-1} \) si cu acelasi rationament se obtine ca \( a_1=a_2=\cdots=a_n=r\pmod{n+1}, \) \( 1\leq r\leq n. \)
Si de aici cazul \( (n+1,r)> 1 \) conduce la o contradictie si ramane concluzia de mai sus.
Fie \( A=\{a_1,a_2,\cdots,a_n\} \) o multime care verifica ipoteza. Consideram sumele
\( a_1 \)
\( a_1+a_2 \)
\( \vdots \)
\( a_1+a_2+...a_n \)
Daca exista 2 sume de mai sus congruente intre ele modulo \( n+1 \) e clar ca diferenta lor, care e tot o suma de \( a_i \)-uri va fi divizibila cu \( n+1, \) imposibil. Deci aceste sume sunt egale modulo \( n+1 \) cu \( \{1,2,...,n\} \) (niciuna din ele nu se poate divide cu 0). Sa il luam pe \( a_2 \) si prespunem ca \( a_2\neq a_1 \pmod{n+1} \). Atunci \( a_2 \) este congruent modulo \( n+1 \) cu una din celelalte sume de mai sus. Dar diferenta lor va fi ceva de forma \( a_1+a_3+...+a_i \) divizibila cu \( n+1, \) contradictie. Deci \( a_2=a_1\pmod{n+1}. \) La fel vom considera sumele \( a_2, a_2+a_3,...,a_2+a_3+...+a_n+a_1 \) si analog ca mai sus \( a_3=a_2\pmod{n+1} \) ... si sumele \( a_n, a_n+a_1,\cdots , a_n+\cdots +a_{n-1} \) si cu acelasi rationament se obtine ca \( a_1=a_2=\cdots=a_n=r\pmod{n+1}, \) \( 1\leq r\leq n. \)
Si de aici cazul \( (n+1,r)> 1 \) conduce la o contradictie si ramane concluzia de mai sus.