SỞ GIÁO DỤC VÀ ĐÀO TẠO NAM ĐỊNH
TRƯỜNG THPT TRẦN HƯNG ĐẠO

BÁO CÁO SÁNG KIẾN
SỬ DỤNG PHƯƠNG TRÌNH NGHIỆM NGUYÊN
ĐỂ GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP

Tác giả: Phạm Quốc Thịnh
Trình độ chuyên môn: Cử nhân
Chức vụ: Giáo viên
Nơi công tác: Trường THPT Trần Hưng Đạo - Nam Định

Nam Định, ngày 15 tháng 6 năm 2015

1


1. Tên sáng kiến: Sử dụng phương trình nghiệm nguyên để giải một số bài toán tổ hợp
2. Lĩnh vực áp dụng sáng kiến: Giảng dạy môn Đại số và giải tích lớp 11 chương
trình THPT.
3. Thời gian áp dụng sáng kiến: Kể từ ngày 5 tháng 9 năm 2014.
4. Tác giả:
Họ và tên: Phạm Quốc Thịnh
Năm sinh: 1980
Trình độ chuyên môn: Cử nhân
Chức vụ công tác: Giáo viên
Nơi làm việc: Trường THPT Trần Hưng Đạo - Nam Định
Điện thoại: 0913898797
Tỷ lệ đóng góp tạo ra sáng kiến: 100%
5. Đơn vị áp dụng sáng kiến:
Tên đơn vị: Trường THPT Trần Hưng Đạo - Nam Định

Ta trích dẫn bài toán tổ hợp trong đề thi VMO - 2014 để minh họa:
Bài toán: (VMO 2014) Cho đa giác đều có 103 cạnh. Tô màu đỏ 79 đỉnh của đa giác
và tô màu xanh các đỉnh còn lại. Gọi A là số cặp đỉnh đỏ kề nhau và B là số cặp đỉnh
xanh kề nhau. Xác định số cách tô màu cả các đỉnh để B = 14 . Biết rằng, hai cách tô
màu được xem là như nhau nếu chúng có thể nhận được từ nhau qua một phép quay
quanh tâm đường tròn ngoại tiếp đa giác.
Lời giải 1:
Số đỉnh được tô màu xanh là: 103 − 79 = 24 .
Nếu tất cả các đỉnh đỏ chụm thành một cụm thì A = 78 .
Nếu tất cả các đỉnh đỏ bị cắt thành hai cụm thì A = 77 .
Cứ như thế, nếu tất cả các đỉnh đỏ bị cắt thành k cụm thì A = 79 − k .
Nhận thấy, nếu có k cụm đỏ thì cũng có k cụm xanh nên B = 24 − k .
Như vậy, các giá trị mà k có thể nhận được là 1, 2 ,..., 24 . Suy ra cặp ( A, B) có thể
nhận được 24 giá trị.

Để có B = 14 thì k = 10 , tức là cần chia các đỉnh xanh thành 10 cụm, chia các đỉnh đỏ
thành 10 cụm. Ta cần đếm số cách chia như vậy.
Ta đánh số các cụm xanh từ 1 đến 10, bắt đầu từ một cụm nào đó. Gọi số phần tử của
cụm thứ i là xi , với i = 1.10 . Khi đó các số: y1 = x1; y2 = x1 + x2 ; ...; y9 = x1 + ... + x9
(riêng y10 = 24 cố định, không tính) là các số dương khác nhau từ 1 đến 23 (không thể
là 24).
9
9
Có C23
cách chọn 9 số từ 23 số. Như vậy, có C23
cách chia 24 đỉnh xanh thành 10 cụm

(có xếp hàng).
9
Tương tự như vậy, có C78


Bình luận: Cách giải trên sử dụng quy tắc nhân, khái niệm tổ hợp và công thức tính số
tổ hợp đã được trình bày trong Sách giáo khoa Đại số và Giải tích lớp 11. Tuy nhiên, ta
cũng có lời giải khác dựa vào nhận xét về số tổ hợp thỏa mãn điều kiện cho trước với
số nghiệm nguyên không âm của một phương trình bậc nhất nhiều ẩn.

Lời giải 2: Gọi X là số các cụm đỉnh màu đỏ liền nhau thì B = 24 − X . Do đó để
B = 14 thì x = 10 .
Trước hết, ta chia 24 điểm xanh thành 10 cụm. Nhận thấy số cách chia 24 điểm xanh
vào

10

cụ m

bằng

số

nghiệm

nghuyên

không

âm

của

phương

số nghiệm nguyên không âm của một phương trình bậc nhất nhiều ẩn với số tổ hợp
thỏa mãn điều kiện cho trước thì ta có thể có lời giải ngắn gọn, dễ hiểu.
Theo hướng nghiên cứu này, tôi xin trình bày sáng kiến kinh nghiệm chuyên môn: "Sử

dụng phương trình nghiệm nguyên để giải một số bài toán tổ hợp".

6


II. MÔ TẢ GIẢI PHÁP
1. Mô tả giải pháp trước khi tạo ra sáng kiến
Trong mục, tôi xin tóm tắt lý thuyết về các quy tắc cơ bản của phép đếm; các
khái niệm: hoán vị, chỉnh hợp, tổ hợp và công thức tính tương ứng đã được trình bày
trong Sách Giáo khoa Đại số và Giải tích lớp 11 hiện hành và nêu ra các ví dụ áp dụng
lý thuyết để giải bài tập tổ hợp tương ứng.

1.1. Các quy tắc cơ bản của phép đếm
1.1.1. Quy tắc cộng
Nếu một công việc được hoàn thành bởi một trong n phương án, trong đó có ai cách
thực hiện phương án thứ i thì có tất cả

n

∑a

i

cách để hoàn thành công việc.

i =1

Bước 1: Chọn một đường để đi từ A đến B, có: 3 cách chọn.
7


Bước 2: Chọn một đường để đi từ B đến C, có: 4 cách chọn.
Vậy, theo quy tắc nhân, có: 3.4 = 12 cách chọn đường đi.

1.2. Hoán vị, chỉnh hợp, tổ hợp
1.2.1. Hoán vị
Cho tập hợp A gồm n phần tử, mỗi cách sắp xếp tất cả n phần tử đó theo một thứ tự
nhất định thì được gọi là một hoán vị của n phần tử.
Áp dụng quy tắc nhân, có n. ( n − 1) . ( n − 2 ) ...2.1 hoán vị như vậy. Ta kí hiệu số hoán vị
n

trên là n ! . Như vậy: n ! = n. ( n − 1) . ( n − 2 ) ...2.1 = ∏ i .
i =1

Ta quy ước: 0! = 1 .

Ví dụ 3: Có bao nhiêu cách sắp xếp 8 học sinh
a) Thành một hàng dọc?
b) Thành một vòng tròn?

Lời giải:
a) Mỗi cách sắp xếp 8 học sinh thành một hàng dọc là một hoán vị của 8 phần tử. Như
vậy có: 8! cách xếp.
b) Theo phần a), có 8! cách xếp 8 học sinh theo một tứ tự nhất định. Tuy nhiên, trên
vòng tròn thì 8 vị trí có vai trò như nhau nên đáp số của bài toán là:

8!

Bước 2: Chọn 4 học sinh trong số 7 học sinh chỉ giỏi Toán và sắp xếp vào các vị trí Tổ
trưởng Tổ 1, 2, 3, 4. Mỗi cách chọn và sắp xếp như vậy là một chỉnh hợp chập 4 của 7
phần tử. Do đó, có: A74 cách.
Bước 3: Chọn 2 học sinh trong số 6 học sinh chỉ giỏi Văn và sắp xếp vào các vị trí Lớp
phó, Bí thư Chi đoàn. Mỗi cách chọn và sắp xếp như vậy là một chỉnh hợp chập 2 của
6 phần tử. Do đó, có: A62 cách.
Vậy, theo quy tắc nhân, có: 4. A74 . A62 cách chọn và sắp xếp nhân sự.

1.2.3. Tổ hợp
Cho tập hợp A gồm n phần tử, mỗi tập con gồm k phần tử của tập hợp A được gọi là
một tổ hợp chập k của n phần tử.
Áp dụng quy tắc nhân và chú ý rằng không có sự phân biệt về thứ tự cả các phần tử
trong mỗi tập con, ta có:

