ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
---------------------------

HOÀNG THÚY HOA

VẬN DỤNG PHƢƠNG PHÁP ĐA THỨC
VÀO MỘT SỐ BÀI TOÁN TỔ HỢP
Chuyên ngành: Phƣơng pháp Toán sơ cấp
Mã số: 8 46 01 13

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. TRỊNH THANH HẢI

THÁI NGUYÊN - 2022


i

Mục lục
Bảng ký hiệu

ii

Mở đầu

1

Chương 1. Kiến thức cơ sở

1.1 Đại cương về đa thức . . . . . . . . . . . . . . . . . .
1.2 Phép chia hết các đa thức, phép modulo số nguyên tố
1.3 Nghiệm của đa thức . . . . . . . . . . . . . . . . . . .
1.4 Hệ số tổ hợp trong một số định lý và ví dụ . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


3
3
4
6
10

Chương 2. Vận dụng phương pháp đa thức vào giải toán tổ hợp 16
2.1 Vận dụng phương pháp đa thức vào giải tốn tìm các tập con
của một tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Vận dụng phương pháp đa thức vào giải một số bài tốn tổ hợp
có yếu tố truy hồi . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Định lý không điểm và ứng dụng vào bài toán tổ hợp . . . . . . 31
2.4 Một số bài toán thi Olympic . . . . . . . . . . . . . . . . . . . 38
Kết luận

46

Tài liệu tham khảo

47


ii

Bảng ký hiệu
K[x]
K[x1 , x2 , . . . , xn ]
.
f (x)..g(x)


f (x) ≡ g(x) (mod p)
deg f
rk (B)
rB (x)
|A|
|s∧ A|
Cnk
∆
∆x
∆m
x

Vành đa thức biến x trên trường K
Vành đa thức n biến trên trường K
Đa thức f (x) chia hết cho đa thức g(x)
Đa thức f (x) đồng dư với g(x) modulo p
Bậc của đa thức f
Số cách xếp k quân xe lên bảng B
Đa thức xe của bảng B
Lực lượng của tập A
Tập tất cả các tổng gồm s phần tử của A
Hệ số tổ hợp chập k của n phần tử
Sai phân
Sai phân theo biến x
Sai phân cấp m theo biến x


1

Mở đầu

1. Lý do chọn đề tài
Đa thức là một khái niệm phổ thơng nhưng đóng vị trí rất quan trọng khơng
những chỉ trong chương trình tốn học phổ thơng mà cịn có rất nhiều ứng dụng
trong nhiều lĩnh vực khác như: hình học, đại số, lý thuyết hàm, . . . , trong đó
có lĩnh vực tốn tổ hợp.
Trong phạm vi tốn phổ thơng, ứng dụng đa thức trong toán tổ hợp là lĩnh
vực thú vị, được nhiều thầy cơ giáo quan tâm, ví dụ như: Trần Nam Dũng
- Trường Đại học Khoa học tự nhiên - Đại học Quốc gia Tp Hồ Chí Minh,
Văn Phú Quốc - giáo viên trường THPT chuyên Nguyễn Bỉnh Khiêm, Quảng
Nam,... Nhiều bài tốn điển hình về tổ hợp trong các kỳ thi Olympic có thể
được giải bằng phương pháp đa thức, thậm chí có bài tốn chỉ có cách giải
bằng đa thức (xem nhận xét sau Bài toán 2.3.1).
Trong phạm vi luận văn, luận văn quan niệm về Phương pháp đa thức trong
giải tốn có thể hiểu một cách trực quan là ta vận dụng khái niệm, tính chất
của một đa thức cũng như các tính chất của lý thuyết đa thức vào giải quyết
một số bài tốn sơ cấp, trong đó có các bài tốn tổ hợp.

2. Mục tiêu của luận văn
Nghiên cứu tìm hiểu và vận dụng phương pháp đa thức vào giải một số bài
tập về tổ hợp.


2

3. Nhiệm vụ nghiên cứu
Luận văn có các nhiệm vụ chính sau:
Nghiên cứu các tính chất của đa thức, bài toán xác định đa thức . . .
Nghiên cứu các tài liệu tham khảo để tìm hiểu về phương pháp đa thức
trong việc giải các bài tốn tổ hợp.
Tìm hiểu, sưu tầm một hệ thống các bài toán tổ hợp mà các bài tốn này

có thể vận dụng phương pháp đa thức để giải quyết.
Trình bày tường minh lời giải một số bài toán tổ hợp theo hướng vận dụng
phương pháp đa thức.

4. Cấu trúc của luận văn
Ngoài phần mở đầu, kết luận tài liệu tham khảo, luận văn dự kiến gồm 2
chương:
Chương 1. Kiến thức cơ sở
Nội dung của chương 1 chủ yếu sẽ trình bày vắn tắt về khái niệm đa thức,
một số tính chất cơ bản của đa thức và một số định lý về hệ số nhị thức trong
tổ hợp.
Chương 2 Vận dụng phương pháp đa thức vào giải toán tổ hợp
Chương này sẽ áp dụng phương pháp đa thức vào các bài toán đếm tổ hợp
như bài tốn tìm các tập con của tập hợp, bài tốn đếm có yếu tố truy hồi, bài
tốn có ứng dụng định lý không điểm và sưu tầm một số bài toán tổ hợp trong
các kỳ thi học sinh giỏi.


3

Chương 1
Kiến thức cơ sở
1.1

Đại cương về đa thức

Định nghĩa 1.1.1. Đa thức một biến là biểu thức có dạng
(1.1)

