Bài toán phân hoạch tập hợp các số nguyên dương thành các cấp số cộng

[HoangNhatTuan]

Không dùng hàm sinh giải bài toán này ạ:
Giả sử tập hợp các số nguyên dương được phân hoạch thành $n$ cấp số cộng có công sai là $d_1,d_2,...,d_n$. Chứng minh tồn tại $i$ khác $j$ sao cho $d_i=d_j$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[tikita]

Nguyên văn bởi HoangNhatTuan

Không dùng hàm sinh giải bài toán này ạ:
Giả sử tập hợp các số nguyên dương được phân hoạch thành $n$ cấp số cộng có công sai là $d_1,d_2,...,d_n$. Chứng minh tồn tại $i$ khác $j$ sao cho $d_i=d_j$

Bài này phải thêm giả thiết là các $d_i>1$.

Ta có thể tiếp cận bài này bằng quy nạp với phát biểu tổng quát sau: Cho tập $S$ là tập hợp tất cả các số nguyên dương của một cấp số cộng với công sai $a, (a\in\mathbb{N^*})$. Giả sử rằng $S$ được phân hoạch thành các cấp số cộng có công sai là $d_1,d_2,...,d_n$ với $d_i>a$. Chứng minh rằng tồn tại $i,j$ sao cho $d_i=d_j$.

Phương pháp tiếp cận là dùng quy nạp kết hợp với phản chứng và dùng một kết quả là: Giao của hai cấp số cộng bất kỳ hoặc là rỗng hoặc cũng là một cấp số cộng.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]