Luận văn Một số Chuyên đề về tổ hợp dành cho học sinh có năng khiếu toán bậc trung học phổ thông

Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn  
ĐạI HọC THáI NGUYÊN 
Tr-ờng Đại học KHOA học 
nguyễn THị NGọC áNH 
Một số chuyên đề về tổ hợp dành 
cho học sinh có năng khiếu toán 
bậc trung học phổ thông 
luận văn thạc sỹ TOáN học 
THáI NGUYÊN - 2009 
www.VNMATH.com
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn  
ĐạI HọC THáI NGUYÊN 
Tr-ờng Đại học KHOA học 
-----------***----------- 
nguyễn THị NGọC áNH 
Một số chuyên đề về tổ hợp dành 
cho học sinh có năng khiếu toán 
bậc trung học phổ thông 
Chuyên ngành: Ph-ơng pháp toán sơ cấp 
Mã số : 60 . 46. 40 
 luận văn thạc sỹ TOáN học 
Ng-ời h-ớng dẫn khoa học: TS. Nguyễn Đức Hoàng 
THáI NGUYÊN - 2009 
www.VNMATH.com
Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn tận tình và nghiêm khắc
của TS . Nguyễn Đức Hoàng. Tôi xin bày tỏ lòng kính trọng và biết ơn sâu
sắc tới Thầy và gia đình.
Tôi xin chân thành cảm ơn Ban giám hiệu trường Đại học Khoa học, Phòng
đào tạo và nghiên cứu khoa học đã quan tâm giúp đỡ, tạo mọi điều kiện thuận
lợi cho tôi được học tập tốt.
Tôi xin chân thành cảm ơn Sở Giáo dục và Đào tạo Tỉnh Thái Nguyên,
Trường Trung học phổ thông Chuyên Thái Nguyên, đặc biệt là tổ Toán đã
giúp đỡ tôi về tinh thần và vật chất trong suốt quá trình học tập.
1
www.VNMATH.com
Mục lục
Lời cảm ơn 1
Mở đầu 3
Chương 1. Kiến thức cơ bản 6
1.1. Quy tắc cộng và quy tắc nhân . . . . . . . . . . . . . . . . . 6
1.2. Hoán vị và tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3. Nguyên lý chuồng chim bồ câu (Nguyên lý Dirichlet) . . . . 9
1.4. Hoán vị và tổ hợp tổng quát . . . . . . . . . . . . . . . . . . 11
1.5. Công thức bao hàm và loại trừ . . . . . . . . . . . . . . . . . 14
Chương 2. Một số chuyên đề về tổ hợp dành cho học sinh có năng
khiếu toán bậc trung học phổ thông 17
2.1. Chuyên đề 1: Quy tắc cộng và quy tắc nhân . . . . . . . . . . 18
2.2. Chuyên đề 2: Hoán vị và tổ hợp . . . . . . . . . . . . . . . . 23
2.3. Chuyên đề 3: Nguyên lý chuồng chim bồ câu . . . . . . . . . 29
2.4. Chuyên đề 4: Các số Ramsey . . . . . . . . . . . . . . . . . . 32
2.5. Chuyên đề 5: Các số Catalan . . . . . . . . . . . . . . . . . . 38
2.6. Chuyên đề 6: Các số Stirling . . . . . . . . . . . . . . . . . . 41
2.7. Chuyên đề 7: Hoán vị và tổ hợp tổng quát . . . . . . . . . . . 47
2.8. Chuyên đề 8: Nguyên lý bao hàm và loại trừ . . . . . . . . . 50
2.9. Chuyên đề 9: Những sự xáo trộn và những sự sắp đặt trước . . 54
2.10. Chuyên đề 10: Đại lượng bất biến . . . . . . . . . . . . . . . 57
Chương 3. Một số bài tập đề nghị 60
2
www.VNMATH.com
Tài liệu tham khảo 67
3
www.VNMATH.com
Mở đầu
Có thể nói tư duy về tổ hợp ra đời từ rất sớm. Vào thời nhà Chu, người ta
đã biết đến các hình vẽ có liên quan đến những hình vuông thần bí. Thời cổ
Hy lạp, nhà triết học Kxenokrat, sống ở thế kỷ thứ 4 trước công nguyên, đã
biết tính số các từ khác nhau lập từ một bảng chữ cái cho trước. Nhà toán
học Pitago và các học trò của ông đã tìm ra nhiều con số có tính chất đặc
biệt. Việc tìm ra được các số như vậy đòi hỏi phải có một nghệ thuật tổ hợp
nhất định. Tuy nhiên, có thể nói rằng, lý thuyết tổ hợp được hình thành như
một ngành toán học mới và quãng thế kỷ 17 bằng một loạt các công trình
nghiên cứu nghiêm túc của các nhà toán học xuất sắc như Pascal, Fermat,
Leibnitz, Euler...Mặc dù vậy, trong suốt hai thế kỷ rưỡi, tổ hợp không có vai
trò nhiều trong việc nghiên cứu tự nhiên. Đến nay, với sự hỗ trợ đắc lực của
máy tính , tổ hợp đã chuyển sang lĩnh vực toán ứng dụng với sự phát triển
mạnh mẽ, có nhiều kết quả có ích cho con người.
Nhận thức được vai trò của lý thuyết tổ hợp đối với đời sống hiện đại. Lý
thuyết tổ hợp đã được đưa vào chương trình học phổ thông và chiếm một
phần trong các kỳ thi toán quốc gia và quốc tế. Tuy nhiên, ở nước ta, tài liệu
viết về tổ hợp chưa nhiều. Do đó, bản luận văn này sẽ cung cấp thêm một tài
liệu về tổ hợp cho học sinh phổ thông; đặc biệt là dành cho những em học
sinh có năng khiếu môn toán. Chúng tôi hi vọng luận văn này sẽ đáp ứng
được phần nào lòng yêu thích khám phá toán học của các em. Đồng thời đây
cũng là một tài liệu để các đồng nghiệp tham khảo.
Luận văn gồm ba chương. Chương một chúng tôi trình bày một số kiến
4
www.VNMATH.com
thức cơ bản của tổ hợp theo một lôgic khác so với sách phổ thông nhằm gây
sự mới lạ cho học sinh. Chương hai là trọng tâm của luận văn. Trong chương
này, học sinh được tìm hiểu mười chuyên đề:
Chuyên đề 1: Quy tắc cộng và quy tắc nhân.
Chuyên đề 2: Hoán vị và tổ hợp.
Chuyên đề 3: Nguyên lý chuồng chim bồ câu.
Chuyên đề 4: Các số Ramsey.
Chuyên đề 5: Các số Catalan.
Chuyên đề 6: Các số Stirling.
Chuyên đề 7: Hoán vị và tổ hợp tổng quát.
Chuyên đề 8: Nguyên lý bao hàm và loại trừ.
Chuyên đề 9: Những sự xáo trộn và những sự sắp đặt trước.
Chuyên đề 10: Đại lượng bất biến.
Trong mỗi chuyên đề, các bài tập thường được dẫn dắt theo những chủ đề
nhất định. Qua đó học sinh tự tìm thấy cho mình những kiến thức liên quan
đến chủ đề được nêu. Đồng thời, mỗi bài đều có lời giải chi tiết, ngắn gọn,
đầy sáng tạo và bất ngờ. Các lời giải này ít gặp trong các tài liệu về tổ hợp có
trên thị trường. Tác giả hi vọng chính điều này kích thích sự ham hiểu biết,
lòng say mê của các học sinh có năng khiếu toán. Chương ba có nội dung là
những bài tập đề nghị được chọn lựa kĩ lưỡng; nhằm giúp các em vận dụng
những kiến thức thu được từ hai chương trước để nâng cao kỹ năng giải toán
tổ hợp của mình.
Sau một thời gian nghiên cứu luận văn đã được hoàn thành. Tuy nhiên sẽ
không tránh khỏi nhiều sai sót. Kính mong sự góp ý của quý thầy cô, các
bạn đồng nghiệp và các em học sinh. Chúng tôi xin chân thành cảm ơn!
5
www.VNMATH.com
Chương 1
Kiến thức cơ bản
1.1. Quy tắc cộng và quy tắc nhân
Quy tắc cộng: Nếu Ei(i = 1, ..., k) là k sự kiện thoả mãn:
(i) Không có hai sự kiện nào trong số chúng xảy ra đồng thời
(ii) Ei có thể xảy ra theo ni cách
thì một trong k sự kiện có thể xảy ra theo (n1 + n2 + ...+ nk) cách.
Ví dụ 1.1.1 Một lớp học có 18 học sinh nam và 12 học sinh nữ thì có
18 + 12 = 30 cách chọn một học sinh (không kể nam, nữ) làm người đại
diện cho lớp.
Ví dụ 1.1.2 Giả thiết E là sự kiện chọn các số nguyên tố nhỏ hơn 10 và F
là sự kiện chọn các số tự nhiên chẵn nhỏ hơn 10.
Thì: E có 4 cách xảy ra, F có 4 cách xảy ra. Nhưng vì 2 là một số nguyên
tố chẵn nên một trong hai sự kiện E hoặc F có thể xảy ra theo 4+4−1 = 7
cách.
Quy tắc nhân: Nếu Ei(i = 1, ..., k) là k sự kiện và E1 có thể xảy ra theo
n1 cách; E2 có thể xảy ra theo n2 cách (không phụ thuộc đến việc E1 xảy
ra như thế nào); E3 có thể xảy ra theo n3 cách (không phụ thuộc đến việc
E1 và E2 xảy ra như thế nào),...,Ek có thể xảy ra theo nk cách (không phụ
thuộc đến (k− 1) sự kiện trước xảy ra như thế nào), thì k sự kiện có thể xảy
ra đồng thời theo n1.n2.n3...nk cách.
Ví dụ 1.1.3 Một giá sách có 6 quyển sách tiếng Anh đôi một khác nhau; 8
quyển sách tiếng Pháp đôi một khác nhau và 10 quyển sách tiếng Đức đôi
một khác nhau.
(i) Có 6.8.10 = 480 cách chọn lấy 3 quyển sách trong đó mỗi quyển một
6
www.VNMATH.com
thứ tiếng.
(ii) Có 6 + 8 + 10 = 24 cách chọn lấy 1 quyển sách bất kỳ trong số các
quyển sách nói trên.
Ví dụ 1.1.4 Nếu một bài thi trắc nghiệm có 8 câu hỏi mỗi câu hỏi có 3
phương án trả lời (một phương án đúng và hai phương án sai). Vậy số cách
chọn câu trả lời của tất cả 8 câu hỏi trên là 38 = 6561 cách.
1.2. Hoán vị và tổ hợp
Cho X là một tập hợp bao gồm n phần tử và r là một số nguyên không
âm nhỏ hơn hoặc bằng n.
Định nghĩa 1.2.1 Một r-hoán vị của X là một bộ sắp thứ tự gồm r phần tử
từ n phần tử của X .
Một n-hoán vị của X được gọi là một hoán vị của X .
Số r-hoán vị của một tập hợp n phần tử được ký hiệu là P (n, r).
Ví dụ 1.2.2 {2, 3, 4} và {2, 4, 3} là hai 3-hoán vị khác nhau của X =
{1, 2, 3, 4, 5}.
Định nghĩa 1.2.3 Một r-tổ hợp của X là một tập con gồm r phần tử của X .
Số r-tổ hợp của một tập hợp n phần tử được ký hiệu là C(n, r).
Định lý 1.2.4 (i) P (n, r) =
n!
(n− r)!
(ii) C(n, r) =
P (n, r)
r!
=
n!
r!(n− r)! = C(n, n− r)
ở đây chúng ta đưa ra hàm giai thừa:
m! ≡ (1).(2)...(m) và 0! ≡ 1
Chứng minh: (i) Có n cách chọn một phần tử bất kỳ của X vào vị trí đầu
tiên trong r vị trí; có (n− 1) cách chọn một phần tử từ nhóm (n− 1) phần
tử còn lại để chiếm vị trí thứ hai trong số r vị trí. Chú ý rằng số cách chọn
phần tử chiếm vị trí thứ hai không phụ thuộc vào cách chọn phần tử chiếm ở
vị trí thứ nhất như thế nào.
7
www.VNMATH.com
Do đó theo quy tắc nhân, hai vị trí đầu tiên có thể lấp đầy bởi n(n − 1)
cách...và tất cả r vị trí có thể lấp đầy bởi:
P (n, r) = n(n− 1)...(n− r + 1) = n!
(n− r)!
cách.
(ii) Để đánh giá C(n, r), chú ý rằng một r-hoán vị của tập hợp n phần tử X
là hoán vị của một r-tập con nào đó của X .
Hơn nữa, những r-tập con phân biệt sinh ra r-tổ hợp phân biệt. Do đó, bằng
quy tắc cộng ta có:
P (n, r) = P (r, r) + P (r, r) + ...+ P (r, r)
Số các số hạng ở vế phải là số các r-tập con của X tức là C(n, r). Do đó ta
có:
P (n, r) = C(n, r)P (r, r) = C(n, r)r!
Mỗi r-tập con của X có một tập con bù duy nhất là (n− r)-tập con. Từ đó
ta có một quan hệ quan trọng là:
C(n, r) = C(n, n− r)
Đặc biệt, số hoán vị của n phần tử là:
P (n, n) = n!
Nhận xét 1.2.5 Trong chương trình phổ thông, một r- hoán vị của một tập
hợp có n phần tử được gọi là một chỉnh hợp chập r của n phần tử, một r- tổ
hợp của một tập hợp có n phần tử được gọi là một tổ hợp chập r của n phần
tử đó.
Ví dụ 1.2.6 Một câu lạc bộ gồm 12 học sinh khối 12; 10 học sinh khối 11;
9 học sinh khối 10. Cần lập ra một ban đại diện gồm: 4 học sinh khối 12;
4 học sinh khối 11; 3 học sinh khối 10. Vậy ta có: C(12, 4) =
12!
4!8!
= 495
8
www.VNMATH.com
cách chọn 4 học sinh khối 12; C(10, 4) = 210 cách chọn 4 học sinh khối 11;
C(9, 3) = 84 cách chọn 3 học sinh khối 10. Bằng quy tắc nhân, số cách để
chọn ra ban đại diện trên là: 495.210.84 = 8731800 cách.
1.3. Nguyên lý chuồng chim bồ câu (Nguyên lý Dirichlet)
Một số kết quả sâu sắc của lý thuyết tổ hợp xuất phát từ một mệnh đề
đơn giản:
Nếu n chuồng chim bồ câu là nơi trú ẩn của ít nhất (n+ 1) con chim bồ
câu thì có ít nhất một chuồng chim chứa từ hai con chim bồ câu trở lên.
Ví dụ 1.3.1 Giả thiết rằng có nhiều chiếc tất đỏ, nhiều chiếc tất trắng và
nhiều chiếc tất xanh ở trong hộp. Hỏi phải lấy từ hộp đó ra ít nhất bao nhiêu
chiếc tất (khi lấy không nhìn vào bên trong) để chắc chắn được 2 chiếc cùng
màu.
Giải
Mỗi một màu được coi như một chuồng chim bồ câu vậy n = 3. Do đó, nếu
lấy n+ 1 = 4 chiếc tất thì ít nhất có hai chiếc tất cùng màu. Một tổng quát
đơn giản của nguyên lý chuồng chim bồ câu như sau:
Nếu n chuồng chim bồ câu là nơi trú ẩn của kn+ 1 con chim bồ câu với
k là một số nguyên dương thì ít nhất có một chuồng chứa từ k+1 con chim
bồ câu trở lên.
Ví dụ 1.3.2 Tương tự như ví dụ 1.3.1 nếu cần lấy 6 chiếc tất cùng màu thì ta
vẫn có n = 3 và để đảm bảo rằng một (hay nhiều hơn) trong số các chuồng
đó chứa k + 1 = 6 (hoặc nhiều hơn) con chim bồ câu thì chúng ta phải lấy
kn+ 1 = 16 con chim. Do đó đáp số là 16 chiếc tất.
Ví dụ 1 ... 1.i2..ik
= n
Trong đó tổng được lấy theo tất cả các bộ có thể.
i1 < i2 < ... < ik, k = 1, 2, ...n từ tập hợp {1, 2, ..., n}.
Hướng giải: Dùng đồng nhất hệ số đa thức và biến đổi tổ hợp.
Bài 3.9 Cho tập hợp A = {a1, a2, ..., an} ∈ N ∗ và số nguyên dương m sao
cho n >
m
2
. Biết rằng số dư trong phép chia các phần tử của A cho m là
khác nhau đôi một.
Chứng minh rằng với mỗi k ∈ Z, tồn tại i, j ∈ {1, 2, ..., n} (i, j không nhất
thiết khác nhau) sao cho số ai + aj − k chia hết cho m.
Hướng giải: Sử dụng nguyên lý Dirichlet.
Bài 3.10 Cho n ∈ N ∗, chứng minh đẳng thức:
n∑
k=0
1
C(n, k)
=
n+ 1
2n+1
.
n+1∑
k=1
2k
k
.
Hướng giải: Quy nạp và biến đổi tổ hợp.
Bài 3.11 Cho P (x) ∈ R[x] có bậc ≤ 2n. Biết rằng với mỗi số nguyên
k ∈ [−n, n] thì | P (x) |≤ 1.Chứng minh rằng với mọi x ∈ [−n, n] thì
| P (x) |≤ 22n
Hướng giải: Dùng đa thức nội suy Lagrange và biến đổi tổ hợp.
Bài 3.12 Cho các số nguyên : x0 < x1 < ... < xn và cho đa thức P (x) =
xn + a1x
n−1 + ... + an. Chứng minh rằng trong các số P (xj), j = 0, 1, .., n
luôn tồn tại ít nhất một số có giá trị tuyệt đối không nhỏ hơn
n!
2n
.
Hướng giải : Giống bài 3.11.
61
www.VNMATH.com
Bài 3.13 Tìm tất cả các số nguyên dương k thỏa mãn điều kiện : Nếu
F (x) ∈ Z(x) sao cho 0 ≤ F (c) ≤ k với mọi c ∈ {0, 1, .., k + 1} thì
F (0) = F (1) = ... = F (k + 1).
Hướng giải: Sử dụng nguyên lý Dirichlet.
Bài 3.14 Giả sử : (1.x+ 2.x2 + ...+ n.xn)2 = a0 + a1x+ ...a2nx
2n
. Chứng
minh rằng an+1 + an+2 + ...+ a2n =
n(n+ 1)(5n2 + 5n+ 2)
24
.
Hướng giải : Biến đổi tổ hợp.
Bài 3.15 Cho P (x) ∈ Z[x] sao cho với mỗi x ∈ N ∗ ta có P (x) > x. Dãy
(bn) xác định như sau: b1 = 1, bk+1 = P (bk),∀k ≥ 1. Biết rằng với mỗi
d ∈ N ∗ luôn tồn tại ít nhất một số hạng của dãy (bn) chia hết cho d. Chứng
minh rằng: P (x) = x+ 1,∀x ∈ N ∗.
Hướng giải: Phản chứng và dùng nguyên lý Dirichlet.
Bài 3.16 Cho n số p1, p2, ..., pn ∈ [0, 1]. Chứng minh rằng bất phương trình:
n∑
i=0
1
| x− pi | ≤ 8n(1 +
1
3
+
1
5
+ ...+
1
2n− 1) có nghiệm thuộc [0, 1].
Hướng giải: Sử dụng nguyên lý Dirichlet.
Bài 3.17 Cho n ∈ N ∗ , đặt Sn =
[n/2]∑
k=0
(C(n, k)−C(n, k− 1))2. Chứng minh
rằng Sn =
1
n+ 1
.C(2n, n).
Hướng giải : Biến đổi tổ hợp.
Bài 3.18 Cho các số thực α1, α2, ..., αn. Chứng minh rằng tồn tại số c phụ
thuộc vào α1, α2, ..., αn sao cho có vô số bộ các số (m1,m2, ...,mn) ∈ Zn
mà | α1m1 + ...+ αnmn |< c| m1 | +...+ | mn |n−1 .
Hướng giải : Dùng qui tắc nhân và nguyên lý Dirichlet.
Bài 3.19 Cho các tập hợp M = {1, 2, ..., 27} và A = {a1, ..., ak} ⊂
{1, 2, ..., 14}. Có tính chất sau: Mỗi phần tử của M là một phần tử của
A hoặc là tổng của hai phần tử (không nhất thiết phân biệt) của A. Tìm giá
trị nhỏ nhất của k.
Hướng giải : Dùng tổ hợp và chứng minh phản chứng để có kết quả giá trị
nhỏ nhất của k bằng 8.
62
www.VNMATH.com
Bài 3.20 Cho hệ phương trình gồm q = 2p ẩn:
a11x1 + ...+ a1qxq = 0.
..............................
ap1x1 + ...+ apqxq = 0.
trong đó aij ∈ {−1, 0, 1}. Chứng minh rằng tồn tại nghiệm (x1, ..., xq) khác
(0, 0, ..., 0), xj ∈ Z và | xj |≤ q,∀j = 1, 2, ..., q.
Hướng giải : Dùng qui tắc nhân và nguyên lý Dirichlet.
Bài 3.21 Cho tập hợp M gồm 2002 số nguyên dương, mỗi số chỉ có ước
nguyên tố không vượt quá 23. Chứng minh rằng tồn tại 4 số phân biệt trong
M có tích là lũy thừa bậc 4 của một số nguyên.
Hướng giải: Nguyên lý Dirichlet.
Bài 3.22 Cho tập hợp A gồm n nguyên tố phân biệt và M là tập gồm n+ 1
số tự nhiên phân biệt sao cho mỗi số trong M đều không là số chính phương
và chỉ có ước nguyên tố thuộc A. Chứng minh rằng có thể chọn ra trong M
một số có tích là một số chính phương.
Hướng giải: Nguyên lý Dirichlet.
Bài 3.23 Cho S = {1, 2, 3, ..., 100} và P là tập các tập con của S mà
|T | = 49. Với mỗi T ∈ P , ta đánh số một cách ngẫu nhiên, các số lấy từ tập
S. Chứng minh rằng tồn tại tập conM của S có số phần tử là 50 và với mỗi
x ∈M , tập M \ {x} không được đánh số bởi x.
Hướng giải: Nguyên lý Dirichlet.
Bài 3.24 Tô màu các ô của bảng 4 x 7 bởi hai màu: đen, trắng.
Chứng minh rằng với mọi cách tô luôn tồn tại một hình chữ nhật có các cạnh
nằm trên đường lưới sao cho 4 ô ở 4 góc cùng màu.
Hướng giải: Nguyên lý Dirichlet.
Bài 3.25 Xét bảng ô vuông 4 x 4. Điền vào mỗi ô một số 1 hoặc -1 sao cho
tổng các số trong mỗi hàng và tổng các số trong mỗi cột bằng 0.
Hỏi có bao nhiêu cách?
63
www.VNMATH.com
Đáp án: 90 cách.
Bài 3.26 Lưới ô vuông n x n, trong đó n là số nguyên dương. Mỗi nút lưới
ta tô một trong hai màu: xanh hoặc đỏ sao cho mỗi hình vuông đơn vị có hai
đỉnh màu đỏ và hai đỉnh màu xanh.
Hỏi có bao nhiêu cách?
Đáp án: 2n+2 − 2 cách.
Bài 3.27 Cho n là số nguyên dương. Kí hiệu Zn = {0, 1, 2, ..., n − 1}. Xét
các tập:
An = {(a, b, c) : a, b, c ∈ Zn, a < b < c, a+ b+ c ≡ 0(modn)}
,
Bn = {(a, b, c) : a, b, c ∈ Zn, a ≤ b ≤ c, a+ b+ c ≡ 0(modn)}
a) Chứng minh rằng |Bn| = |An|+ n.
b) Tính |An|.
Hướng giải: b) Dùng so sánh để chứng minh
|An+3| = |Bn|. Suy ra |An+3| = |An|+ n. Từ đó tính được |An|.
Bài 3.28 Cho tập X = {1, 2, ..., 2000}. Hỏi có bao nhiêu tập con T của X
mà tổng các phần tử của T chia hết cho 5.
Đáp số: Số tập con cần tìm là
1
5
(2402 + 22000)
Bài 3.29 Cho bảng ô vuông 1991 x 1992. Kí hiệu ô (m,n) là nằm ở giao
của hàng thứ m và cột thứ n. Tô màu các ô của bảng theo quy tắc sau:
Lần thứ nhất tô ba ô (r, s), (r + 1, s + 1), (r + 2, s + 2) với 1 ≤ r ≤ 1989,
1 ≤ s ≤ 1990. Từ lần thứ hai, mỗi lần tô ba ô chưa có màu nằm bên cạnh
nhau trong cùng một hàng hoặc trong cùng một cột. Hỏi ta có thể tô màu
hết tất cả các ô của bảng được không?
Đáp số: Không ( Sử dụng bất biến) .
Bài 3.30 Cho góc vuông Oxy. Chia góc đó thành các hình vuông đơn vị bởi
64
www.VNMATH.com
các đường thẳng song song với Ox và Oy. Kí hiệu ô (i, j) là ô nằm ở giao
của dòng thứ i và cột thứ j (thứ tự các dòng và cột được tính từ dưới lên và
từ trái sang phải). Thực hiện thuật toán sau: Mỗi lần lấy ra khỏi góc xOy
viên bi ở ô (i, j) nào đó mà tại các ô (i+1, j) và (i, j +1) đều không có bi,
đồng thời thêm vào hai ô này mỗi ô một viên bi.
Hỏi sau một số lần thực hiện thuật toán ta có thể nhận được trạng thái mà:
a) Các ô (1,1),(1,2),(2,1),(2,2) đều không có bi?
b) Các ô (1,1),(1,2),(2,1),(2,2), (1,3) và (3,2) đều không có bi?
Đáp số:
a) Có
b) Không ( Sử dụng bất biến) .
Bài 3.31 Hai người luân phiên viết các số 0 hoặc 1 vào các ô của bảng 1993
x 1994. Gọi An và Bn tương ứng là giá trị lớn nhất của tổng các số thuộc
cùng một hàng và tổng các số thuộc cùng một cột. Người thứ nhất thắng nếu
An > Bn, ngược lại thì người thứ hai thắng.
Hỏi có chiến lược thắng.
Đáp số: Người thứ hai có chiến lược thắng.
Bài 3.32 Trên bảng cho trước số nguyên dương n0 ≥ 2. Hai người chơi trò
chơi sau: Người thứ nhất được phép viết lên bảng số n1 sao cho n0 ≤ n1 ≤
n0
2
, người thứ hai được phép viết số n2 sao cho
n1
n2
có dạng ps, trong đó p
là số nguyên tố và s là số nguyên dương. Sau đó thay giá trị của n0 bởi giá
trị của n2 và tiếp tục chơi. Người thứ nhất sẽ thắng nếu viết được số 2001 và
người thứ hai sẽ thắng nếu viết được số 1. Giả thiết rằng, hai người chơi đều
rất thông minh. Hỏi ai là người chiến thắng.
Đáp số: Nếu n0 ∈ {2, 3, 4, 5} thì người thứ hai sẽ thắng. Nếu n0 ∈ {6, 7} thì
hai người hòa. Các trường hợp còn lại thì người thứ nhất sẽ thắng.
Bài 3.33 Trong một cuộc thi hoa hậu, mỗi giám khảo được đề nghị 10 thí
sinh vào vòng chung kết. Một nhóm thí sinh gọi là chấp nhận được đối với
giám khảo A nếu trong nhóm đó có ít nhất một thí sinh do A đề nghị. Biết
65
www.VNMATH.com
rằng, với 6 giám khảo bất kì đều tồn tại một nhóm gồm đúng 2 thí sinh là
nhóm chấp nhận được đối với cả 6 giám khảo đó. Chứng minh rằng tồn tại
một nhóm gồm 10 thí sinh là nhóm chấp nhận được đối với mọi thành viên
của ban giám khảo.
Hướng dẫn: Phản chứng.
Bài 3.34 Cho k, n là các số nguyên dương và một bảng ô vuông vô hạn.
Đặt 3k x n quân cờ trong hình chữ nhật 3k x n. Xét cách chơi sau đây: mỗi
quân cờ sẽ nhảy ngang hoặc nhảy dọc qua một ô kề nó chứa quân cờ để đến
ô tiếp theo nếu ô này còn trống. Sau khi làm như vậy thì loại bỏ quân cờ vừa
bị nhảy qua.Hỏi có khi nào trên bảng ô vuông đã cho chỉ còn lại đúng một
quân cờ?.
Hướng giải: Sử dụng bất biến.
Bài 3.35 Trong hình tròn đơn vị cho 2000 điểm tạo thành đa giác lồi
A1A2...A2000. Chứng minh rằng tồn tại 3 điểm trong số đó tạo thành tam
giác có diện tích không vượt quá
1
31250000
.
Hướng giải: Phương pháp cực hạn.
Bài 3.36 Trên mặt phẳng cho một số điểm đỏ và một số điểm xanh. Một
số cặp điểm được nối với nhau . Một điểm được gọi là kì dị nếu quá nửa số
đoạn thẳng xuất phát từ điểm này có đầu mút còn lại là khác màu với nó.
Thực hiện thuật toán sau: Mỗi lần chọn tra một điểm kì dị và đổi màu nó.
Chứng minh rằng sau hữu hạn bước, tất cả các điểm kì dị đều bị xóa.
Hướng giải: Phương pháp cực hạn.
Bài 3.37 Xem kết quả học tập của một lớp học, người ta thấy hơn 2/3 số học
sinh đạt điểm giỏi ở môn Toán cũng đồng thời đạt điểm giỏi ở môn Vật Lý;
hơn 2/3 số học sinh đạt điểm giỏi ở môn Vật Lý cũng đồng thời đạt điểm
giỏi ở môn Ngữ văn; hơn 2/3 số học sinh đạt điểm giỏi ở môn Ngữ văn cũng
đồng thời đạt điểm giỏi ở môn Lịch sử; hơn 2/3 số học sinh đạt điểm giỏi
ở môn Lịch sử cũng đồng thời đạt điểm giỏi ở môn Toán. Chứng minh rằng
tồn tại ít nhất một học sinh đạt điểm giỏi ở cả bốn môn nêu trên.
66
www.VNMATH.com
Hướng dẫn: Nguyên lý bù trừ.
Bài 3.38 Cho trước n là số tự nhiên lẻ lớn hơn 1, với mỗi hoán vị a =
(a1, a2, ..., an) trong số n! hoán vị của 1, 2, ..., n, ta đặt
S(a) =
n∑
i=1
2iai
Chứng minh rằng tồn tại 2 hoán vị b và c, b khác c sao cho n! là một ước số
của S(b)− S(c).
Hướng dẫn: Phương pháp phản chứng.
Bài 3.39 Một hình tròn được chia thành 6 hình quạt bằng nhau, trong mỗi
hình quạt đặt một quân cờ. Mỗi lần cho phép chuyển một quân cờ ở một
hình quạt sang một trong hai hình quạt bên cạnh. Chứng minh rằng không
thể dồn các quân cờ vào một hình quạt sau 2006 lần thực hiện.
Hướng dẫn : Xây dựng hệ thức truy hồi.
Bài 3.40 Cho P1, P2, ..., Pn là n điểm trên cùng một đường tròn. Cho p ∈
N, 2 ≤ p ≤ n. Có bao nhiêu cách tô màu n diểm đã cho bằng p màu sao
cho hai điểm kề nhau được tô bởi hai màu khác nhau.
Đáp số: a1 = p, a2 = p(p− 1), an = (p− 1)an−2 + (p− 2)an−1.
67
www.VNMATH.com
Tài liệu tham khảo
Tiếng Việt
1. Nguyễn Hữu Điển (2004), Giải toán bằng phương pháp đại lượng bất biến,
Nxb Giáo dục, Hà Nội.
2. Nguyễn Đức Nghĩa, Nguyễn Tô Thành (2004), Toán rời rạc, Nxb Đại học
Quốc gia Hà Nội, Hà Nội.
3. Nguyễn Văn Mậu, Trần Nam Dũng, Vũ Đình Hòa, Đặng Huy Ruận, Đặng
Hùng Thắng (2008), Chuyên đề chọn lọc tổ hợp và toán rời rạc, Nxb Giáo
dục, Hà Nội.
4. Ngô Đắc Tân (2004), Lý thuyết tổ hợp và đồ thị, Nxb Đại học Quốc gia
Hà Nội, Hà Nội.
Tiếng Anh
5. V.K. Balakrishnan, Ph.D (1995), Theory and problems of combinatorics,
McGraw-Hill, INC, Singapore.
6. Titu Andreescu Zuming Feng (2004), A Path to Combinatoricts for Under-
graduates ( Counting Strategies), Birkhauser Boston, United states of Amer-
ica.
68
www.VNMATH.com