f (x) = an xn + an−1 xn−1 + . . . + a1 x + a0


trong đó ai ∈ K, i = 1, 2, ..., n, được gọi là các hệ số, an 6= 0 được gọi là hệ số

cao nhất, a0 được gọi là số hạng tự do, x được gọi là biến của đa thức. Bậc
của đa thức f (x) là số mũ cao nhất của lũy thừa có mặt trong (1.1) và được
ký hiệu là deg(f ).
Nếu các hệ số của đa thức f (x) dạng (1.1) là các số nguyên, số hữu tỷ,

số thực hay số phức, thì ta nói f (x) là đa thức tương ứng thuộc trường số
nguyên, trường số hữu tỷ, trường số thực hay trường số phức và tương ứng viết

f (x) ∈ Z[x], f (x) ∈ Q[x], f (x) ∈ R[x], f (x) ∈ C[x].
Định nghĩa 1.1.2. Hai đa thức P (x) =

m
X
k=0

k

ak x , Q(x) =

n
X

bk xk được gọi là

k=0

bằng nhau khi và chỉ khi n = m, ak = bk , ∀k = 0, 1, . . . , m.


Định nghĩa 1.1.3. Đa thức có tất cả các hệ số của nó bằng khơng được gọi
là đa thức khơng. Đa thức bậc khơng cịn được gọi là đa thức hằng.


4
Định nghĩa 1.1.4 (Phép cộng, trừ đa thức). Cho hai đa thức P (x) =

Q(x) =

n
X

m
X

ak xk ,

k=0

bk xk . Khi đó phép cộng và trừ các đa thức P (x), Q(x) được thực

k=0

hiện theo từng hệ số của xk , tức là
max{m,n}

X

P (x) ± Q(x) =


k=0

(ak ± bk )xk .

Định nghĩa 1.1.5 (Phép nhân đa thức). Cho hai đa thức P (x) =

Q(x) =

n
X

m
X

ak x k ,

k=0

bk xk . Khi đó phép nhân đa thức P (x)Q(x) là một đa thức

k=0

R(x) =

m+n
X

k


rk x , rk =

k=0

k
X

ai bk−i .

i=0

Định nghĩa 1.1.6. Đa thức n biến x1 , x2 , . . . , xn là một tổng hữu hạn gồm
các đơn thức dạng

axr11 xr22 · · · xrnn
trong đó a là hệ số, ri , i = 1, 2, . . . , n, là các số nguyên không âm. Ký hiệu
K[x1 , x2 , . . . , xn ] là tập các đa thức n biến x1 , x2 , . . . , xn trên trường K.
Bậc của đơn thức axr11 xr22 · · · xrnn là r1 + r2 + · · · + rn và bậc của đa thức là

bậc đơn thức lớn nhất trong các số hạng của nó.

1.2

Phép chia hết các đa thức, phép modulo số nguyên tố

Định nghĩa 1.2.1. Cho hai đa thức P (x) và Q(x). Ta nói rằng đa thức P (x)
.
chia hết cho đa thức Q(x) và viết P (x)..Q(x), nếu tồn tại đa thức S(x), sao cho

P (x) = S(x)Q(x). Trong trường hợp này ta cũng nói đa thức Q(x) chia hết

đa thức P (x) và là ước của P (x), còn đa thức P (x) là bội của đa thức Q(x).


5
Định nghĩa 1.2.2. Cho các đa thức P (x), Q(x) và S(x). Nếu P (x) = S(x)Q(x),
thì ta nói đa thức P (x) phân tích được thành nhân tử của các đa thức Q(x)
và S(x).
Ví dụ 1.2.3. Phân tích thành nhân tử:
a) 6x5 − 15x4 + 20x3 − 15x3 + 6x − 1.

b) x4 − 6x3 + 11x2 − 6x + 1.

Chứng minh. a) Khai triển nhị thức Newton

(x − 1)6 = x6 − 6x5 + 15x4 − 20x3 + 15x3 − 6x + 1.
Do đó

6x5 − 15x4 + 20x3 − 15x3 + 6x − 1
= x6 − (x − 1)6

= [x3 − (x − 1)3 ][x3 + (x − 1)3 ]

= [x2 + x(x − 1) + (x − 1)2 ][(2x − 1)(x2 − x(x − 1) + (x − 1)2 ]
= (3x2 − 3x + 1)(2x − 1)(x2 − x + 1).

b) Ta có

x4 − 6x3 + 11x2 − 6x + 1 = (x4 − 6x3 + 9x2 ) + (2x2 − 6x) + 1
= (x2 − 3x)2 + 2(x2 − 3x) + 1
= (x2 − 3x + 1)2


Định nghĩa 1.2.4 ([4]). Cho p là một số nguyên tố, cho f (x) và g(x) là hai
đa thức hệ số nguyên. Ta nói f (x) đồng dư với g(x) theo modulo p và viết

f (x) ≡ g(x) (mod p) nếu tất cả các hệ số của đa thức f (x) − g(x) chia hết
cho p.


6
Từ định nghĩa trên ta dễ dàng suy ra:
a) f (x) ≡ f (x) (mod p).

b) Nếu f (x) ≡ g(x) (mod p) thì g(x) ≡ f (x) (mod p).

c) Nếu f (x) ≡ g(x) (mod p) và g(x) ≡ h(x) (mod p) thì f (x) ≡ h(x)

(mod p).

d) Nếu f1 (x) ≡ g1 (x) (mod p) và f2 (x) ≡ g2 (x) (mod p) thì

f1 (x) ± f2 (x) ≡ g1 (x) ± g2 (x)

