Chứng minh rằng với mỗi số tự nhiên $n$ lớn hơn $1$, luôn tồn tại một tập $S$ gồm $n$ phần tử sao cho với hai phần tử $a,b$ bất kì trong $S$, $a-b|a$ và $a-b|b$ nhưng $a-b$ không là ước của bất kì số nào trong $S$ khác nữa.
$a-b|a$ và $a-b|b$
#2
Đã gửi 08-01-2016 - 18:07
Chứng minh rằng với mỗi số tự nhiên $n$ lớn hơn $1$, luôn tồn tại một tập $S$ gồm $n$ phần tử sao cho với hai phần tử $a,b$ bất kì trong $S$, $a-b|a$ và $a-b|b$ nhưng $a-b$ không là ước của bất kì số nào trong $S$ khác nữa.
Ta chứng minh bằng qui nạp. Giả sử bài toán đúng tới $n$ tức là tồn tại tập $S_{n}=\left \{ a_1,a_2,...a_{n} \right \}$ thỏa đề
Ta xây dựng tập $S_{n+1}$ như sau : Đặt $A=\prod (a_i-a_j)$ với $i,j$ chạy từ $1$ đến $n$
Với mỗi $k$ từ $1$ đến $n$ ta chọn $b_k=Aa_1a_2...a_n+a_k$ . Còn $b_{k+1}=Aa_1a_2...a_n$
Ta thấy $b_i-b_j= a_i-a_j |a_i|b_i$ và $b_i-b_j= a_i-a_j |a_j|b_j$ ; $\forall 1\leq i,j\leq n$
và $b_i-b_j$ ko là ước của $b_k$ nào nữa
Riêng $b_i-b_{n+1}= a_i |gcd(b_i,b_{n+1});\forall 1\leq i\leq n$ và cũng ko là ước của $b_k$ nào nữa.
Vậy tập $S_{n+1}=\left \{ b_1,b_2,...b_{n+1} \right \}$ thỏa đề và ta có $đpcm$
Bài viết đã được chỉnh sửa nội dung bởi Visitor: 08-01-2016 - 18:24
- Chris yang, Bui Ba Anh và Element hero Neos thích
__________
Bruno Mars
#3
Đã gửi 08-01-2016 - 20:19
Ta chứng minh bằng qui nạp. Giả sử bài toán đúng tới $n$ tức là tồn tại tập $S_{n}=\left \{ a_1,a_2,...a_{n} \right \}$ thỏa đề
Ta xây dựng tập $S_{n+1}$ như sau : Đặt $A=\prod (a_i-a_j)$ với $i,j$ chạy từ $1$ đến $n$
Với mỗi $k$ từ $1$ đến $n$ ta chọn $b_k=Aa_1a_2...a_n+a_k$ . Còn $b_{k+1}=Aa_1a_2...a_n$
Ta thấy $b_i-b_j= a_i-a_j |a_i|b_i$ và $b_i-b_j= a_i-a_j |a_j|b_j$ ; $\forall 1\leq i,j\leq n$
và $b_i-b_j$ ko là ước của $b_k$ nào nữa
Riêng $b_i-b_{n+1}= a_i |gcd(b_i,b_{n+1});\forall 1\leq i\leq n$ và cũng ko là ước của $b_k$ nào nữa.
Vậy tập $S_{n+1}=\left \{ b_1,b_2,...b_{n+1} \right \}$ thỏa đề và ta có $đpcm$
Dạ anh giải thích rõ hơn chỗ này được không ạ? Vì giả sử là ước của một $b_k$ nào đó thì $a_i|a_k$ Từ chỗ này em vẫn chưa tìm ra vô lí.
- Visitor yêu thích
#4
Đã gửi 08-01-2016 - 21:17
Dạ anh giải thích rõ hơn chỗ này được không ạ? Vì giả sử là ước của một $b_k$ nào đó thì $a_i|a_k$ Từ chỗ này em vẫn chưa tìm ra vô lí.
Ở bước quy nạp $n$ ta đã có $a_i-a_k|a_i$ , kia lại có $a_i|a_k$ nên chỉ có trường hợp duy nhất là $a_k=2a_i$
đến đây thì ta quay lại bước quy nạp $n-1$ , với những kí hiệu tương tự trên thì $a_k=2a_i\Leftrightarrow A'.a'_1.a'_2...a'_{n-1}+a'_k=2(A'.a'_1.a'_2...a'_{n-1}+a'_i)$
$\Leftrightarrow A'.a'_1.a'_2...a'_{n-1}=a'_k-2a'_i$
(lưu ý là có thể $a'_k$ hoặc $a'_i$ bằng $0$ )
Hiển nhiên vô lí
Bài viết đã được chỉnh sửa nội dung bởi Visitor: 08-01-2016 - 21:24
- Bui Ba Anh, Element hero Neos và Ego thích
__________
Bruno Mars
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh