Tài liệu tham khảo Toán 12 từ cơ bản đến nâng cao

a đánh dấu ít nhất bao nhiêu
điểm.
65
66 CHƯƠNG 6. CÁC ĐỀ TOÁN TỔ HỢP CHỌN LỌC
Bài toán 6.8. Có một con ếch tại mỗi đỉnh của 2n giác đều (n > 1). Tại một thời điểm tất
cả các con ếch nhảy đến các đỉnh kề cùng một lúc (có thể có nhiều hơn một con ếch nhảy đến
cùng một đỉnh), chúng ta gọi đó là một cách nhảy. Biết rằng tồn tại một cách nhảy sao cho
đường thẳng chứa mỗi cặp 2 đỉnh phân biệt có ếch trên nó sau khi nhảy, không đi qua tâm
của đa giác đều. Tìm tất cả các giá trị có thể của n.
Bài toán 6.9. Cho tập hợp S = {1, 2, ..., n} và P = {P1, P2, ..., Pn} là các tập hợp các tập
con có 2 phần tử của S thoả mãn điều kiện |Pi ∩ Pj | = 1 nếu và chỉ nếu (i, j) ∈ P . Chứng
minh rằng mỗi phần tử của S thuộc đúng 2 phần tử của P .
Bài toán 6.10. Cho n viên sỏi và 2 người A,B chơi một trò chơi như sau. Đầu tiên A lấy
k viên sỏi với 1 ≤ k ≤ n− 1 sau đó B lấy t viên sao cho 1 ≤ t ≤ k. Cứ như thế cho đến hết,
người nào lấy được viên sỏi cuối cùng là người chiến thắng. Hỏi A có chiến lược luôn thắng
hay không.
Bài toán 6.11. Một tứ giác đều cạnh 1 bị phủ kín bởi 6 đường tròn bán kính R. Chứng minh
rằng R ≥ √3/10.
Bài toán 6.12. Trong một lớp học mỗi bạn nam quen với ít nhất một bạn nữ. Chứng minh
rằng có thể chọn một nhóm gồm nhiều hơn một nửa số thành viên của lớp mà mỗi bạn nam
quen với một số lẻ bạn nữ trong nhóm.
Bài toán 6.13. Trong một câu lạc bộ có 42 thành viên. Biết rằng cứ 31 thành viên bất kỳ
thì có một đôi nam nữ quen nhau. Chứng minh rằng từ các thành viên của câu lạc bộ có thể
chọn ra 12 đôi nam nữ quen nhau.
Bài toán 6.14. Cho Sn = {1, 2, ..., n}. giả sử A1, A2, ..., An là n tập con khác rỗng của Sn.
Đặt k = [n/2]+ 1. Chứng minh rằng tồn tại k tập Ai1, Ai2, ..., Aik trong các tập Ai mà tồn tại
hai tập hợp con X của Sn để |Aij ∩X| là số lẻ với mọi 1 ≤ j ≤ k.
Bài toán 6.15. Cho bảng ô vuông n.n gồm các số nguyên không âm aij. Biết rằng với mọi
i, .j thì tổng tất cả các số ở hàng i và cột j đều không nhỏ hơn n. Chứng minh rằng:∑
i,j
aij ≥ n
2
2
.
Bài toán 6.16. Cho đồ thị lưỡng phân với 2 tập đỉnh A1, A2, ..., An và B1, B2, ..., Bn. Biết
Ai nối với Bi với mọi 1 ≤ i ≤ n và Ai nối với Bj nếu và chỉ nếu Aj nối với Bi. Chứng minh
rằng tồn tại tập các điểm:
S = {Ai1, Ai2, ..., Aik}
sao cho với mỗi số Bi số cạnh nối Bi với một đỉnh thuộc S là lẻ.
Bài toán 6.17. Có tồn tại hay không n > 2 điểm trong mặt phẳng sao cho không có ba điểm
nào thẳng hàng và các tâm đường tròn ngoại tiếp của mọi tam giác có các đỉnh là các điểm
đó cũng là một trong n điểm đó.
Bài toán 6.18. Cho số nguyên n > 2. Tìm số nguyên m lớn nhất sao cho nếu với n túi, mỗi
túi chứa một vài quả cầu, mỗi quả cầu có khối lượng là một luỹ thừa nguyên của 2 (trong mỗi
túi khối lượng các quả cầu không nhất thiết phân biệt) và tổng khối lượng của tất cả các quả
cầu trong mỗi túi là bằng nhau, thì tồn tại ít nhất m quả cầu có cùng khối lượng trong tất cả
các quả cấu đã được chia vào n túi.
67
Bài toán 6.19. Trên bảng ban đầu có n số 1 (n ≥ 2). Cứ sau mỗi lần ta lấy 2 số tuỳ ý a, b
và thay chúng bởi số
a+ b
4
. Sau n− 1 lần thì trên bảng còn lại một số duy nhất. Tìm giá trị
lớn nhất, nhỏ nhất của số đó.
Bài toán 6.20. Cho trước số nguyên dương N . Hai người A,B chơi một trò chơi như sau.
Bắt đầu từ người A viết số N lên bảng, sau đó mỗi người viết số m thì người sau viết số m−1
hoặc [m/2]. Ai viết được số 1 trước thì thắng cuộc. Hỏi ai là người thắng cuộc, vì sao?
Bài toán 6.21. 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 khảo. Một nhóm thí sinh được gọi là chấp nhận được 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 rằng cứ 6 giám khảo thì có 2 thí sinh là
nhóm chấp nhận được với cả 6. Chứng minh rằng có thể chọn được 10 thí sinh là nhóm chấp
nhận được với tất cả các thành viên trong ban giám giảo.
Bài toán 6.22. Có 101 thành phố. Biết giữa hai thành phố bất kì thì có 1 đường bay một
chiều hoặc không có đường bay nào cả.
i) Biết rằng mỗi thành phố có 50 đường bay đến, 50 đường bay đi. Chứng minh rằng với
2 thành phố bất kì A và B ta có thể bay từ A đến B mà chỉ phải dừng tại nhiều nhất 1 thành
phố C.
ii) Biết rằng mỗi thành phố có 40 đường bay đến, 40 đường bay đi. Chứng minh rằng với
thành phố bất kỳ A và B ta có thể bay từ A đến B mà chỉ phải dừng tại nhiều nhất 2 thành
phố C1, C2.
Bài toán 6.23. Cho trước số nguyên dương n ≥ 12 và một tập hợp X có n phần tử. F là
một họ gồm các tập con 4 phần tử của X sao cho giao của mỗi cặp tập con phân biệt trong
F có nhiều nhất 2 phần tử. Chứng minh rằng có một tập con S của X chứa ít nhất 3
√
6n − 6
phần tử sao cho không có tập con 4 phần tử nào của S nằm trong họ F .
Bài toán 6.24. Cho số nguyên dương chẵn n và A1, A2, ..., An là n tập con của tập S =
{1, 2, .., n} sao cho i ∈ Ai∀i ∈ S và i ∈ Aj nếu và chỉ nếu j ∈ Ai với i 6= j. Chứng minh rằng
tồn tại i 6= j mà |Ai ∩Aj| là số chẵn.
Bài toán 6.25. Trong một căn phòng có 2005 cái hộp, mỗi hộp chứa một hoặc vài loại trái
cây là táo chuối và nho. Dĩ nhiên số trái cây là nguyên. Chứng minh rằng có thể tìm được
669 hộp sao cho toàn bộ chúng chứa ít nhất 1/3 của tất cả số táo và ít nhất 1/3 tất cả số
chuối. Liệu có phải luôn luôn tìm được 669 hộp sao cho toàn bộ chúng chứa ít nhất 1/3 tất
cả số táo, ít nhất 1/3 tất cả số chuối và ít nhất 1/3 tất cả số nho.
Bài toán 6.26. Ta gọi bộ số x = (x1.x2, ..., xn) là một vecto trong không gian n chiều. Với
hai vecto trong không gian n chiều là x = (x1, x2, ..., xn) và y = (y1, y2, ..., yn) ta ký hiệu
xy =
n∑
i=1
xiyi là tích vô hướng của 2 vecto x, y. Giả sử rằng f(n) là số lớn nhất mà tồn tại
f(n) vecto khác 0 mà tích vô hướng của 2 vecto bất kì đều không dương. Chứng minh rằng
f(n) ≤ n.
68 CHƯƠNG 6. CÁC ĐỀ TOÁN TỔ HỢP CHỌN LỌC
Bài toán 6.27. Cho tập hợp A có n phần tử và n tập con nhiều hơn 1 phần tử của nó là
A1, A2, ..., An. Giả sử rằng với mọi tập con 2p phần tử A
′ ∈ A có duy nhất một tập con Ai
của A′. Chứng minh rằng với 2 tập bất kì trong n tập ban đầu có chung duy nhất một phần
tử.
Bài toán 6.28. Cho n là một số nguyên dương và tập hợp các bộ số sau:
Sn = {(a1, a2, ..., an)|ai ∈ [0, 1],∀i = 1, n}.
Với hai phần tử a = (a1, a2, ..., a2n), b = (b1, b2, ..., b2n) ∈ Sn. Định nghĩa khoảng cách d(a, b) =
2n∑
i=1
|ai − bi|. Chúng ta gọi tập hợp con A ∈ Sn là tốt nếu d(a, b) ≥ 2n−1 thoả mãn với mọi cặp
phần tử phân biệt a, b của A. Hỏi một tập con tốt của Sn có thể có nhiều nhất bao nhiêu phần
tử.
Bài toán 6.29. Giả sử tập hợp A ∈ {(a1, a2, ..., an)|ai ∈ R,∀i = 1, n}. Định nghĩa hàm
khoảng cách như sau: với mỗi a = (a1, a2, ..., a2n), b = (b1, b2, ..., b2n) ∈ A đặt:
γ(a, b) = (|a1 − b1|, |a2− b2|, ..., |an− bn|).
Xét tập hợp D(A) = {γ(a, b)|a, b ∈ A}. Chứng minh rằng |D(A)| ≥ |A|.
Bài toán 6.30. Cho một tập hợp gồm k dãy nhị phân đôi một khác nhau có độ dài lần lượt
là n1, n2, ..., nk. Giả sử rằng không tồn tại dãy nhị phân 0, 1 nào mà ta có thể biểu diễn bằng
cách đặt liên tiếp các số n1, n2, ..., nk (không nhất thiết khác nhau) bằng hai cách khác nhau.
Chứng minh rằng:
1
2n1
+
1
2n2
+ ...+
1
2nk
≤ 1.
Bài toán 6.31. Cho bảng vuông n.n với n > 1. Hãy tìm tất cả các cách tô màu bằng hai
màu đen trắng sao cho không có hai ô đen nào kề nhau và bất kỳ ô trắng nào cũng kề với ít
nhất hai ô đen.
Bài toán 6.32. Chứng minh rằng không thể có nhiều hơn 4096 cây nhị phân độ dài 24 sao
cho 2 cây bất kỳ trong chúng có ít nhất 8 vị trí khác nhau.
Bài toán 6.33. Trong một buổi dạ tiệc có 2n người gồm nam và nữ. Họ ngồi trên một cái
bàn tròn. Hãy tìm tất cả n sao cho với mọi cách ngồi ta luôn có thể chia họ thành n cặp nam
nữ mà hai người cùng cặp không ngồi cạnh nhau.
Bài toán 6.34. Cho tập hợp hữu hạn M gồm ít nhất hai số thực dương khác nhau. Biết rằng
với bất kỳ a ∈M tồn tại các số b, c ∈M (a, b, c không nhất thiết phân biệt) sao cho a = 1+ b
c
.
Chứng minh rằng tồn tại hai số x, y ∈M (x 6= y) sao cho x+ y > 4.
Bài toán 6.35. Cho số nguyên dương n > 2. Hãy tìm số các số nguyên a thoả mãn điều kiện
tồn tại song ánh f : {1, 2, .., n} → {1, 2, .., n} mà |f(i)− i| = a ∀i = 1.n.
Bài toán 6.36. Xét 2000 đường tròn bán kính 1 trên mặt phẳng sao cho không có hai đường
tròn nào tiếp xúc nhau và mỗi đường tròn cắt ít nhất 2 đường tròn khác. Hãy tìm giá trị nhỏ
nhất của số giao điểm của các đường tròn này.
69
Bài toán 6.37. Cho các số nguyên dương n, k thoả mãn n = 2k − 1 và k ≥ 6. Giả sử
T = {x = (x1, x2, ..., xn)|xi ∈ [0, 1],∀i = 1, n}. Định nghĩa hàm khoảng cách d(x, y) là số các
chỉ số j sao cho xj 6= yi. Giả sử tồn tại các tập con S của T với 2k phần tử thoả mãn với mỗi
phần tử x ∈ T tồn tại duy nhất phần tử y ∈ S sao cho d(x, y) ≤ 3. Chứng minh rằng n = 23.
Bài toán 6.38. Cho các số nguyên dương n, k. Trong mặt phẳng n đường tròn được bố trí
sao cho hai đường tròn tuỳ ý cắt nhau tại 2 điểm phân biệt và không có ba đường tròn nào
cùng đi qua một điểm. Các giao điểm được tô bởi 1 trong n màu, mỗi màu được dùng ít nhất
một lần, trên mỗi đường tròn có đúng k màu. Tính k, n để việc tô màu có thể thực hiện được.
Bài toán 6.39. Với mỗi cặp số khác nhau (x, y) của tập hợp hữu hạn phần tử X ta gán cho
nó một số là f(x, y) bằng 0 hoặc 1 sao cho f(x, y) 6= f(y, x) ∀x 6= y. Chứng minh rằng có
đúng một trong các tính chất sau là đạt được:
i) X là hợp của 2 tập rời nhau khác rỗng U, V sao cho f(u, v) = 1 ∀u ∈ U, v ∈ V .
ii) Các phần tử của X có thể gán cho x1, x2, ..., xn thoả mãn f(x1, x2) = f(x2, x3) = ... =
f(xn, x1).
Bài toán 6.40. Giả sử rằng trên đường tròn đã có n ô (n ≥ 3). Mỗi ô đã được viết một trong
hai ký hiệu 0, 1. Một phép toán thực hiện theo luật sau. Chọn một ô C nào đó có ký hiệu 1,
biến đổi nó thỳanh 0 và biến đổi các ký hiệu x, y trong hai ô kề với ô C thành 1 − x, 1 − y.
Trạng thái ban đầu có một ô mang ký hiệu 1 còn các ô khác mang ký hiệu 0. tìm các giá trị
n msao cho sau một số hữu hạn bước thực hiện phép toán trên ta có thể đưa các ký hiệu trên
các ô về toàn là 0.
Bài toán 6.41. Từ được định nghĩa là một số có 10 chữ số chỉ gồm các số 0, 1. Một phép
biến đổi một từ là chọn một số các chữ số liên tiếp trong từ sao cho tổng của chúng là một số
chẵn rồi dảo ngược các số đó. Hai từ được gọi là đồng nghĩa nếu sau một số làn dùng phép
biến đổi từ này có thể biến thành từ kia. Tìm số lớn nhất các từ đôi một không đồng nghĩa.
Bài toán 6.42. Cho bảng buông n.n. Trên mỗi ô vuông con của bảng có ghi duy nhất một số
nguyên dương sao cho hiệu của hai số ghi ở hai ô kề nhau là 1 hoặc −1. Chứng minh rằng ta
có thể tìm được một số nguyên dương k mà tất cả các cột chứa k hoặc tất cả các hàng chứa
k.
Bài toán 6.43. Cho bảng vuông 2n.2n với n là một số nguyên, n ≥ 2. Ta điền 2n2 số tự
nhiên từ 1 tới 2n2 vào bảng, mỗi số lặp lại 2 lần. Chứng minh rằng tồn tại một cách chọn 2n2
số tự nhiên từ 1 tới 2n2, mỗi số một lần sao cho trên mỗi hàng và mỗi cột luôn có ít nhất
một số được chọn.
Bài toán 6.44. Viết n số tự nhiên trên một đường tròn. Tìm n sao cho với mọi dãy gồm n
số tự nhiên ta luôn tìm được hai số cạnh nhau sao cho sau khi xoá chúng đi các số còn lại có
thể chia thành hai tập hợp có tổng các phần tử bằng nhau.
Bài toán 6.45. Giả sử n là một số nguyên dương, n > 1. Giả sử rằng cho 2n điểm trong
mặt phẳng, không có ba điểm nào thẳng hàng, n điểm trong chúng được tô màu xanh, n điểm
còn lại được tô màu đỏ. Một đường thẳng trong mặt phẳng được gọi là tốt nếu nó đi qua một
điểm xanh và một điểm đỏ của mỗi nửa mặt phẳng có bờ là đường thẳng này số điểm xanh
trên đó bằng số điểm đỏ. Chứng minh rằng tồn tại ít nhất hai đường thẳng tốt.
70 CHƯƠNG 6. CÁC ĐỀ TOÁN TỔ HỢP CHỌN LỌC
Bài toán 6.46. Cho bảng vuông 1983.1984 tô màu như bàn cờ vua. Trên mỗi ô trắng ta ghi
số 1 hoặc −1. Tên mỗi ô đen ta ghi tích của các ô trắng kề với nó. Biết tất cả các các ô đen
đều ghi số 1. Chứng minh rằng tất cả các số của bảng dều là số 1.
Bài toán 6.47. Người ta điền số vào 441 ô vuông của bảng vuông 21.21 sao cho tại mỗi hàng
và mỗi cột có không quá 6 giá trị khác nhau được điền vào. Chứng minh rằng có một số xuất
hiện ở ít nhất 3 hàng và ít nhất 3 cột của bảng vuông này.
Bài toán 6.48. Cho họ các đường tròn trong mặt phẳng có phần trong rời nhau từng cặp.
Mỗi đường tròn tiếp xúc với ít nhất 6 đường tròn khác của họ. Chứng minh rằng họ này có
vô hạn phần tử.
Bài toán 6.49. Giả sử N là một số nguyên dương, hai người chơi A,B lần lượt viết các số
1, 2, .., N lên bảng. A viết số 1 ở lượt đầu tiên. Từ lượt thứ 2 nếu một người viết số n thì
người tiếp theo viết số n+1 hoặc số 2n. Ai viết số N là người thắng. Ta nói N là kiểu A hay
kiểu B tuỳ theo A hay B có chiến thuật thắng. Xác định kiểu của 2004 và tìm N nhỏ nhất
lớn hơn 2004 khác kiểu với 2004.
Bài toán 6.50. Cho tập hợp n phần tử phân biệt A. Giả sử rằng các tập hợp con U1, U2, ..., Um
của A thoả mãn tồn tại số nguyên k sao cho với mọi cặp (i, j) ta có |Ui ∩ Uj | = k. Chứng
minh rằng m ≤ n.
a
Chương 7
Một số chủ đề tổ hợp chọn lọc
7.1 Bài toán Rubik lục lăng
Giới thiệu. Toán học cũng giống như một "trò chơi", bởi vì nó truyền cho những người làm
toán một khát vọng chinh phục và chiến thắng. Ngược lại để có thể chơi giỏi một trò chơi nào
đó, cần phải có những suy luận toán học logic và hợp lý dẫn đường. Rubik là một trò chơi
"trí tuệ". Hẳn các bạn đều đã từng một lần trăn trở bởi các khối màu của một chiếc rubik
lục lăng (6 mặt), và hẳn bạn đã từng trầm trồ khi được một ai đó "biểu diễn" với món đồ
chơi nho nhỏ này. Làm sao họ có thể xoay, xoay và xoay ..... để rồi cuối cùng tất cả các khối
màu hỗn độn trở về đúng vị trí của nó. Thực ra để có thể thực hiện được điều đó bạn chỉ cần
nắm được khoảng 7 kỹ thuật cơ bản.
Nhiều người lại cho rằng bởi vì việc quay rubik có thể quy về 7 thủ thuật đơn giản đó, nên
nó đã không còn gì thú vị. Sự thực là những người đó chưa hiểu nhiều lắm về rubik. Vấn đề
về các rubik là rất phong phú. Chẳng hạn đó là làm thế nào để có thể tìm ra được các thủ
thuật có ích, và tại sao lại tồn tại những thủ thuật như vậy. Đây là một câu hỏi khó, vì rằng
mối liên hệ giữa các mặt của rubik là rất "vướng víu" và không dễ để có thể tìm được mô
hình toán học tốt cho bài toán này. Tuy nhiên, vấn đề khó và thú vị đó không phải mục đích
của chúng tôi.
Trong bài viết nhỏ này chúng tôi muốn đề cập đến một kết quả tưởng chừng hiển nhiên,
nhưng đã là trăn trở của rất nhiều rubiker sành sỏi. Vấn đề của chúng ta là nếu có một ai
đó tình cờ lắp ngược đúng một khối của rubik thì liệu có thể xoay về trạng thái ban đầu hay
không. Chúng ta cần phân biệt hai trường hợp tương ứng với hai loại vị trí của một khối, ở
71
72 CHƯƠNG 7. MỘT SỐ CHỦ ĐỀ TỔ HỢP CHỌN LỌC
cạnh và ở đỉnh. Do đó cần phải giải quyết hai bài toán tương đối khác nhau.
Bài toán 7.1.1. Chứng minh rằng không thể lật ngược một khối ở cạnh của rubik mà các
khối khác vẫn ở đúng vị trí ban đầu của nó (vị trí tương đối so với các khối khác).
lời giải. Để giải quyết bài toán này ta cần tìm được một bất biến đối với phép quay hợp lệ.
Chúng ta tiến hành đánh dấu các mặt của các khối trên cạnh bằng các mũi tên như sau:
Nghĩa là ở thời điểm đầu tiên chúng ta vẽ các mũi tên theo ba vòng "bện" xung quanh
rubik. Khi đó trên mỗi khối ở cạnh thì hai mũi tên trên hai mặt của khối đó sẽ tạo thành
một trong hai hướng. Sau khi xoay, nếu hướng của một khối ở vị trí nào đó giống với huớng
của khối ô ở vị trí đó lúc đầu tiên thì ta nói đó là một khối đúng, và gọi là khối sai trong
trường hợp ngược lại.
Rõ ràng là sau mỗi lần xoay thì hiệu giữa số ô đúng và số ô sai giữ nguyên tính chẵn lẻ,
điều này suy ra từ sự kiện là một khối sai sau khi xoay đi sẽ thành khối đúng. Rõ ràng nếu
tại một thời điểm nào đó chỉ có một khối sai thì hiệu số đó là một số lẻ, trong khi đó lúc
đầu tiên (chưa xoay) hiệu này là chẵn. Vậy không thể xoay lại được cho tất cả 6mặt đều đúng.
Một kết quả tương tự mà chúng ta quan tâm đó là nếu thay khối ở cạnh bởi khối ở đỉnh thì
mọi chuyện sẽ thế nào. Một kết quả có thể đạt được ngay đó là khối ở đỉnh nếu có "xoay" đi
được thì cũng không thể quá thoải mái, hình vẽ minh hoạ dưới đây nói lên điều đó:
Tuy nhiên bài toán sau đây mới thực sự là khó và có lẽ vẫn chưa có lời giải (!?).
Bài toán 7.1.2 (Open Question). Chứng minh rằng không thể xoay một khối ở đỉnh của
rubik mà các khối khác vẫn đúng như ban đầu (vị trí tương đối so với các khối khác).
7.2. NGUYÊN LÝ BẤT BIẾN VÀ NỬA BẤT BIẾN 73
7.2 Nguyên lý bất biến và nửa bất biến
Giới thiệu. Bất biến và nửa bất biến là một công cụ quan trọng và có hiệu quả cao trong
rất nhiều các bài toán tổ hợp. Xét lớp bài toán sau: cho A,B là hai tập hợp và f là các phép
toán. Bắt đầu từ A bằng các tác động f lên các phần tử của A ta thu được f(f(A)) = f2(A).
Tiếp tục ta thu được f3(A), f4(A), . . .. Vậy bài toán đặt ra ở đây là gì? Đó là có tồn tại hay
không một số nguyên dương k mà fk(A) = B và nếu tồn tại thì liệu có chỉ ra được nó hay
không? Rõ ràng đây là một câu hỏi hay và khó. Có rất nhiều bài toán mặc dù cách phát biểu
khác xa như trên nhưng nó lại thuộc lớp bài toán trên.
7.2.1 Bất biến
Trong mục này chúng ta sẽ xét đến lớp bài toán không tồn tại k tức là không bao giờ ta nhận
được tập B từ tập A thông qua f và một trong những phương pháp đó là xây dựng một đặc
trưng ψ(X) mà nó không thay đổi trong quá trình thực hiện phép toán f và có ψ(A) 6= ψ(B).
Đặc trưng ψ(X) gọi là một bất biến. Chúng ta hãy cùng xét mấy ví dụ sau đây:
Ví dụ 7.2.1. Trên bảng số cho 10 số 1 và 11 số −1, mỗi lần cho phép lấy ra 2 số và thay
vào đó là số 1 nếu 2 số lấy ra bằng nhau và −1 nếu khác nhau. Hỏi sau 20 lần thì số còn lại
là số 1 hay không?
lời giải. Trong bài toán này dễ thấy tập A là tập gồm 10 số 1 và 11 số −1, B là tập gồm
1 số 1 và phép toán là cho phép lấy ra 2 phần tử và thay bằng tích của chúng. Do f thay
2 phần tử bởi tích của chúng nên ta dễ dàng thấy một bất biến là ψ(X) =
∏
x∈X
x. Mà ta có
ψ(A) = −1 6= 1 = ψ(B) do đó dẫn tới kết luận của bài toán.
Ví dụ 7.2.2. Cho dãy số x0 = 1, x1 = 0, x2 = 1, x3 = 0, x4 = 1, x5 = 0. Với n ≥ 0 thì xn+6
là chữ số tận cùng của số xn + xn+1 + xn+2 + xn+3 + xn+4 + xn+5. Hỏi có tồn tại k hay không
mà xk = 0, xk+1 = 1, xk+2 = 0, xk+3 = 1, xk+4 = 0, xk+5 = 1.
lời giải. Dễ thấy là A là bộ số (x0, x1, x2, . . . , x5); B = (0, 1, 0, 1, 0, 1) và:
fk(A) = (xk, xk+1, xk+2, xk+3, xk+4, xk+5).
Với phép toán f xác định:
xk+6 ≡ xk + xk+1 + xk+2 + xk+3 + xk+4 + xk+5 (mod 10).
Bây giờ ta tìm đặc trưng ψ. Với X = (c1, c2, . . . , c6) ta xét từ dạng đơn giản nhất là hàm
tuyến tính:
ψ(X) = t1c1 + t2c2 + t3c3 + t4c4 + t5c5 + t6c6 (mod 10).
Ta có:
ψ(fk+1(A)) ≡ t1xk+1 + t2xk+2 + t3xk+3 + t4xk+4 + t5xk+5 + t6xk+6 (mod 10)
≡ t6xk+(t6+ t1)xk+1+(t6+ t2)xk+2+(t6+ t3)xk+3 +(t6+ t4)xk+4+(t6+ t5)xk+5 (mod 10).
74 CHƯƠNG 7. MỘT SỐ CHỦ ĐỀ TỔ HỢP CHỌN LỌC
Như vậy là ta cần có t6 ≡ t1 (mod 10), t6 + t1 ≡ t2 (mod 10), . . . , t6 + t5 ≡ t6 (mod 10). Nên
có thể dễ dàng nhận ra t1 = 2, t2 = 4, . . . , t6 = 12 thỏa mãn. Hay:
ψ(X) = 2c1 + 4c2 + 6c3 + 8c4 + 10c5 + 12c6 (mod 10).
Vậy luôn có ψ(fk(A)) = ψ(A) = 8. Nhưng ψ(B) = 2 6= ψ(A) do đó ta không thể có B nghĩa
là không tồn tại k. Bài toán được chứng minh.
Qua ví dụ trên ta có thể thấy đối với các phần tử là các số thì ta thường tìm những hàm
tuyến tính, đa thức, . . .
Ví dụ 7.2.3. Trên bảng ô vuông vô hạn, tại ô (1, 1) có một viên bi. Cho phép bỏ bi theo quy
tắc sau: Mỗi lần lấy chọn ô (i, j) mà các ô (i+ 1, j) và (i, j + 1) đều không có bi và lấy bi ở
ô (i, j) ra khỏi bảng và đặt vào các ô (i+ 1, j) và (i, j +1) mỗi ô một viên. Hỏi bằng cách đó
ta có thể làm cho các ô (1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1) đều không có bi hay không?
lời giải. Đối với bài toán này ta quan tâm tới các ô chứa bi. Ta có mỗi trạng thái k của các
ô chứa bị trên bảng cho ta một tập hợp Xk = {(i, j)| ô (i, j) có bi} với X0 = {(1, 1)}. Ta xét
hàm ψ(X) =
∑
(i,j)∈X
s(i, j).
Ta tìm s sao cho ψ là bất biến hay ta cần ψ(Xk+1) = ψ(Xk) với mỗi k. Rõ ràng là ta có
trạng thái k+1 nhận được từ trạng thái k qua việc bỏ đi bi ở ô (i, j) và thay vào