(mod p)

và

f1 (x)f2 (x) ≡ g1 (x)g2 (x)

(mod p).


Ví dụ 1.2.5. Ta có

3x3 + 5x2 + 6x + 7 ≡ 2x2 + 4

(mod 3),

4x2 + 2x + 1 ≡ x2 − x − 2

1.3

(mod 3).

Nghiệm của đa thức

Nghiệm của đa thức đóng một vai trị quan trọng trong việc nghiên cứu các
tính chất của đa thức. Nhiều tính chất của đa thức được thể hiện qua nghiệm
của chúng. Ngược lại, việc nghiên cứu tính chất các nghiệm của đa thức cũng
cũng là một trong các vấn đề trung tâm của đại số.
Định nghĩa 1.3.1. Số α là nghiệm của đa thức Pn (x), nếu Pn (α) = 0.
Định lý 1.3.2 (Định lý Bezout). Đa thức P (x) chia hết cho x − a khi và chỉ
khi số a là nghiệm của đa thức P (x).

.
Chứng minh. Giả sử P (x)..(x − a). Khi đó ta có P (x) = (x − a)Q(x), trong đó

Q(x) là đa thức nào đó. Thay x = a, ta được P (a) = (a − a)Q(a) = 0. Vậy a
là một nghiệm của P (x).

Đảo lại, giả thiết a là một nghiệm của P (x). Giả thiết P (x) có dạng


P (x) = an xn + an−1 xn−1 + . . . + a1 x + a0 .


7
Ta có
(1.2)

P (x) = P (x) − P (a)

= an (xn − an ) + an−1 (xn−1 − an−1 ) + . . . + a1 (x − a)
= (x − a)[an (xn−1 + xn−2 a + . . . + xan−1 + an−1 )

+ an−1 (xn−2 + xn−3 a + . . . + xan−2 + an−2 ) + . . . + a1 ].

(1.3)

Do an 6= 0, nên biểu thức bên trong dấu [. . .] của biểu thức (1.3) ở trên là đa

thức bậc n − 1. Ký hiệu đa thức này là Q(x). Khi đó (1.3) có dạng

P (x) = (x − a)Q(x).

.
Đẳng thức này chứng tỏ P (x)..(x − a). Định lý được chứng minh.
Hệ quả 1.3.3. Mọi đa thức bậc n có khơng q n nghiệm.
Chứng minh. Thật vậy, giả sử Pn (x) là đa thức bậc n có n + m nghiệm

x1 , x2 , . . . , xm (m ≥ 1). Theo Định lý Bezout ta có:
Pn (x) = (x − x1 )Q1 (x)
= (x − x1 )(x − x2 )Q2 (x)

..
.
= (x − x1 )(x − x2 ) . . . (x − xn+m )Qm+1 ,
trong đó Qk (x) là đa thức bậc n − k. Từ đây suy ra đa thức Pn (x) có bậc lớn
hơn n, vơ lý.

Từ Hệ quả 1.3.3 ta suy ra
Hệ quả 1.3.4. Đa thức có vơ số nghiệm chỉ là đa thức khơng.
Hệ quả 1.3.5. Hai đa thức có bậc nhỏ hơn hoặc bằng n nhận cùng giá trị tại

n + 1 giá trị khác nhau của đối số, đôi một tương ứng bằng nhau thì đồng nhất
bằng nhau.


8
Chứng minh. Giả sử P (x) và Q(x) là hai đa thức có bậc khơng vượt q n mà

P (xk ) = Q(xk ), k = 1, 2, . . . , n, n + 1, xi 6= xj , i 6= j.
Xét hiệu R(x) = P (x) − Q(x). Rõ ràng là deg(R) ≤ n, R(xk ) = 0, k =

1, 2, . . . , n, n + 1. Theo các Hệ quả 1.3.3 và Hệ quả 1.3.4, R(x) phải là đa thức
không. Vậy P (x) ≡ Q(x).
Định nghĩa 1.3.6. Ta nói số α là nghiệm bội k của đa thức Pn (x) bậc n nếu
tồn tại một đa thức Q(x), sao cho

Pn (x) = (x − α)k Q(x), Q(α) 6= 0.
• Khi k = 1, k = 2 ta gọi α tương ứng là nghiệm đơn, nghiệm kép của Pn (x).

• Khi k ≥ 2 ta nói α là nghiệm bội của Pn (x).


Định lý 1.3.7. Nếu α là nghiệm bội k của đa thức Pn (x) thì α là nghiệm cấp

k − 1 của đa thức đạo hàm Pn′ (x).
Chứng minh. Vì α là nghiệm cấp k của đa thức Pn (x), nên Pn (x) = (x −

α)k Q(x), Q(α) 6= 0. Suy ra

Pn′ (x) = k(x − α)k−1 Q(x) + (x − α)k Q′ (x)

= (x − α)k−1 [kQ(x) + (x − α)Q′ (x)].

Do Q(α) 6= 0, nên kQ(x) + (x − α)Q′ (x) không có nghiệm là α. Do đó α là
nghiệm cấp k − 1 của Pn′ (x). Định lý được chứng minh.

Định lý 1.3.8. Cho đa thức f (x) = an xn + an−1 xn−1 + . . . + a0 , trong đó

an 6= 0, ai là các số nguyên. Nếu p và q là các số nguyên nguyên tố cùng nhau,
sao cho f (p/q) = 0, thì q là ước của an , còn p là ước của a0 .

Chứng minh. Giả sử

0 = f (p/q) = an (p/q)n + . . . + a1 (p/q) + a0 .


