Chủ đề này có 1 trả lời

[leanh9adst]

Cho một bộ số S gồm 3 số nguyên dương không nhất thiết phân biệt. Thực hiện quy tắc: chọn 2 số x,y trong đó, nếu x<=y thì thay 2 số này bằng 2x,y-x để thu được bộ mới. CMR có thể thực hiện 1 chuỗi hữu hạn quy tắc như trên để thu được một tập S' chứa số 0.

[JUV]

Với $3$ số $a,b,c$, ta sẽ thực hiện một số phép toán để giảm thực sự $min(a,b,c)$. Giả sử $a\geq b\geq c$, gọi thương của phép chia $b$ cho $c$ là $p$, số dư là $q<c$. Viết $p$ dưới dạng nhị phân là $\overline{a_1a_2...a_t}_{(2)}$, gọi $1=j_1<j_2<...<j_k$ là tất cả các số thoả mãn $a_{j_i}=1 \forall i=\overline{1,k}$. Ta sẽ thực hiện phép toán $t$ lần : Cho $3$ số $a,b,c$ vào $3$ nhóm $A,B,C$, thực hiện phép toán với $2$ số trong $B$ và $C$ tại lần $t+1-j_i \forall i=\overline{1,k}$ và trong những lần khác chọn số trong nhóm $A,C$ ($2$ số nhận được, số bé nhất vào nhóm $C$, số còn lại vào nhóm còn lại).  Sau $t$ lần ta nhận được $3$ số $a+b+c-q-2^{t}c,q,2^{t}c$ với $min(a+b+c-q-2^{t}c,q,2^{t}c)<c$ (do $q<c$). Tiếp tục làm đến khi giảm được $min(a,b,c)=0$ có $Q.E.D$

Bài viết đã được chỉnh sửa nội dung bởi JUV: 01-12-2016 - 15:48