n ( n − 1) ... ( n − k + 1)
k!

tổ hợp như vậy. Ta kí hiệu số tổ hợp chập

k của n phần tử là Cnk .

Như vậy, Cnk =

n!
.
k !( n − k ) !

Ví dụ 4: Một nhóm Sinh viên tình nguyện gồm 4 nam và 8 nữ. Cần chia thành 2 tổ,
mỗi tổ có 2 nam và 4 nữ. Hỏi có bao nhiêu cách chia tổ như vậy?


sang phải đúng bằng m .
Bài toán được đưa về việc tìm xem có bao nhiêu dãy nhị phân có độ dài (m + n) mà
trong đó có đúng n giá trị 1. Thật đơn giản, để lập dãy nhị phân như trên, trước hết ta
xếp m phần tử 0 vào (m + n) vị trí trong dãy nhị phân, có Cmm+ n cách xếp như vậy. Với
mỗi cách xếp m phần tử 0 như vậy, chỉ việc chèn các phần tử 1 vào các ô trong đã tạo
ra giữa m phần tử 0 là ta được dãy nhị phân nói trên. Như vậy, có Cmm+ n dãy nhị phân
thỏa mãn điều kiện nói trên.
Quay trở lại bài toán, ta cho một vật chuyển động trên một đường đi từ nút ( 0;0 ) đến
nút ( m; n ) theo một đường đi thỏa mãn điều kiện của bài toán trên. Gọi xi +1 là đoạn
mà vật đó chuyển động theo chiều từ dưới lên trên có chỉ số thứ i , với i = 1, m . Khi đó,
11


một cách trực quan, ta nhận thấy số đường đi thỏa mãn điều kiện trên bằng số nghiệm
nguyên không âm của phương trình

x1 + x1 + ... + xm+1 = n .
Số nghiệm đó bằng Cmm+ n .
Như vậy, số nghiệm nguyên không âm của phương trình x1 + x1 + ... + xm = n , trong đó

m, n ∈ » là Cmm+−n1−1 .
Tiếp theo bài toán cơ bản, ta đưa ra một số ví dụ quan trọng có liên quan đến các bài
toán tổ hợp sau này.

Ví dụ 6: Tìm số nghiệm nguyên của phương trình

x1 + x2 + x3 + x4 = 17
thỏa mãn điều kiện: x1 ≥ 1, x2 ≥ 2, x3 ≥ 3, x4 ≥ 4 .

Lời giải:

A1 ∩ A2 ∩ A3 = A1 ∩ A2 ∩ A4 = A1 ∩ A3 ∩ A4 = A2 ∩ A3 ∩ A4 = 0
A1 ∩ A2 ∩ A3 ∩ A4 = 0
Theo nguyên lý bù trừ, ta có đáp số: C83 − 4.C53 = 16 (nghiệm).

2.2. Mối liên hệ giữa số nghiệm nguyên của phương trình bậc nhất nhiều ẩn với số
tổ hợp thỏa mãn điều kiện cho trước
Trong mục này, ta sẽ sử dụng kết quả của Bài toán cơ bản và Ví dụ 6, Ví dụ 7 để giải
một số bài toán tổ hợp.
Trước hết, ta quay lại bài toán chia kẹo Euler

Ví dụ 8: Có bao nhiêu cách chia hết n chiếc kẹo giống nhau cho m em bé khác nhau?
( m, n ∈ » * )

Lời giải:
Gọi xi là số kẹo đã chia cho em bé thứ i , (với i = 1, m ). Nhận thấy, số cách chia n
chiếc kẹo cho m em bé bằng số nghiệm nguyên không âm của phương trình

x1 + x2 + ... + xm = n
Theo Bài toán cơ bản, ta có đáp số: Cmm+−n1−1 (cách).

Ví dụ 9: Có bao nhiêu cách chia hết n chiếc kẹo giống nhau cho m em bé khác nhau
sao cho mỗi em bé đều có ít nhất một chiếc kẹo? Ở đó: m, n ∈ »* và n ≥ m .