9
Nhân phương trình trên với q n ta được

0 = an pn + an−1 qpn−1 + . . . + a1 q n−1 p + a0 q n .
Vì p là ước của ai q n−i pi với i = 1, 2, . . . , n, nên p là ước của a0 q n . Nhưng p, q
là nguyên tố cùng nhau, nên p chia hết a0 . Tương tự, q chia hết ai q n−i pi với


i = 0, 1, . . . , n − 1, nên q chia hết an pn . Vì p, q là nguyên tố cùng nhau, nên q
chia hết an . Định lý được chứng minh.

Định lý 1.3.9. Giả sử f (x) = an xn + an−1 xn−1 + . . . + a0 , trong đó an 6= 0, và

ai (i = 0, 1, . . . , n) là các số nguyên. Nếu a0 , an , f (1) là các số lẻ thì f khơng
có nghiệm hữu tỷ.
Chứng minh. Trước hết nhận xét rằng, nếu n = 1 và a0 , a1 là các số lẻ thì

f (1) = a0 + a1 là số chẵn. Do đó chúng ta giả thiết rằng n ≥ 2. Chúng ta sẽ

chứng minh bằng phản chứng. Giả sử rằng đa thức f có nghiệm hữu tỷ p/q

trong đó p, q là các số nguyên tố cùng nhau. Theo Định lý 1.3.8, p là ước của

a0 và q là ước của an . Ngoài ra, p và q là những số lẻ vì a0 và an là các số lẻ.
Như vậy pi q j là số lẻ với mỗi cặp nguyên không âm i, j. Vì f (p/q) = 0, ta có

0 = q n f (p/q) = an pn + an−1 qpn−1 + . . . + a1 q n−1 p + a0 q n .
Vì

f (1) =

X

ai = (a0 + an ) +

X


ai

i6=0,n

là số lẻ, nên số các số hạng lẻ trong các số ai phải là số lẻ. Do đó, khai triển của

q n f (p/q) có một số lẻ các số hạng lẻ nên khơng thể bằng khơng. Mâu thuẫn.
Vì vậy f khơng có nghiệm hữu tỷ. Định lý được chứng minh.
Ví dụ 1.3.10. Xét đa thức

f (x) = 15x19 + 7x13 − 2x8 + 13x6 − 12x4 − 3x3 + 2x2 + 28x + 343.
Ta có an = 15 và a0 = 343 là các số lẻ. Nhận xét rằng có 5 trong các hệ số của

f là các số lẻ, nên chắc chắn f (1) là số lẻ. Do đó f khơng thể có nghiệm hữu
tỷ.


10

1.4

Hệ số tổ hợp trong một số định lý và ví dụ

n
= Cn0
Ví dụ 1.4.1. Chứng minh C2n

Chứng minh. Ta có (1 + x)2n =

2n

P

i=1


2

+ Cn1

i
xi mà
C2n


2

+ Cn2


2

+ . . . + (Cnn )2 .

(1 + x)n (1 + x)n = (1 + x)2n
n
n
n
X
X
X
n
n
m m

k k
Cnk Cnm xk+m
Cn x =
Cn x ·
(1 + x) (1 + x) =
m=0

k=0

k=0
m=0

n
Hệ số của số hạng chứa xn ở vế trái là C2n
. Hệ số của số hạng chứa xn ở vế

phải là

Cn0 Cnn + Cn1 Cnn−1 + . . . + Cnn−1 Cn1 + Cnn Cn0
= Cn0 Cn0 + Cn1 Cn1 + . . . + Cnn−1 Cnn−1 + Cnn Cnn (vì Cnk = Cnn−k )

2

2

2
= Cn0 + Cn1 + . . . + Cnn−1 + (Cnn )2 .

2

2

2
n
Vậy C2n
= Cn0 + Cn1 + . . . + Cnn−1 + (Cnn )2 .


Ví dụ 1.4.2 (Đẳng thức Vandermonde). Chứng minh rằng với mọi n, m, r ∈ N
ta có

r
X

r
r−k
.
= Cn+m
Cnk Cm

k=0

Chứng minh. Ta có

(1 + x)n (1 + x)m = (1 + x)n+m
⇔
⇔

n
X

Cnk xk

k=0
m
n X
X


m
X

j j
x
Cm

=

j=0

j j+k
x
=
Cnk Cm

k=0 j=0

n+m
X

k=0
n+m
X

k
xk
Cn+m


k
xk .
Cn+m

k=0

So sánh hệ số của xr ở hai vế của đẳng thức này ta thu được
r
X
X
r
k j
r
r−k
.
= Cn+m
Cnk Cm
Cn Cm = Cn+m ⇔
j+k=r

k=0


11
Ví dụ 1.4.3. Chứng minh
k
= Cnk + 4Cnk−1 + 6Cnk−2 + 4Cnk−3 + Cnk−4 , 4 ≤ k ≤ n.
Cn+4

Chứng minh. Ta có thể chứng minh đẳng thức này bằng cách nhóm trực tiếp

các số hạng ở vế phải như sau:
VP = (Cnk + Cnk−1 ) + 3(Cnk−1 + Cnk−2 ) + 3(Cnk−2 + Cnk−3 ) + Cnk−3 + Cnk−4
k−1
k−2
k−3
k
k
= VT.
+ 3Cn+1
+ Cn+1
+ Cn+1
= Cn+1
= Cn+1




Tuy nhiên có thể dùng công thức nhị thức Newton và phương pháp cân bằng
hệ số để chứng minh như ở Ví dụ 1.4.1 và Ví dụ 1.4.2.
Ta có

