Đa thức và ứng dụng trong các bài toán tổ hợp
Trần Nam Dũng
Trờng ĐHKHTN Tp HCM
Đa thức là một trong các khái niệm quan trọng của toán học, có nhiều ứng dụng trong các
lĩnh vực khác nhau: đại số, số học, hình học đại số, lý thuyết hàm Trong bài viết này,
chúng tôi đề cập đến những ứng dụng của đa thức trong các bài toán tổ hợp.
1. Đa thức và các bài toán về tổng con
Quy tắc nhân đơn thức xa1.xa2.xan = xa1+a2++an, rất thú vị, trong nhiều trờng hợp, cho
chúng ta những ứng dụng bất ngờ của đa thức vào các bài toán liên quan đến tổng con. Ta
xem xét một số ví dụ.
Bài toán 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.
Lời giải: 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ý Viette, xp-1 - 1 = (x-)(x-2) (x-p-1)
Xét đa thức Q(x) = (x-)(x-2) (x-2p) và gọi
H = { A {1, 2, , 2p}: |A| = p}
S ( A)
; S ( A) = x
Giả sử Q( x) = ai x i . Khi đó a p =
2p

AH

i =0

Vì nếu S(A) i (mod p) thì


n p 1 + n p 2 + ... + n1 + n0 2 C 2pp 2
n0 2 =
=
p
p


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

C 2pp 2
p

.

Với mỗi đa tập hợp (cho phép các phần tử trùng nhau) A = {x1, x2, , xn} ta đặt A(2) = {xi
+ xj | 1 i < j n}. 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, nhng 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}
Vì thế biết A(2) = { 5, 6, 7, 9, 10, 11} 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 toán 2. Với n = 2k, chứng minh rằng tồn tại các đa tập hợp A, B thoả mãn điều kiện:
1) | A | = | B | = n; 2) A B và 3) A(2) = B(2)
Điều ngợc lại cũng đúng, nghĩa là nếu tồn tại các đa tập hợp A, B thoả mãn các điều kiện
1) 2) và 3) thì n = 2k.
Lời giải: Ta chứng minh vế đầu bằng phơng pháp quy nạp toán học. Với k = 1, ta 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

b1 b2
bn
2)

a
a1 a 2
n 1
+
+ ... + n =
b1 b2
bn
2

Lời giải: Xét
n



x

ai + kbi

i =1 k = 0

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 môđun bi, tức là N = ai + kbi. Nh vậy, xN xuất hiện đúng 1 lần trong tổng nói
trên. Vậy ta có
n



i =1 1 x
i =1 1 + x + ... + x
n
1
Cho x = 1 ta đợc = 1.
i =1 bi
Để chứng minh 2), ta lấy đạo hàm hai vế đẳng thức (*) thì đợc
n
ai x ai 1 (1 + x + ... + x bi 1 ) x ai (1 + 2 x + ... + (bi 1) x bi 2 )
=0

(1 + x + ... + x bi 1 ) 2
i =1
Cho x = 1, chú ý rằng 1 + 2 + + bi-1 = (bi-1)bi/2, ta đợc
n
n
ai bi (bi 1)bi / 2
ai 1 1

=0
=
0
hay


2
bi
2 2bi
i =1
i =1 bi


p
(do có C 2 p 1 tổng ở vế trái)
p
Ta có C 2 p 1 không chia hết cho p. Vì thế, ta 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 rằng, trong
khai triển tổng vế trái, hệ số của ai1s1aiksk với s1 + + sk = p-1 chia hết cho p.

Để có những số hạng nh vậy, ta 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 này, ta sẽ đợc hệ số của ai1s1
aiksk là (p-1)!/s1!...sk!.
p k
Có C 2 p 1k cách bổ sung, do đó hệ số của a i1s1aiksk trong khai triển ở vế trái là
( p 1)!
p k
C 2ppk1 k
. Chú ý rằng 1 k p - 1 nên C 2 p 1k chia hết cho p. Từ đó, tất cả các số
s1!...sk !
hạng ai1s1aiksk 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. Mâu thuẫn này 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. Đa thức và công thức truy hồi
Với

m

n

i =0



N ( B ) = (1) k (n k )!rk ( B ) .
k =0

