mateforum.ro

Fie \( a, b \) naturale nenule si \( (a, b) =: d > 1 \).
a) Sa se arate ca exista o partitie a lui \( \mathbb{N}^{\ast} \) in doua multimi nevide \( A, \ B \) cu proprietatea \( x \in A \Rightarrow x + a \in A \) si \( y \in B \Rightarrow y + b \in B \).
b) Sa se arate ca daca \( (A, B) \) este o partitie a lui \( \mathbb{N}^{\ast} \) cu proprietatea data, atunci pentru orice \( z \in \mathbb{N}^{\ast} \), numerele \( z \) si \( z + d \) sunt ambele in \( A \) sau ambele in \( B \).

Vasile Pop, Shortlist ONM 2007, Cls. a VIII-a

a)

Fie \( A=\{x|x\equiv1(mod\ d)} \) si \( B=\{y|y\equiv2, 3, \dots ,d-1(mod\ d)} \).

Vom arata ca aceste multimi au proprietatile cerute.
Fie x un element din \( A \). Vom arata ca x+a este si el in \( A \).
De fapt este suficient sa aratam ca \( x+a\equiv1(mod \ d) \). Deoareca \( (a,b)=d \), avem ca \( a\vdots d \) deci\( x+a\equiv{x}\equiv 1(mod \ d) \) deci \( x+a \equiv 1(mod \ d) \) , asadar \( x+a \in A \).

b)

Presupunem ca \( \exists\ {z} \) astfel incat \( z \) si \( z+d \) nu sunt ambele in \( A \) sau \( B \). Atunci unul din acele numere este in \( A \), iar unul in \( B \)(Putem presupune fara a restrange generalitatea ca \( z \in A \) si \( z+d \in B \).

Vom arata ca exista un element in \( A \) care coincide cu un element din \( B \)(ceea ce, evident, este imposibil).

Este suficient sa aratam ca exista \( n_1 \) si \( n_2 \) astfel incat \( z+a.n_1=z+d+b.n_2 \Longleftrightarrow a.n_1=d+b.n_2(1) \)(primul termen este din \( A \), iar al doilea din \( B \)).

Deorece \( (a,b)=d \) avem ca exista \( k_1, \ k_2 \) cu \( (k_1,k_2)=1 \) astfel incat \( a=d.k_1 \) si \( b=d.k_2 \).
Asadar, relatia (1) devine
\( d.k_1.n_1=d+d.k_2.n_2 \Longleftrightarrow k_1.n_1=1+k_2.n_2 \).
Este suficient sa demonstram ca exista un numar natural \( n \) astfel incat \( k_2.n+1\vdots{k_1} \).
Presupunem prin absurd ca acest numar \( n \) nu exista. Atunci nici unul din numerele \( k_2+1, 2.k_2+1, \dots, (k_1-1).k_2+1 \) nu este divizibil cu \( k_1 \). Atunci ori exista un \( s \) astfel incat \( k_2.s+1\equiv 1(mod \ k_1) \), ori exista \( r_1, r_2 \) astfel incat \( k_2.r_1+1\equiv{k_2.r_2+1}(mod \ k_1) \).
Primul caz este echivalent cu faptul ca \( k_2.s\vdots{k_1} \), iar deoarece \( (k_1, k_2)=1 \), avem ca \( s\vdots k_1 \), ceea ce este fals deoarece \( 1\leq{s}\leq{k_1-1} \).
Cel de al doilea caz este echivalent cu faptul ca \( k_2.(r_1-r_2)\vdots{k_1} \)(presupunem ca \( r_1<r_2 \)). Deoarece \( (k_1, k_2)=1 \), avem ca \( r_1-r_2\vdots{k_1} \), ceea ce este fals, deoarece \( 1\leq{r_1-r_2}\leq{k_1-2} \).

Asadar, exista un numar natural \( n \) astfel incat \( k_2.n+1\vdots{k_1} \), deci exista un element in \( A \), care coincide cu un elemnt din \( B \), ceea ce evident este fals.

Deci, pentru orice \( z \) avem ca \( z \) si \( z+d \) sunt in aceeasi multime a partitiei.