(1 + x)n (1 + x)4 = (1 + x)n+4 ,
hay
n
X

Cnk xk

4

3


2




x + 4x + 6x + 4x + 1 =

k=0

Hệ số của số hạng chứa x ở vế trái là
k

n+4
X

k
xk .
Cn+4

k=0

Cnk−4 + 4Cnk−3 + 6Cnk−2 + 4Cnk−1 + Cnk−1 .
k
Hệ số của số hạng chứa xk ở vế phải là Cn+4
. Vậy
k
Cn+4
= Cnk + 4Cnk−1 + 6Cnk−2 + 4Cnk−3 + Cnk−4 , 4 ≤ k ≤ n.

Định lý 1.4.4 (Định lý Lucas, [4]). Cho p là một số nguyên tố và n là một số

nguyên sao cho

n = nm nm−1 ...n0 p = n0 + n1 p + · · · nm pm .
Cho i là một số nguyên dương nhỏ hơn n. Nếu i = i0 + i1 p + · · · + im pm với

0 ≤ i0 , i1 , . . . , im ≤ p − 1 thì

Cni
i

≡

n
Y

Cnijj

j=0

ở đây C00 = 1 và Cnjj = 0 nếu nj < ij .

(mod p),


12
Chứng minh. Trước hết ta chứng minh p | Cpk với mọi số nguyên tố p và k =

1, 2, . . . , p − 1. Ta có

Cpk =


p(p − 1) · · · (p − k + 1)
.
k!

Do p là số nguyên tố và k = 1, 2, . . . , p − 1 nên gcd(p, k!) = 1. Mà Cpk nguyên
(p − 1) · · · (p − k + 1)
nên k! | (p − 1) · · · (p − k + 1) hay
∈ Z. Vậy p | Cpk . Do
k!
đó

(1 + x)p ≡ 1 + xp

(mod p)

và
2

(1 + x)p ≡ ((1 + x)p )p ≡ (1 + xp )p ≡ 1 + xp

2

(mod p).

Vì vậy, bằng quy nạp ta được
r

(1 + x)p ≡ 1 + xp


r

(mod p)

với mọi số nguyên dương r. Ta có
m

(1 + x)n = (1 + x)n0 +n1 p+···+nm p

n
m
n
= (1 + x)n0 (1 + x)p 1 · · · (1 + x)p m
m

≡ (1 + x)n0 (1 + xp )n1 · · · (1 + xp )nm

(mod p).

Hệ số của xi trong khai triển của (1+x)n là Cni . Mặt khác, vì i = i0 +i1 p+· · ·+
m

im pm nên hệ số của xi là hệ số của xi0 (xp )i1 · · · (xp )im và bằng Cni00 Cni11 · · · Cnimm .
Do đó Cni ≡ Cni00 Cni11 · · · Cnimm (mod p).

Định lý 1.4.5 (Định lý Kummer, [4]). Cho n và i là các số mũ nguyên dương
với i ≤ n và p là một số nguyên tố. Khi đó pt là ước của Cni nếu và chỉ nếu t

nhỏ hơn hoặc bằng số lần nhớ khi cộng (n − i) và i trong hệ cơ số p.
Chứng minh. Ta sử dụng công thức

νp (n!) =


n − Sp (n)
,
p−1

(1.4)


13
ở đây νp (n) là ký hiệu số mũ tự nhiên m lớn nhất của p sao cho pm | n và Sp (n)
là tổng các chữ số của n trong hệ cơ số p.

Chúng ta sẽ chứng minh rằng số nguyên dương không âm lớn nhất t sao cho

pt | Cni là bằng chính xác số lần nhớ khi cộng (n − i) và i trong hệ cơ số p. Đặt
n! = am an−1 · · · a0 p , i! = bk bk−1 · · · b0 p , (n − i)! = cl cl−1 · · · c0 p .
Vì 1 ≤ i ≤ n nên k, l ≤ m. Khơng mất tính tổng qt giả sử rằng k ≤ l. Gọi

a, b, c và t′ là những số nguyên sao cho pa kn!, pb ki!, pc k(n − i)! và pt kCni . Khi
′

đó t′ = a − b − c. Từ công thức (1.4) ta có

n − (am + am−1 + · · · + a0 )
,
p−1
i − (bk + bk−1 + · · · + b0 )
,
b=
p−1

(n − i) − (cl + cl−1 + · · · + c0 )
.
c=
p−1

a=

Như vậy

t′ =

−(am + · · · + a0 ) + (bk + · · · + b0 ) + (cl + · · · + c0 )
.
p−1

(1.5)

Mặt khác, nếu cộng n − i và i trong hệ cơ số p ta có

bk bk−1 . . . b1 b0
cl cl−1 . . . ck ck−1 . . . c1 c0
am am−1 . . . al al−1 . . . ak ak−1 . . . a1 a0
Khi đó, ta có hoặc b0 + c0 = a0 (khơng có nhớ) hoặc b0 + c0 = a0 + p (nhớ 1).
Nói chung, ta có

b0 + c0 = a0 + α1 p,
b1 + c1 + α1 = a1 + α2 p,
b2 + c2 + α2 = a2 + α3 p,
............
b m + c m + α m = am ,



14
ở đây αi là số lần nhớ trong chữ số thứ i − 1 từ phải (chỉ lưu ý rằng bj = 0 với

j > k và cj = 0 với j > l). Cộng vế theo vế các phương trình trên lại với nhau
ta được