Chứng minh: Có n! cách xếp n quân xe lên C sao cho không quân nào ăn quân nào. Bây
giờ ta đếm xem trong các cách xếp này, có bao nhiêu cách xếp phạm luật, tức là các cách
xếp có ít nhất 1 quân xe nằm trên 1 ô thuộc B. Đặt B = {b 1, b2, , bm}, trong đó bi là các
ô. Đặt Bi = {các cách xếp n quân xe lên C sao cho không quân nào ăn quân nào và có 1
m

quân xe ở ô bi}. Khi đó, tập các cách xếp không hợp lệ chính là



Bi . Dùng nguyên lý

i =1

bù trừ, chú ý rằng | Bi1 Bi 2 ... Bik | sẽ bằng (n-k)! nếu cách quân xe ở bi1, bi2, , bik đôi
một không ăn nhau và bằng 0 trong trờng hợp ngợc lại, ta suy ra đpcm.
Nh vậy, điều quan trọng là tính đợc rk(B). Với mục đích tính rk(B), ta đa vào khái niệm đa
thức xe nh sau:
Định nghĩa 1. Giả sử rk(B) là số cách đặt k quân xe lên B sao cho không quân nào ăn
n

k
quân nào, khi đó rB ( x) = rk ( B) x đợc gọi là đa thức xe của bảng con B, trong đó r 0(B)
k =0

= 1.

quân nào ăn quân nào. Số cách xếp trong trờng hợp này, nh vậy, bằng rk(B2). Từ đó
rk(B) = rk-1(B1) + rk(B2)
Đẳng thức này chuyển sang ngôn ngữ đa thức chính là rB(x) = xrB1(x) + rB2(x).
Định nghĩa 2. Một ma trận L loại r ì n với r n gọi là một khối chữ nhật La tinh r ì n
nếu mỗi một trong các số 1, 2, , n xuất hiện trên mỗi dòng đúng 1 lần và xuất hiện trên
mỗi cột không quá 1 lần. Nếu r = n thì L gọi là khối vuông La tinh.
Bài toán 5. Cho khối vuông La tinh 6 ì 6 có 2 dòng đầu là
1 2 3 4 5 6
2 4 1 3 6 5
Có bao nhiêu cách thêm vào dòng thứ 3?
Lời giải: Số cách thêm vào dòng thứ 3 chính là số hoán vị S6 sao cho (i) không ở
trong ô bị cấm của bàn cờ sau

Gọi B là bảng gồm các ô cấm. Sử dụng các tính chất về đa thức xe, ta tính đợc
RB(x) = (1 + 8x + 20x2 + 16x3 + 2x4)(1 + 4x + 2x2)
= 1 + 12x + 54x2 + 112x3 + 106x4 + 40x5 + 4x6
Từ đó, số cách thêm vào dòng thứ ba là
6! - 5!12 + 4!54 - 3!112 + 2!106 - 1!40 + 4 = 70.
3. Định lý không điểm tổ hợp
Trong kỳ thi Toán quốc tế lần thứ 48 tổ chức tại Việt Nam tháng 7 vừa qua, có bài toán số
6 đợc coi là bài toán khó nhất của kỳ thi. Bài toán này có cách phát biểu tổ hợp, nhng lời


giải lại sử dụng đến đa thức. Chỉ có 5 thí sinh làm đợc bài này, số còn lại đều xa lầy vào
con đờng tổ hợp thuần tuý.
Bài toán 6. Cho n > 1 là số nguyên. Trong không gian, xét tập hợp
S = { (x, y, z) | x, y, z {0, 1, , n}, x + y + z > 0}
Hãy tìm số mặt phẳng nhỏ nhất cùng chứa tất (n+1) 3 - 1 điểm của S nhng không đi qua
gốc toạ độ.
Chú ý là trờng hợp 2 chiều của bài toán này có thể giải đợc bằng phơng pháp quy nạp toán

đơn thức x1t1x2t2xntn trong f là khác 0. Khi đó, nếu S 1, S2, , Sn là các tập con của F sao
cho |Si| > ti thì tồn tại s1 S1, s2 S2, , sn Sn sao cho f(s1, s2, , sn) 0.
Có 3 thí sinh lần lợt đến từ Moldova, Ukraina và Nga đã chứng minh lại định lý này và áp
dụng để giải quyết bài toán 6.


