Dtth part5 booklet là tài liệu môn Toán trong chương trình Lớp 11 được cungthi.online tổng hợp và biên soạn từ các nguồn chia sẻ trên Internet. Tạo nguồn tài liệu giúp các bạn trong việc ôn luyện và học tập
Những địa chỉ uy tín để bạn mua sách
Nội dung tóm tắt
5.3. Các bài toán 137
Tóm lại ta luôn có S ≡ 1 + 1
2
+
1
3
+ ...+
1
p− 2
+
1
p− 1
(mod p)
Theo định lí Wolstenholme ta có
1 +
1
2
+
1
3
+ ...+
1
p− 2
+
1
p− 1
≡ 0 (mod p)⇒ S ≡ 0 (mod p)
⇒ S
... p
Ví dụ 5.14. Cho các số nguyên không âm i; j;n thoả mãn : i+ j ≤ n.
Chứng minh rằng:
2n−i−j
∣∣∣∣∣∣
n∑
p=0
(
n
p
)(
p
i
)(
p
j
)
4
Lời giải.
Không mất tính tổng quát giả sử i ≥ j.
Ta có:
(
n
p
)(
p
i
)(
p
j
)
=
(
n
i
)(
n− i
n− p
)(
p
j
)
Đặt Aj =
n∑
p=0
(
n
i
)(
n− i
n− p
)(
p
j
)
Xét biểu thức
F (x) =
n∑
j=0
Ajx
j
=
n∑
j=0
n∑
p=0
(
n
i
)(
n− i
n− p
)(
p
j
)
xj
=
(
n
i
) n∑
p=0
(
n− i
n− p
) n∑
j=0
(
p
j
)
xj
=
(
n
i
) n∑
p=0
(
n− i
n− p
)
(1 + x)p
Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học
138 5.3. Các bài toán
=
(
n
i
)
(1 + x)n
n∑
p=0
(
n− i
n− p
)
1
(1 + x)n−p
=
(
n
i
)
(1 + x)n
(
1 +
1
1 + x
)n−i
=
(
n
i
)
(1 + x)i(2 + x)n−i
Vậy F (x) =
(
n
i
)
(1 + x)i(2 + x)n−i và Aj là hệ số của xj trong khai
triển của F (x).
Dễ thấy là hệ số của các đơn thức của x có bậc bé hơn j trong khai
triển (2 + x)n−i đều chia hết cho 2n−i−j
Do đó 2n−i−j |Aj . Đây là đpcm.
Ví dụ 5.15 (Australia MO). Tìm giá trị k tự nhiên nhỏ nhất sao cho
số
∀n ≥ m : k
m+ n+ 1
(
2n
n+m
)
∈ N
4
Lời giải.
Trước hết ta chứng minh
1
m+ 1
(
2m
m
)
∈ Z
Ta có:
1
m+ 1
(
2m
m
)
=
(
1− m
m+ 1
)(
2m
m
)
=
(
2m
m
)
− (2m)!
(m− 1)!(m+ 1)!
=
(
2m
m
)
− (2m)!
(m− 1)!(m+ 1)!
=
(
2m
m
)
−
(
2m
m− 1
)
∈ Z
Giả sử cho trước số m ∈ N. Vì với n = m, số k
m+ n+ 1
(
2n
n+m
)
=
k
2m+ 1
phải là số tự nhiên nên giá trị phải tìm k ∈ N phải chia hết
cho 2m+ 1, vì thế k ≥ 2m+ 1.
Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp
Tài liệu tham khảo
[1] http://diendantoanhoc.net/forum/
[2] http://www.artofproblemsolving.com/
[3] http://www.math.net.vn
[4] http://forum.mathscope.org/
[5] 102 Combinatorial Problems, Titu Andreescu, Zuming Feng
171
170 6.5. Bài tập
Bài 2. Chứng minh rằng với mọi số tự nhiên n ≥ 1 chúng ta có:
n∑
r=1
r
(
n
r
)2
= n
(
2n− 1
n− 1
)
.
Bài 3. (IMO 1989) Cho n, k là các số nguyên dương và S là tập hợp
gồm n điểm trên mặt phẳng thỏa mãn:
(1) Không có ba điểm nào thuộc tập S thẳng hàng.
(2) Với mỗi điểm P thuộc tập S thì có ít nhất k điểm thuộc S
cách đều với điểm P.
Chứng minh rằng: k <
1
2
+
√
2n
Bài 4. (IMC 2002) Trong một cuộc thi toán học có 200 sinh viên tham
dự. Họ được đề nghị giải 6 bài toán và mỗi bài toán được giải
đúng bởi ít nhất 120 sinh viên . Chứng minh rằng luôn có hai
sinh viên mà với mỗi bài toán thì ít nhất một trong hai thí sinh
này giải đúng bài toán đó.
Bài 5. Chứng minh rằng:
∑ k!
k1!k2!...kn!
= nk, trong đó bộ (k1, k2, ..., kn)
thỏa mãn k1 + k2 + ...+ kn = k.
Bài 6. Cho m;n là những số nguyên không âm . Chứng minh rằng :
E(m;n) =
n∑
k=0
(−1)k
(
n
k
)(
m− k
m− k − n
)
= 1
Với m ≥ 2n
Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp
5.3. Các bài toán 139
Giả sử k = 2m + 1, thế thì với n = m, số dương
k
n+m+ 1
(
n+m
2n
)
là số tự nhiên và với n > m nó bằng
2m+ 1
n+m+ 1
(
2n
n+m
)
=
(
1− n−m
n+m+ 1
)(
2n
n+m
)
=
(
2n
n+m
)
− (2n)!
(n+m+ 1)!(n−m− 1)!
=
(
2
n+m
)
−
(
2n
n+m+ 1
)
∈ Z
Vậy giá trị k nhỏ nhất bằng 2m+ 1.
Ví dụ 5.16 (T8/419-THTT). Tìm tất cả các cặp số nguyên dương n, k
thỏa mãn điều kiện (
3n
n
)
= 3n.nk
4
Lời giải.
Ta có: (
3n
n
)
= 3n.nk
⇔ (3n)!
n!(2n)!
= 3n.nk
⇔ (3n− 2)!(3n− 1).3n
2n2(n− 1)!(2n− 1)!
= 3n.nk
⇔ (3n− 2)!
(n− 1)!(2n− 1)!
=
2.3n−1nk+1
3n− 1
Vì
(3n− 2)!
(n− 1)!(2n− 1)!
=
(
3n− 2
n− 1
)
∈ Z⇒ 2.3n−1.nk+1
... 3n− 1 (5.4)
Lại có (3, 3n− 1) = 1 và (n, 3n− 1) = 1 nên từ (5.4) suy ra
2
... 3n− 1⇒ 3n− 1 ≤ 2⇒ n ≤ 1
Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học
140 5.3. Các bài toán
Do đó n = 1. Ta được
(
3n
n
)
= 3n.nk ⇔
(
3
1
)
= 3.1k
Đẳng thức này thỏa mãn với mọi số k nguyên dương.
Vậy cặp số (n, k) cần tìm là (1, k) với k là số nguyên dương bất kì.
Nhận xét. Có thể giải bài toán này bằng cách khác như sau:
Với n = 1, ta có kết quả như trên; với n ≥ 2, bằng quy nạp ta chứng
minh rằng
(
3n
n
)
6
... 3n nên bài toán không thỏa mãn.
Ví dụ 5.17 (IMO 1974). Chứng minh rằng với mọi số nguyên dương
n thì
n∑
k=0
(
2n+ 1
2k + 1
)
23k 6
... 5
4
Lời giải (1).
Ta có:
n∑
k=0
(
2n+ 1
2k + 1
)
23k =
n∑
k=0
(
2n+ 1
2k
)
23(n−k)
Mặt khác vì 16 chia 5 dư 1 nên ta có:
23(n−i) ≡ 1
2n−i
=
2i
2n
(mod 5)
Suy ra 2n.
n∑
k=0
(
2n+ 1
2k + 1
)
.23k ≡ S2n+1 (mod 5)
với S2n+1 =
n∑
k=0
(
2n+ 1
2k
)
2i
Do vậy, giờ ta sẽ đi tính S2n+1 =
n∑
k=0
(
2n+ 1
2k
)
2i
Xét hàm sinh f(x) = (1 + x
√
2)2n+1 =
2n+1∑
i=0
(
i
2n+ 1
)
2i,theo định lí
RUF thì:
S2n+1 =
1
2
(f(1) + f(−1)) = 1
2
(
(1 +
√
2)2n+1 + (1−
√
2)2n+1
)
Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp
6.5. Bài tập 169
Để ý rằng 0 = (1− 1)r =
r∑
i=0
(−1)i
(
r
i
)
= 1−
r∑
i=1
(−1)i−1
(
r
i
)
.
Vậy chúng ta có
r∑
i=1
(−1)i−1
(
r
i
)
= 1, tức là x được đếm 1 lần ở
vế phải.
Vậy nguyên lí bù trừ được chứng minh.
Nhận xét.
Qua một số bài toán và ví dụ ở trên các bạn có thể thấy, phương pháp
đếm bằng hai cách được diễn tả bằng ngôn ngữ hoàn toàn dễ hiểu.
Bằng cách đó chúng ta có thể áp dụng giải được nhanh gọn một số bài
toán mà các phương pháp khác tỏ ra kém hữu hiệu và phức tạp hơn.
Bên cạnh ưu điểm trên thì phương pháp đếm bằng hai cách cũng có