(b0 + · · · + bk ) + (c0 + · · · + cl )
= (a0 + · · · + am ) + (p − 1)(α1 + · · · + αm ).
Vậy phương trình (1.5) trở thành t′ = α1 + · · · + αm .
Định lý 1.4.6 (Định lý Wolstenholme, [4]). Cho p là một số nguyên tố. Khi
đó
p
C2p
≡2

(mod p2 ).

Chứng minh. Sử dụng đẳng thức Vandermonde (Ví dụ 1.4.2), ta có
p
C2p
= Cp0 Cpp + Cp1 Cpp−1 + · · · + Cpp Cp0 .

Do p | Cpk ∀k = 1, 2, . . . , p − 1 nên

p2 | Cpi Cpp−i ∀i = 1, 2, . . . , p − 1.
p
Vậy C2p
≡ 2 (mod p2 ).


Định lý 1.4.7 (Định lý RUF (Root of Unity Filter), [4]). Cho số nguyên dương

n. Gọi ε là nghiệm phức khác 1 bất kì của phương trình xn = 1. Xét đa thức
∞
P
F (x) =
ai xi . Khi đó
i=1

∞
X
i=1

ain =

1
(f (1) + f (ε) + f (ε2 ) + · · · + f (εn−1 )).
n

Chứng minh. Vì ε là một nghiệm phức của phương trình xn = 1 nên ε = e2πi/n .
Đặt

sk = 1 + εk + ε2k + · · · + ε(n−1)k .
Nếu n | k thì εk = e2πik/n = 1 nên

sk = 1 + 1 + · · · + 1 = n.


15

Ngược lại, nếu n ∤ k thì

Do đó

1 − e2πik
1 − εnk
sk =
=
= 0.
1 − εk
1 − εk
f (1) + f (ε) + f (ε2 ) + · · · + f (εn−1 ) = a0 s0 + a1 s1 + a2 s2 + · · ·
= n(a0 + an + a2n + · · · )

Chia cả hai vế cho n ta được điều phải chứng minh.
Lưu ý rằng định lý RUF khơng phản ảnh trực tiếp tính chất số học của hệ
số nhị thức Cnk nhưng rất có ý nghĩa trong việc kết hợp với lý thuyết hàm sinh
để giải quyết các bài toán số học.
Định lý 1.4.8 (Định lý Lagrange về đa thức đồng dư, [4]). Cho P (x) là một
đa thức hệ số nguyên bậc n và các hệ số của P (x) không đồng thời chia hết cho

p. Khi đó phương trình đồng dư P (x) ≡ 0 (mod p) có min{n, p} nghiệm.
Bổ đề 1.4.9 ([4]). Nếu phương trình P (x) ≡ 0 (mod p) có nhiều nghiệm hơn
bậc của P (x) thì tất cả các hệ số của P (x) đều chia hết cho p.


16

Chương 2
Vận dụng phương pháp đa thức vào

giải toán tổ hợp
2.1

Vận dụng phương pháp đa thức vào giải tốn tìm các
tập con của một tập hợp

Bài toán 2.1.1 (IMO 1995). Cho p là một số nguyên tố lẻ. Tìm số các tập con

A của tập hợp {1, 2, . . . , 2p}, biết rằng
(i) A chứa đúng p phần tử;

(ii) Tổng các phần tử của A chia hết cho p.
Chứng minh. Xét đa thức

P (x) = xp−1 + xp−2 + · · · + x + 1.
Đa thức này có p − 1 nghiệm phức phân biệt. Gọi α là một nghiệm bất kỳ

của P (x). Chú ý rằng α, α2 , . . . , αp−1 là p − 1 nghiệm phân biệt của P (x) và

α p = 1.

Do đó, theo định lý Viète, ta có

xp − 1 = (x − α)(x − α2 ) · · · (x − αp−1 )(x − αp ).
Xét đa thức Q(x) = (x−α)(x−α2 ) · · · (x−α2p ). Gọi H = {A ⊂ {1, 2, . . . , 2p} :
P
|A| = p} và S(A) là tổng các phần tử của A (tức là S(A) =
x). Giả sử
x∈A



17

Q(x) =

2p
P

ai xi , khi đó

i=0

ap = −

X

αS(A) .

A∈H

Vì nếu S(A) ≡ i (mod p) thì αS(A) = αi nên

ap = −

p−1
X

ni α i ,

i=0


trong đó ni là số các tập con A của H sao cho S(A) ≡ i (mod p).
Mặt khác, Q(x) = (xp − 1)2 , suy ra ap = −2. Thành thử có
p−1
X

ni αi = 2.

(2.1)

i=0

Xét đa thức R(x) =

p−1
P
i=1

ni xi + n0 − 2. Từ (2.1) suy ra α là một nghiệm của

R(x). Vì deg P = deg R và α là một nghiệm bất kỳ của P (x) nên P (x) và
R(x) chỉ sai khác nhau hằng số nhân. Từ đó
np−1 = np−2 = · · · = n1 = n0 − 2,
suy ra

p
np−1 + np−2 + · · · + n1 + n0 − 2 C2p − 2
=
.
n0 − 2 =

p
p
p
C2p
−2
Vậy đáp số của bài toán là n0 = 2 +
.
p

Với mỗi đa tập hợp (các phần tử có thể trùng nhau) A = {x1 , x2 , . . . , xn }

ta đặt

A(2) = {xi + xj | 1 ≤ i < j ≤ n}.
Tập hợp A(2) có nhiều tính chất thú vị, chẳng hạn khi n = 3, biết A(2) thì có
thể biết được A, nhưng với n = 4 thì điều này khơng cịn đúng nữa, chẳng hạn
với A = {1, 4, 5, 6}, B = {2, 3, 4, 7} thì