Thật vậy, giả sử k < 3n
Xét Q(x, y, z) = P(x, y, z) d(x-1)(x-n)(y-1)(y-n)(z-1)(z-n)
Trong đó d 0 đợc chọn sao cho Q(0, 0, 0) = 0. Khi đó Q(x, y, z) = 0 với mọi (x, y, z)
Sx ì Sy ì Sz. Vì |Sx| = |Sy| = |Sz| > n và hệ số của xnynzn trong Q(x, y, z) bằng d khác 0 nên
theo định lý Combinatorial Nullstellensatz, tồn tại (x0, y0, z0) Sx ì Sy ì Sz sao cho Q(x0,
y0, z0) 0. Mâu thuẫn. Vậy k = 3n.
Định lý Combinatorial Nullstellensatz là trờng hợp rời rạc của định lý không điểm Hilbert
nổi tiếng (Hilbert Nullstellensatz). Định lý này đợc Nora Alon chứng minh năm 1999 và
có nhiều ứng dụng trong số học, tổ hợp và lý thuyết đồ thị. Phép chứng minh định lý này
có thể xem trong [4, 5, 6]. Sau đây chúng ta xem xét một số ứng dụng khác của định lý
này.
Bài toán 7. (Cauchy Davenport) Với các tập hợp A và B, định nghĩa A+B = {a+b| a
A, b B}. Khi đó với mọi số nguyên tố p và với mọi A, B thuộc Zp, ta có
|A + B| min {p, |A| + |B| - 1}
Lời giải: Nếu |A| + |B| > p, kết luận bài toán là hiển nhiên: trong trờng hợp này A + B =
Zp. Bây giờ giả sử rằng |A| + |B| p và giả sử ngợc lại rằng |A + B| |A| + |B| - 2. Khi đó
trong Zp có tập hợp C sao cho C A + B, |C| = |A| + |B| - 2.
Xét đa thức
|A|-1 |B|-1

của x

y


6. Cho S = {(x, y)| 0 x m, 0 y n, x + y > 0}. Chứng minh rằng để phủ tất cả các
điểm của S bằng các đờng thẳng không đi qua gốc toạ độ, ta cần ít nhất m+n đờng thẳng.
7. (Vô địch Nga, 1991) Cho 2n số thực phân biệt a 1, a2, , an, b1, b2, , bn. Bảng n ì n đợc ghi các số theo quy tắc sau: trong ô ở dòng i, cột j ta ghi số a i + bj. Chứng minh rằng
nếu tích các số ở tất cả các cột bằng nhau thì tích các số ở tất cả các hàng cũng bằng
nhau.
8. Cho p là một số nguyên tố và G là một đồ thị có bậc không nhỏ hơn 2p-1. Chứng minh
rằng tồn tại một tập không rỗng các đỉnh U của G sao cho số cạnh có ít nhất một đỉnh
thuộ U chia hết cho p.
9. (Vô địch Saint-Peterburg 2003) Cho p là số nguyên tố và số nguyên dơng n p. Giả sử
a1, a2, , an là bộ các số nguyên bất kỳ và fk là số các tập con k phần tử của bộ này có
n

tổng chia hết cho p. Chứng minh rằng

(1)
k =0

k

f k p (ta quy ớc f0 = 1).

5. Tài liệu tham khảo
1. Herbert S. Wilf, Generatingfunctionology, electronic version,
/>2. Trần Ngọc Danh, Toán rời rạc nâng cao, Nhà xuất bản Đại học quốc gia Tp HCM,
2004.
3. Nguyễn Sinh Nguyên, Nguyễn Văn Nho, Lê Hoành Phò, Tuyển tập các bài dự tuyển
Olympic Toán học quốc tế 1991 2001, Nhà xuất bản Giáo dục 2003.
4. Nora Alon, Combinatorial Nullstellensatz, Combinatorics, Probability and Computing,
8 (1-2), 7-29.
5. Anton Batominosvki, Solution to IMO 2007 Problems, Internet resource