Lời giải:

13


Gọi xi là số kẹo đã chia cho em bé thứ i , (với i = 1, m ). Nhận thấy, số cách chia n
chiếc kẹo cho m em bé bằng số nghiệm nguyên của phương trình

Lý luận tương tự Ví dụ 6, số nghiệm nguyên của phương trình (2) thỏa mãn điều kiện

xi > 9, i = 1, 6 là: C145

14


Vì 6 tập nghiệm của phương trình (2) lần lượt thỏa mãn điều kiện xi > 9, i = 1, 6 là đôi
một rời nhau nên tổng số nghiệm của phương trình (2) thỏa mãn điều kiện

xi > 9, ∀i = 1, 6 là: 6.C145
Theo nguyên lý bù trừ, số nghiệm nguyên không âm của phương trình (1) thỏa mãn
5
điều kiện xi ≤ 9, ∀i = 1,6 là: C24
− 6.C145 .
5
− 6.C145 số tự nhiên thỏa mãn yêu cầu bài toán.
Vậy có C24

Bình luận: Trong lời giải trên, ngoài việc sử dụng Ví dụ 6 để xác định số nghiệm
nguyên không âm của phương trình bậc nhất nhiều ẩn, ta còn phải sử xác định tổng số
phần tử của các tập hợp rời nhau và nguyên lý bù trừ. Để tiện cho việc theo dõi, tác giả
xin trình bày sơ lược lý thuyết Tập hợp trong phần Phụ lục.
Lời giải của các bài toán sau đây cũng được sử dụng lý thuyết Tập hợp.

Ví dụ 11: Có bao nhiêu cách chọn ra m số phân biệt từ n số nguyên dương đầu tiên
sao cho trong sự lựa chọn đó không có hai số nguyên liên tiếp? Ở đó m, n ∈ N * và
n > 2m .

Lời giải:

Theo bài toán cơ bản, số nghiệm nguyên không âm của phương trình (3) là: C3002
.

Lý luận tương tự Ví dụ 7, số nghiệm của phương trình (3) thỏa mãn điều kiện
2
x1 > 1000 bằng C2001
và số nghiệm của phương trình (3) thỏa mãn điều kiện
2
x2 , x3 > 2000 bằng: 2.C1001
.

Dễ thấy tập nghiệm thỏa mãn điều kiện x1 > 1000 và tập nghiệm thỏa mãn điều kiện

x2 , x3 > 2000 rời nhau nên theo nguyên lý bù trừ, số nghiệm của phương trình (3) thỏa
2
2
2
mãn điều kiện 0 ≤ x1 ≤ 1000; 0 ≤ x2 , x3 ≤ 2000 bằng: C3002
− C2001
− 2.C1001
.
2
2
2
Vậy, đáp số của bài toán là: C3002
− C2001
− 2.C1001
(cách xếp).

Ví dụ 13: (VMO 2012) Cho một nhóm 5 cô gái, kí hiệu là G1 , G2 , G3 , G4 , G5 và 12

Đến đây, vì y5 chỉ có thể nhật một số ít giá trị nên có thể làm thủ công bằng cách lần
lượt thay y5 bởi các giá trị 0, 1, 2, 3 và áp dụng kết quả của Bài toán cơ bản, ta thu

được kết quả: C124 + C114 + C104 + C94 (nghiệm).
Cuối cùng, vì 12 chàng trai có thể đổi chỗ cho nhau nên số cách sắp xếp thỏa mãn các

(

)

điều kiện của bài toán là: C124 + C114 + C104 + C94 .12!

Ví dụ 14: Một học sinh muốn lọt vào đội tuyển đi thi Toán phải trải qua 4 kì thi và phải
đạt ít nhất 17 điểm, nhưng không có kì thi nào bị điểm 1 hoặc 2. Hỏi có bao nhiêu cách
để học sinh đó chắc chắn lọt vào đội tyển. (Hai cách tiến hành khác nhau nếu có ít nhất
một kì thi đạt số điểm khác nhau và mỗi kì thi có thể đạt điểm 1 hoặc 2 hoặc 3 hoặc 4
hoặc 5).