A(2) = B (2) = {5, 6, 7, 9, 10, 11}.


18
Vì thế nếu biết A(2) = {5, 6, 7, 9, 10, 11} thì khơng thể biết được A.
Một câu hỏi thú vị đặt ra là, với những giá trị nào của n thì nếu biết A(2) ,
ta có thể tìm được A? Kết quả bài toán dưới đây sẽ trả lời một phần câu hỏi
đó.
Bài tốn 2.1.2. Với n = 2k , chứng minh rằng tồn tại các đa tập hợp A, B
thỏa mãn các điều kiện:
1) |A| = |B| = n,


2) A 6= B ,

và 3) A(2) = B (2) .

Ngược lại, nếu tồn tại các đa tập hợp A, B thỏa mãn các điều kiện 1), 2) và 3)
thì n = 2k .
Chứng minh. Ta chứng minh phần đầu bằng phương pháp quy nạp toán học.
Với k = 1, có thể chọn A = {1, 4}, B = {2, 3}. Giả sử ta đã xây dựng được hai

đa tập hợp A, B sao cho

1) |A| = |B| = 2k ,

2) A 6= B ,

và 3) A(2) = B (2) .

Khi đó, đặt A∗ = A ∪ (B + s) và B ∗ = (A + s) ∪ B , trong đó A + s = {a + s |

a ∈ A}. Khi đó

|A∗ | = |B ∗ | = 2k+1 , A∗ (2) = B ∗ (2)

và với s đủ lớn thì A∗ 6= B ∗ .
Để chứng minh phần thứ hai, ta giả sử tồn tại hai đa tập hợp A và B thỏa
mãn các điều kiện 1), 2) và 3). Đặt

f (x) = xa1 + xa2 + · · · + xan ,
g(x) = xb1 + xb2 + · · · + xbn .


Khi đó, từ điều kiện A(2) = B (2) suy ra

f 2 (x) − f (x2 ) = g 2 (x) − g(x2 ).
Từ đó

f (x2 ) − g(x2 ) = (f (x) − g(x))(f (x) + g(x)).


19
Do f (1) = g(1) = n nên f (x) − g(x) chia hết cho x − 1. Đặt f (x) − g(x) =

(x − 1)k+1 h(x), (h(1) 6= 0) và thay vào phương trình trên ta được
(x2 − 1)k+1 h(x2 ) = (x − 1)k+1 h(x)(f (x) + g(x)).
Suy ra

(x + 1)k+1 h(x2 ) = h(x)(f (x) + g(x)).
Thay x = 1, chú ý h(1) 6= 0 và f (1) = g(1) = n, ta được n = 2k , điều phải

chứng minh.

Định nghĩa 2.1.3. Dãy phủ đầy đủ là các cặp sắp thứ tự (ai ; bi ) (i = 1, 2, . . . , k )
các số nguyên không âm, sao cho với mọi số nguyên không âm n, tồn tại duy
nhất một chỉ số i, 1 ≤ i ≤ k sao cho n ≡ ai (mod bi ).
Ví dụ với mọi số ngun khơng âm n thì n hoặc đồng dư 1 (mod 2), hoặc
đồng dư 0 hoặc 2 (mod 4). Do đó, (1; 2), (0; 4), (2; 4) là một dãy phủ đầy đủ.
Bài tốn dưới đây cung cấp một số tính chất thú vị của dãy phủ đầy đủ,
cũng là những điều kiện cần để một dãy là dãy phủ đầy đủ.
Bài toán 2.1.4. Nếu (a1 ; b1 ), (a2 ; b2 ), . . . , (an ; bn ) lập thành một dãy phủ đầy
đủ thì
1

1
1
+ + ··· +
= 1.
i)
b1 b2
bn
a1 a2
an
n−1
ii)
+
+ ··· +
=
.
b1
b2
bn
2
Chứng minh. Xét tổng

n P
∞
P

i=1 k=0

xai +kbi , |x| < 1. Theo định nghĩa của dãy phủ đầy

đủ thì với mọi N , tồn tại duy nhất một chỉ số i sao cho N đồng dư ai (mod bi ),

tức là N = ai + kbi . Như vậy, xN xuất hiện đúng một lần trong tổng nói trên.
Vậy ta có

∞
n X
X
i=1 k=0

x

ai +kbi

=

∞
X
i=0

xi .


20
Từ cơng thức tính tổng cấp số nhân, ta được
n
X
i=1

xai
1
=

(chú ý |x| < 1).
1 − x bi
1−x

Ta sẽ khai thác đẳng thức quan trọng này để chứng minh các tính chất i) và
ii). Để chứng minh i), ta viết lại đẳng thức trên dưới dạng
n
X
xai (1 − x)

x bi

i=1

hay

n
X
i=1

Cho x → 1, ta được

=1

xai
= 1.
1 + x + · · · + xbi −1

(2.2)


n
X
1
= 1.
b
i
i=1

Để chứng minh ii), ta lấy đạo hàm hai vế đẳng thức (2.2) thì được
n
X
ai xai −1 (1 + x + · · · + xbi −1 ) − xai (1 + 2x + · · · + (bi − 1)xbi −2 )
i=1

(1 + x + · · · + xbi −1 )2

Cho x → 1, chú ý rằng 1 + 2 + · · · + bi − 1 =
(bi −1)bi
2
2
bi

n
X
ai b i −
i=1

hay

= 0.


(bi − 1)bi
ta được
2
=0

n 
X
ai
i=1

1
1 
− −
= 0.
bi 2 2bi

Từ kết quả câu i) suy ra điều phải chứng minh.

Bài toán 2.1.5. Chứng minh rằng từ 2n − 1 số nguyên bất kì ln tìm được

n số có tổng chia hết cho n.

Chứng minh. Với n nhỏ, bài tốn có thể chứng minh dễ dàng bằng cách xét
các trường hợp. Ví dụ, với n = 3, ta chia 5 số nguyên vào 3 ô, ô chia 3 dư 0, ô


21
chia 3 dư 1 và ô chia 3 dư 2. Nếu mỗi ơ đều chứa ít nhất 1 số thì chọn từ 3 ô,
mỗi ô một số, ta được 3 số cần tìm. Nếu có 1 ơ nào đó rỗng thì sẽ có ít nhất 1

ơ có 3 số và đó chính là 3 số cần tìm.
Với n = 5, ta có thể lặp lại cách chứng minh tương tự, tuy nhiên số trường
hợp cần xét sẽ nhiều hơn.
Nếu n là hợp số, chẳng hạn n = 9, ta có thể sử dụng cách làm sau: áp dụng
kết quả với n = 3, từ 17 số {a1 , a2 , . . . , a17 }, dĩ nhiên có thể chọn ra 3 số có

tổng chia hết cho 3. Khơng mất tính tổng qt, giả sử đó là a1 + a2 + a3 . Tiếp
theo, từ 13 số {a4 , a5 , . . . , a17 }, có thể chọn ra 3 số có tổng chia hết cho 3, giả

sử đó là a4 , a5 , a6 . Tiếp tục như vậy, ta được các bộ ba số có tổng chia hết

cho 3, mà bằng cách đánh số lại nếu cần, giả sử đó là (a7 , a8 , a9 ), (a10 , a11 , a12 ),

(a13 , a14 , a15 ).
Xét các số

s1 =

a4 + a5 + a6
a13 + a14 + a15
a1 + a2 + a3
, s2 =
, . . . , s5 =
.
3
3
3

Theo cách xây dựng, 5 số s1 , s2 , . . . , s5 là các số nguyên. Áp dụng kết quả với


n = 3, ta suy ra tồn tại 3 số trong 5 số này có tổng chia hết cho 3. Khơng mất
tính tổng quát, giả sử đó là s1 , s2 , s3 . Khi đó a1 +a2 +a3 +· · ·+a9 = 3(s1 +s2 +s3 )

chia chết cho 9, điều phải chứng minh.

Bằng cách làm tương tự, ta thấy rằng nếu bài toán đã đúng với n = p và

n = q thì nó cũng đúng với n = pq. Vậy chỉ cần chứng minh bài toán đúng với
n = p là số nguyên tố. Ta sẽ chứng minh điều này.
Giả sử ngược lại, tồn tại 2p − 1 số nguyên a1 , a2 , . . . , a2p−1 sao cho mọi tổng

con gồm p phần tử của nó đều khơng chia hết cho p. Khi đó, theo định lý nhỏ
Fermet, ta có

(ai1 + ai2 + · · · + aip )p−1 ≡ 1

(mod p).


22
Từ đó
X

p
(ai1 + ai2 + · · · + aip )p−1 ≡ C2p−1

(mod p)

1≤i1

p
p
(do có C2p−1
tổng ở vế trái). Do C2p−1
khơng chia hết cho p. Vì thế, sẽ suy ra

điều mâu thuẫn nếu chứng minh được rằng vế trái chia hết cho p. Ta chứng
minh điều này bằng cách chứng minh, trong khai triển tổng vế trái, hệ số của

asi11 · · · asikk (với s1 + · · · + sk = p − 1) chia hết cho p.
Để có những số hạng như vậy, cần chọn thêm p − k phần tử ik+1 , . . . , ip để

bổ sung thành p số và xét (ai1 + · · · + aik + · · · + aip )p−1 . Khai triển biểu thức
(p − 1)!
này, ta sẽ được hệ số của asi11 · · · asikk là
.
s 1 ! · · · sk !

p−k
Có C2p−1−k
cách bổ sung, do đó hệ số của asi11 · · · asikk trong khai triển ở vế
(p − 1)!
p−k
p−k
trái là C2k−1−k
. Chú ý rằng 1 ≤ k ≤ p − 1 nên C2p−1−k
chia hết cho
s1 ! · · · s k !
p. Từ đó, tất cả các số hạng asi11 · · · asikk trong khai triển ở vế trái đều có hệ số

chia hết cho p, tức là vế trái chia hết cho p. Mâu thuẫn. Chứng tỏ điều giả sử
là sai. Bài toán được chứng minh cho n = p và như vậy cho n bất kì.

2.2

Vận dụng phương pháp đa thức vào giải một số bài
toán tổ hợp có yếu tố truy hồi

Theo định nghĩa phép nhân đa thức, với P (x) =

m
P

i

ai x , Q(x) =

i=0

thì

P (x)Q(x) =

m+n
X

ck x , trong đó ck =
i

k=0

k
X

m
P

aj xj

j=0

ai bk−i .

i=0

Cơng thức này là cơ sở để chứng ta có thể biểu diễn một số công thức truy hồi
thông qua phép nhân đa thức. Dưới đây, chúng ta sẽ giới thiệu sơ lược về lý
thuyết đa thức xe để minh họa cho ý này.
Nhiều bài tốn tổ hợp có thể phát biểu dưới dạng tổng quát sau: Cho bàn
cờ C kích thước n × n và bảng con B ⊂ C . Có bao nhiêu cách xếp n con xe lên