Lời giải:
Gọi Ai là tập hợp tất cả các cách tiến hành 4 kì thi sao cho tổng số điểm đạt được
trong 4 kì thi là i và không có kì thi nào đạt điểm dưới 3. ( i = 17, 20 ).
Gọi A là tập hợp tất cả các cách tiến hành 4 kì thi sao cho học sinh được lọt vào đội
tuyển, ta có: A = A17 ∪ A18 ∪ A19 ∪ A20 và các tập hợp A17 , A18 , A19 , A20 đôi một rời
nhau.
Theo quy tắc cộng, ta có: A = A17 + A18 + A19 + A20 .
Hoàn toàn tương tự như Ví dụ 7:

17



là số nghiệm nguyên của phương trình x1 + x2 + x3 + x4 = 20 với

( j = 1, 4) . Số nghiệm thỏa mãn điều kiện như vậy là: 1.

Suy ra A = A17 + A18 + A19 + A20 = 16 + 10 + 4 + 1 = 31 .
Vậy có 31 cách khác nhau để học sinh được lọt vào đội tuyển.
Cuối cùng, ta lấy ví dụ là một bài trong kì thi OLYMPIC Toán của Balan (4/1995)

Ví dụ 15: Có 12 cái hộp khác nhau được đánh số từ 1 đến 12 và 8 hòn bi giống nhau.
Hỏi có bao nhiêu cách xếp 8 hòn bi vào 12 cái hộp sao cho tổng số bi trong các hộp 1,
2, 3 là chẵn, còn tổng số bi trong các hộp 4, 5, 6 là lẻ.

Lời giải:
Từ giả thiết suy ra tổng số bi được xếp vào 6 hộp từ 7 đến 12 phải là số lẻ. Trước hết,
ta hãy biểu diễn 8 thành tổng của 3 số: số đầu chẵn, số thứ hai lẻ và số thứ ba lẻ. Có

8 = 0 + 7 +1 = 0 + 5 + 3 = 0 +1+ 7
8 = 2 + 5 +1 = 2 + 3 + 3 = 2 +1+ 5
8 = 4 + 3 +1 = 4 +1+ 3
8 = 6 +1+1
Như vậy, có 10 cách biểu diễn.
Kí hiệu Aijk là cách xếp 8 viên bi vào 12 hộp sao cho tổng số bi trong ba hộp đầu là i ,
tổng số bi trong ba hộp tiếp theo là j và tổng số bi trong 6 hộp cuối cùng là k .
Gọi A là tập hợp tất cả các cách xếp bi thỏa mãn yêu cầu của bài toán, ta có

A = A071 ∪ A053 ∪ A035 ∪ A017 ∪ A251 ∪ A233 ∪ A215 ∪ A431 ∪ A413 ∪ A611
18


Vì các tập hợp đôi một rời nhau nên

A017 = 1.3.792 = 2376

A251 = 6.21.6 = 756

A233 = 6.10.56 = 3360

A215 = 6.3.252 = 4536

A431 = 15.10.6 = 900

A413 = 15.3.56 = 2520

A611 = 28.3.6 = 504
19


Do đó

A = A071 + A053 + A035 + A017 + A251 + A233 + A215 + A431 + A413 + A611 = 18864
Vậy, có 18864 cách xếp 8 viên bi vào 12 chiếc hộp thỏa mãn yêu cầu bài toán.

III. HIỆU QUẢ DO SÁNG KIẾN ĐEM LẠI
Bản sáng kiến kinh nghiệm đã nêu ra khó khăn khi sử dụng các quy tắc cơ bản của
phép đếm; các công thức tính số hoán vị, chỉnh hợp, tổ hợp khi giải các bài toán tổ hợp
nâng cao.

Đồng thời, bản sáng kiến cũng nêu ra một cách giải quyết khó khăn là: Nhận xét có
tương ứng 1 - 1 giữa số tổ hợp thỏa mãn điều kiện cho trước với số nghiệm nguyên
không âm của phương trình bậc nhất nhiều ẩn. Từ đó đưa bài toán tổ hợp về bài toán
tìm số nghiệm nguyên không âm của một phương trình bậc nhất nhiều ẩn.