Tổng hợp BT môn Toán rời rạc| Môn Toán rời rạc| Trường Đại học Bách Khoa Hà Nội

2.1 Các nguyên lý đếm cơ bản 23
Định lý 2.7 Cho n tập hữu hạn A1, A2, . . . , An. Khi đó, n
|A1 ∪ A2 ∪ ... ∪ An| = ∑ (−1)k−1 ∑
|Ai ∩ A ∩ ... ∩ A |. 1 i2 ik k=1 1≤i12<... 2.1.6 Bài tập
1. Khóa 59 của viện Toán ứng dụng và Tin học có 23 sinh viên định
hướng Toán và 95 sinh viên định hướng Tin.
(a) Hỏi có bao nhiêu cách chọn ra hai đại diện sinh viên sao cho
có một sinh viên định hướng Tin và một sinh viên định hướng Toán?
(b) Hỏi có bao nhiêu cách chọn ra một đại diện sinh viên định hướng Tin hoặc Toán?
2. Bài thi trắc nghiệp có 10 câu hỏi, mỗi câu sinh viên chỉ được chọn một trong bốn đáp án.
(a) Hỏi có bao nhiêu cách sinh viên làm bài nếu sinh viên đó trả
lời tất cả các câu hỏi?
(b) Hỏi có bao nhiêu cách sinh viên làm bài nếu sinh viên đó có
thể bỏ trống phần trả lời?
3. Tính số chuỗi nhị phân độ dài n và số chuỗi nhị phân độ dài không quá n.
4. Tính số chuỗi nhị phân độ dài n có tính chất: không thay đổi khi
viết theo thứ tự ngược.
5. Có bao nhiêu chuỗi nhị phân độ dài 10 bắt đầu bằng hai chữ số 1
hoặc kết thúc bằng 3 chữ số 0.
6. Có bao nhiêu chuỗi nhị phân độ dài 10 chứa hoặc 5 chữ số 0 liên
tiếp hoặc 5 chữ số 1 liên tiếp.
7. Có bao nhiêu chuỗi nhị phân độ dài 10 rơi vào chỉ một trong hai
khả năng hoặc 4 chữ số 0 liên tiếp hoặc 5 chữ số 1 liên tiếp?
8. Có bao nhiêu số nguyên dương không vượt quá 100 chia hết cho hoặc 4 hoặc 6? 24 Bài toán đếm
9. Có bao nhiêu số nguyên dương không vượt quá 100 rơi vào chỉ một
trong hai khả năng hoặc chia hết cho 4 hoặc chia hết cho 6?
10. Mã Morse: Trong hệ mã Morse, mỗi chữ cái trong đươc biểu diễn
bằng một chuỗi các ký hiệu telex gồm các "chấm" và "vạch". Tính
số chữ cái chó thể biểu diễn được bằng chuỗi n ký hiệu.
11. Một bảng chữ cái, một cách tổng quát, là một tập hợp L = {l1, l2,..., ln}
gồm n chữ cái khác nhau. Một bộ k chữ cái của bảng chữ cái L là
một k-từ. Tính số 3-từ của bảng chữ cái L, số 3-từ không cho phép
lặp lại chữ cái và số 3-từ chứa chữ cái ln.
12. Trong một lớp trung học có 40 học sinh. Trong số đó có 14 thích
học môn toán, 16 thích môn vậy lý, và 11 thích môn hóa học. Đồng
thời, bảy học sinh thích cả toán và lý, tám thích cả lý và hóa, năm
thích cả toán và hóa, bốn thích cả ba môn. Hỏi có bao nhiêu học
sinh không thích cả toán, lý lẫn hóa.
13. Sử dụng nguyên lý cộng chứ minh nguyên lý nhân.
2.2 Hoán vị, chỉnh hợp và tổ hợp
Nhiều bài toán đếm có thể đưa về bài toán tìm số cách sắp xếp một số
phần tử đặc biệt của một tập hơp theo một thứ tự nào đó. Cũng có nhiều
bài toán giải bằng việc tìm số cách chọn một số phần tử từ một tập hợp
nào đó mà không kể đến thứ tự. Ví dụ, tìm số cách chọn ra ban chấp hành
chi đoàn thanh niên gồm ba thành viên từ một chi đoàn có 15 thành viên.
Trong phần này chúng ta sẽ tìm hiểu các công cụ liên quan đến những bài toán dạng này.
2.2.1 Chỉnh hợp và hoán vị
Định nghĩa 2.2 Một hoán vị của một tập hợp gồm các đối tượng khác
nhau là một thứ tự sắp xếp các đối tượng này.
Nếu chỉ chọn ra k phần tử để sắp xếp thì được gọi là k-chỉnh hợp.
Một k-chỉnh hợp của tập hợp n số tự nhiên đầu tiên {1, 2,..., n} được
2.2 Hoán vị, chỉnh hợp và tổ hợp 27 n!
Định lý 2.10 Số chỉnh hợp vòng chập k của n k·(n−k)!. Đặc biệt số
hoán vị vòng của tập gồm n phần tử là (n − 1)!
Ví dụ 2.9 Có bao nhiêu cách xếp sáu sinh viên ngồi trên một bài tròn
trong đó có hai sinh viên không thích ngồi cạnh nhau? Lời giải:
Chỉnh hợp lặp và tổ hợp lặp 2.2.4 Bài tập
1. Có bao nhiêu cách xếp bốn sinh viên An, Bình, Cường, Dũng thành
một hàng dọc sao cho Bình không đứng ngay sau An.
2. Đoàn tàu thống nhất có hai toa hành lý, một toa ăn, năm toa giường
nằm và ba toa ghế ngồi. Hỏi có bao nhiêu cách xếp các toa?
3. Trong kỳ thi tuyển sinh đại học, một trường dựa trên kết quả thi của
bốn môn. Để đỗ, thí sinh phải đạt tối thiểu 5 điểm mỗi môn, đồng
thời tổng điểm bốn môn không thấp hơn 25. Hỏi có bao nhiêu kết
quả thi có thể để thí sinh đỗ?
4. Phương trình x1 + x2 + x3 + x4 + x5 = 20 có bao nhiêu nghiệm nguyên dương?
5. Tìm số nghiệm nguyên của phương trình
x1 + x2 + x3 + x4 + x5 = 30
với x1 ≥ 3, x2 ≥ 2, x3 ≥ 0, x4 ≥ 5 và x5 ≥ −5.
6. Có bao nhiêu cách chia mười người thành bốn cặp đôi?
7. Có bao nhiêu cách xếp tám quân xe trên bàn cờ 8 × 8 sao cho không có hai con nào ăn nhau?
8. Có bao nhiêu cách xếp 52 lá bài tú lơ khơ sao cho tất cả các quân
bài cùng chất luôn đi với nhau. 28 Bài toán đếm
9. Có bao nhiêu số tự nhiên lớn hơn 5400 sao cho (i) không có hai
chữ số nào giống nhau, (ii) chữ số 3 và 5 không xuất hiện.
10. Có bao nhiêu cách xếp năm người đàn ông ngồi xen kẽ năm người phụ nữ trên bàn tròn?
11. Có bao nhiêu cách xếp 10 người ngồi trên bàn tròn sao cho B không
ngồi cạnh A? Sao cho B không ngồi bên phải A?
12. Có bao nhiêu cách chọn một hội đồng năm người từ một câu lạc
bộ gồm 8 người đàn ông và 10 người phụ nữ sao cho có ít nhất hai
người phụ nữ được chọn? Sao cho có thêm điều kiện người đàn
ông A và người phụ nữ B không cùng có trong hội đồng?
13. Có bao nhiêu tập ba số nguyên lấy trong các số từ 1 đến 20 không
chứa hai số nguyên liên tiếp?
14. Đội tuyển thi olympic sinh viên toán gồm 12 sinh viên, 7 người thi
đại số và 5 người thi giải tích, được chọn từ 15 người trong đó 4
người có thể thi đai số, 5 người có thể thi giải tích và 6 người có
thể thi cả hai môn. Hỏi có bao nhiêu cách chọn đội tuyển có thể?
15. Một lớp học có hai hàng ghế, mỗi hàng có 8 ghế. Có 14 sinh viên,
trong đó 6 sinh viên chỉ ngồi ở hàng bên trái, 5 sinh viên chỉ ngồi
ở hàng bên phải. Hỏi có bao nhiêu cách xếp chỗ các sinh viên này?
16. Một bữa tiệc có 10 người đàn ông và 15 người phụ nữ.
(a) Có bao nhiêu cách ghép 10 căp đôi gồm một người đàn ông và một người phụ nữ?
(b) Có bao nhiêu cách ghép 8 cặp đôi gồm một người đàn ông và một người phụ nữ?
17. Sáu người thi chạy với nhau, hỏi có bao nhiêu thứ tự về đích? (cho phép hòa)
18. Có bao nhiêu cách xếp 6 sinh viên nam, 6 sinh viên nữ và một
giảng viên ngồi trên một bàn tròn sao cho không có hai sinh viên
nữ nào ngồi cạnh nhau, không có hai sinh viên nam nào ngồi cạnh
nhau? Câu hỏi tương tự nếu có hai giảng viên?
19. Một giải bóng đá có 20 đội. Ba đội đứng đầu sẽ được nhận cúp
vàng, bạc và đồng tương ứng. Ba đội đứng cuối sẽ xuống hạng. Hai 2.3 Công thức truy hồi 29
kết quả của giải đấu được xem là giống nhau nếu các đội đoạt cúp
vàng là giống nhau, tương tự cho cúp bạc và đồng, các đội xuống
hạng là giống nhau. Hỏi có bao nhiêu kết quả có thể của giải đấu?
20. Trong một bữa tiệc có n người, mọi người được ghép cặp nói chuyện
với nhau theo từng đôi (có một người không có người nói chuyện
nếu số người dự tiệc là số lẻ). Tính số cách ghép cặp có thể?
21. Có bao nhiêu cách xếp 2n + 1 cuốn sách phân biệt lên ba giá sách
sao cho hai giá bất kỳ có tổng số sách lớn hơn giá còn lại?
22. Chứng minh các đẳng thức sau r m r r − k (a) m k = k m − k n m1 m2 m1 + m2 (b) ∑ k n − k = n k=0 n n n 1 2n + 1 2n (c) ∑ k n − k = n + 1 − n k=1 2 n n
(d) n(n + 1)2n−2 = ∑ k2 k k=1 n n 2 2n − 1 (e) ∑ k k = n n − 1 k=1
23. Tìm số hoán vị tập {1, 2,..., 9} sao cho không có số lẻ nào ở đúng vị trí ban đầu.
24. Tìm số hoán vị tập {1, 2,..., 9} sao cho có đúng 5 số ở đúng vị trí ban đầu.
25. Tìm số hoán vị tập {1, 2,..., 9} sao cho có ít nhất một số chẵn ở đúng vị trí ban đầu. 2.3 Công thức truy hồi 2.3.1
Khái niệm công thức truy hồi
Ví dụ 2.10 Dãy số Fibonacci 32 Bài toán đếm 2(2n + 1)
Định lý 2.18 C0 = 1 và Cn+1 = n + 2 Cn Số mất thứ tự
Định nghĩa 2.4 Cho số nguyên dương n, số mất thứ tự, ký hiệu Dn
hoặc !n là số hoán vị của tập hợp n phần tử sao cho không có phần tử
nào xuất hiện ở vị trí ban đầu. Định lý 2.19
!n = (n − 1)(!(n − 1)+!(n − 2) với 0! = 1,!1 = 0. Định lý 2.20 n (−1)i
!n = n! ∑ i! i=0 n ! n
n = n! − ∑ ·!(n − i) i i=1
!n = n[!(n − 1)] + (−1)n
Bài toán phủ bằng các quân cờ domino 2.3.3 Bài tập
1. Cho a và b là các số nguyên dương với a là ước của b. Chứng minh
rằng một bàn cờ m × n có thể phủ được bằng các hình a × b khi và
chỉ khi a là ước của cả m và n và b là ước của m hoặc ước của n.
2. Một bàn cờ 6 × 6 được phủ bởi 18 quân domino. Chứng minh rằng
có thể cắt dọc hoặc ngang bàn cờ mà không có quân domino nào bị cắt. 2.3 Công thức truy hồi 33
3. Đường cắt trong bài 2 được gọi là đường chia. Phủ bàn cờ 8 × 8
bằng các quân cờ domino sao cho không có đường chia. n(n + 1)
4. Cho Sn là bàn cờ dạng bậc thang có 2 ô. Chứng minh rằng
Sn không thể phủ được bằng các quân cờ domino. n n 5. = n − 1 2 n 6. = 2n−1 − 1 2 7. n = 2n−1 − 1 2 n 1 1
= 3n−1 − 2n−1 + 3 2 2 n 1
= 34n−1 − 3n−1 − +2n−1) + 13 4 2 n 1
= 45n−1 − 4n−1 + 323n−1 + 2n−1 − 14 5 3! 8. 1 ! n! n! n = = + , n ≥ 1 e e 2
!n = (e + e−1)n! − en!, n ≥ 2 n+1 2 n − i
9. Chứng minh rằng số Fibonacci thứ n, fn = ∑ i − 1 i=1
10. Gọi f (n) là số Fibonacci thứ n. Cho m và n là các số nguyên dương. .
(a) Chứng minh rằng nếu m..n thì f (m)... f (n).
(b) Cho d = CLN(m, n). Chứng minh rằng f (d) = CLN( f (m), f (n))
11. Số Lucas là các số l0, l1,..., ln,..., ln+1 = ln + ln−1, giống dãy số
Fibonacci nhưng với điều kiện đầu khác l0 = 2, l1 = 1. Chứng minh rằng
(a) ln = fn−1 + fn+1 với n ≥ 1. 34 Bài toán đếm
(b) l20 + l21 + ... + l2 = n
lnln+1 + 2, với n ≥ 0.
12. Tìm công thức truy hồi của hn là số phần của mặt phẳng được chia
bởi n đường thẳng đôi một cắt nhau trong đó không có ba đường thẳng nào đồng quy.
13. Cho đa giác đều 2n đỉnh. Tìm công thức truy hồi của hn là số cách
nối các cặp đỉnh sao cho không có 2 đoạn thẳng nào cắt nhau. Tìm
công thức truy hồi cho hn. 2.4 Hàm sinh 2.4.1 Khái niệm hàm sinh
Trong phần này, chúng ta sẽ nghiên cứu về công cụ hàm sinh để giải bài
toán đếm. Về cơ bản, hàm sinh là chuỗi Taylor (chuỗi khai triển lũy thừa),
nghĩa là hàm khả vi vô hạn lần. Nếu chúng ta có thể tìm được hàm và
chuỗi Taylor của nó thì hệ số của chuỗi Taylor cho ta nghiệm của bài
toán. Về cơ bản, trong phần này, chúng ta không xem xét tính hội tụ của
chuỗi mà sẽ thao tác trên các chuỗi lũy thừa một cách hình thức. Cho {hn}∞
n=0 là một dãy số
h0,h1,...,hn,....
Khi đó hàm sinh của dãy số là chuỗi số ∞
g(x) = ∑ hnxn = h0 +h1x+h2x2 +···+hnxn +··· . n=0
Chúng ta cũng quy ước nếu dãy số hay chuỗi số được đánh thứ tự bắt đầu
từ h1 thì xem h0 = 0.
Về cơ bản, phương pháp sử dụng hàm sinh hoặc sẽ cho chúng ta công
thức tường mình cho bài toán đếm, hoặc các hệ số trong biểu diễn chuỗi
sẽ cho chúng ta đáp án bài toán đếm.
Hai ví dụ đơn giản nhất của dãy cấp số cộng, còn gọi là dãy số học
h0,h0 + q,h0 + 2q + ldots,h0 + nq,... 2.4 Hàm sinh 37 Định lý 2.21
c(x) = 1 + xc(x)2 ∞ 2n xn
c(x) = ∑ n n n=0 + 1 Số mất thứ tự Số Euler
Bài toán phủ bằng các quân cờ domino 2.4.5 Bài tập
Cho số thực α và số nguyên không âm k, ký hiệu α
α(α − 1)...(α − k + 1) k = k!
1. Viết hàm sinh của các dãy số sau α α α (a) 0 , 1 ,..., n ,...
(b) 1, c, c2,..., cn,...
(c) 1, −1, 1, −1,..., (−1)n,... α α α (d) 0 ,− 1
,...,(−1)n n ,... 1 1 1 (e) 1, , ,..., ,... 2 3 n −1 1
(f) 0, 1, 0,
,0, ,0,...,0,(−1)n 1 ,0,... 3 5 2n + 1
(g) 0, 1, 8, 27,..., n3,... 0 1 n (h) 3 , 3 ,..., 3 ,...
2. Cho đa giác n + 2 đỉnh nội tiếp một đường tròn sao cho không có
ba đường chéo nào thẳng hàng. Gọi hn là số phần của đa giác tạo
nên bởi các đường chéo. 38 Bài toán đếm
(a) Tìm công thức truy hồi cho hn.
(b) Xây dựng hàm sinh cho hn.
(c) Tìm công thức tường minh cho hn.
3. Viết hàm sinh mũ của các dãy số sau
(a) 0, 1, 0, −1, 0, 1, 0,..., 0, (−1)n, 0,...
(b) 1, 0, −1, 0, 1, 0,..., 0, (−1)n, 0,...
4. Cho hn là số nghiệm nguyên không âm của phương trình e1 + e2 +
e3 + e4 = n. Tìm hn, với điều kiện
(a) Các số ei là số chẵn.
(b) Các số ei là bội của 3.
(c) e1 = 0, e2 ≥ 3, e3 ≤ 4.
(d) e1 là 1, 3 hay 5, e2 là 2 hay 4. (e) Các số ei ≥ 5.
5. Tìm số nghiệm nguyên không âm của phương trình 2e1 + 3e2 +
e3 + 4e4 = n. n ∞ 6. Cho dãy hn = 2 , viết hàm sinh cho dãy. n=0
7. Cho hn là số cách tô bàn cờ 1 × n bằng k màu phân biệt. Tìm hàm
sinh mũ của dãy {hn}∞
n=0, với điều kiện
(a) Mỗi màu đều được sử dụng chẵn lần.
(b) Mỗi màu được sử dụng ít nhất ba lần.
(c) Mỗi màu được sử dụng không quá 4 lần.
(d) Màu thứ nhất được sử dụng số lẻ lần, màu thứ hai được sử
dụng với số lần là số chia ba dư 1.
(e) Màu thứ nhất được sử dụng 1 lần, màu thứ 2 2 lần, . . . , màu thứ k k lần.
(f) Màu thứ nhất được sử dụng không quá 1 lần, màu thứ 2 không
quá 2 lần, . . . , màu thứ k không quá k lần.
8. Cho hn là số chuỗi tam phân (chuỗi gồm các ký tự ’0’, ’1’, ’2’) độ n ∞
dài n. Tìm hàm sinh mũ của dãy hn = 2 và công thức n=0
tường minh cho hn biết rằng
2.5 Giải công thức truy hồi tuyến tính hệ số hằng 39
(a) Số ký tự ’0’ là lẻ, số ký tự ’1’ là chẵn.
(b) Sô ký tự ’0’ và ’1’ đều là số lẻ.
(c) Số ký tự ’0’ và ’1’ đều là số chẵn khác không.
(d) Tìm số số có n chữ số sao cho các chữ số đều xuất hiện ít
nhất 2 lần. Chữ số 0 xuất hiện không quá 3 lần. Các chữ số
chẵn xuất hiện lẻ lần và các chữ số xuất hiện chẵn lần. 2.5
Giải công thức truy hồi tuyến tính hệ số hằng 2.5.1
Công thức truy hồi thuần nhất 2.5.2
Công thức truy hồi không thuần nhất 2.5.3
Sử dụng hàm sinh giải công thức truy hồi
Khái niệm hàm sinh có thểđược mở rộng cho trường hợp chuỗi chỉ số
kép hay tổng quát hơn chuỗi đa chỉ số. Định nghĩa 2.5 Cho
{an,k}∞n=0,k=0 = {a0,0,a{0,1},a1,0,a1,1,a0,2,a{2,0},a1,2,a2,1,a2,2,...,
k = 0,1,... và n = 0,1,... là dãy (chỉ số kép). Tổng vô hạn ∞ ∞
g(x,y) = ∑ ∑ an,kxkyn n=0 k=0
được gọi là hàm sinh (hai biến x, y) của dãy {an,k}∞n=0,k=0. Tổng vô hạn ∞ ∞ xk yn
g(x,y) = ∑ ∑ an,k k n n=0 k=0 ! !
được gọi là hàm sinh mũ của dãy {an,k}∞n=0,k=0. n
Ví dụ 2.12 Xét dãy {an,k = k
}∞k,n=0. Sử dụng công thức nhị thức 40 Bài toán đếm Newton, ta có 2.5.4 Bài tập
1. Giả sử ban đầu Fibonacci thả 3 đôi thỏ. Tìm số thỏ tại thời điểm tháng thứ n.
2. Cho bàn cờ 1 × n. Tô các ô của bàn cờ bằng các màu xanh hoặc đỏ.
Gọi h(n) là số các tô màu sau cho không có hai ô đỏ nào kề nhau
(chung cạnh hoặc chung đỉnh). Tìm công thức đệ quy cho h(n).
Tìm công thức tường minh cho h(n).
3. Cho bàn cờ 1 × n. Tô các ô của bàn cờ bằng các màu xanh, đỏ hoặc
trắng. Gọi h(n) là số các tô màu sau cho không có hai ô đỏ nào
kề nhau (chung cạnh hoặc chung đỉnh). Tìm công thức đệ quy cho
h(n). Tìm công thức tường minh cho h(n).
2.6 Một số chủ đề nâng cao
2.6.1 Mười hai công thức đếm
2.6.2 Một số phương pháp chứng minh đẳng thức tổ hợp
Phương pháp đếm kép
Phương pháp song ánh
Phương pháp phần tử đặc biệt 2.6.3 Bài tập
1. Tung một quân xúc sắc n lần, tính xác suất để tổng số điểm thu được chia hết cho 5.
2. Chứng minh rằng: với mọi 0 < n ∈ N: n 2 n 2n − 1 n n − 1 = ∑ k k k=1
2.6 Một số chủ đề nâng cao 41
3. Trên hình vuông ABCD ta định nghĩa đường đi giữa hai đỉnh
X; Y (không nhất thiết phân biệt) là một dãy các đỉnh kề nhau
X = X0 → X1 → X2 → ··· → Xn = Y. Như vậy, X0,X1,...,Xn là
các đỉnh của hình vuông và XiXi+1 là cạnh của hình vuông, số n
được gọi là độ dài của đường đi. Với mỗi số tựnhiên n, gọi xn; yn;
zn tương ứng là số các đường đi độ dài n giữa: một đỉnh và chính
nó, một đỉnh và một đỉnh cố định kề nó, một đỉnh và đỉnh đối diện
(đỉnh đối xứng qua tâm). Ví dụ, x0 = 1; y0 = 0; z0 = 0; x1 = 0;
y1 = 1; z1 = 0; x2 = 2; y2 = 0; z2 = 2.
(a) Thiết lập công thức truy hồi cho xn; yn; zn.
(b) Tìm công thức tổng quát của xn; yn; zn.
4. Có bao nhiêu ma trận vuông cấp n có đúng n + 1 phần tử bằng 1,
các phần tử còn lại bằng 0 và có định thức bằng 1?
5. Cho n đường tròn đôi một giao nhau, nghĩa là hai đường tròn bất
kỳ trong đó có hai điểm chung. Ba đường tròn trong đó không có
điểm chung. Các đường tròn này chia mặt phẳng ra thành bao nhiêu phần? 44
Xây dựng cấu hình tổ hợp Nguyên lý cực trị
Trong một tập hữu hạn phần tử luôn tồn tại phần tử cực trị. Trong một
tập các số nguyên dương luôn tồn tại số nhỏ nhất.
Ví dụ 3.3 Chứng minh rằng 3.1.2
Một số bài toán tồn tại kinh điển Hình vuông Latin Trò chơi Sudoku
Hình vuông Latin trực giao Ma Phương
Hình lục giác thần bí Bài toán bốn màu
Bài toán hệ đại diện phân biệt 3.1.3
Phương pháp xác suất 3.1.4 Bài tập
1. Kỳ thi olympic toán sinh viên có 200 sinh viên tham gia. Đề thi
bao gồm 6 bài. Biết rằng mỗi bài có ít nhất 120 sinh viên giải được.
Chứng minh rằng luôn tìm được hai sinh viên sao cho ít nhất một
người trong đó giải được cả 6 bài.
2. Giả sử mỗi điểm nguyên (điểm có các tọa độ là hai số nguyên)
trong mặt phẳng được tô bằng một trong hai màu xanh hoặc đỏ.
Chứng minh rằng luôn tồn tại một hình chữ nhật có các đỉnh cùng màu.
3. Một kỳ thủcó 11 tuần để chuẩn bị cho giải đấu muốn luyện chơi ít
nhất một trận mỗi ngày, nhưng để tránh mệt mỏi, không muốn có 3.1 Bài toán tồn tại 45
7 ngày kế tiếp nhau nào đó chơi 12 trận. Chứng minh rằng luôn có
một dãy ngày kế tiếp nhau trong đó kỳ thủnày chơi đúng 21 trận.
4. Trong 37, một sinh viên mỗi ngày học ít nhất một giờ. Biết rằng
tổng số giờ học của sinh viên đó không quá 60 giờ. Chứng minh
rằng có một chuỗi ngày kế tiếp sinh viên đó học tổng cộng đúng 13 giờ.
5. Cho dãy gồm m số nguyên, chứng minh rằng ta luôn có thể tìm
được một dãy con có tổng chia hết cho m.
6. Chọn 101 số từ các số 1, 2, . . . , 200. Chứng minh rằng trong 101
số này ta luôn chọn được hai số chia hết cho nhau.
7. Hai đĩa, một lớn một nhỏ, mỗi đĩa được chia thành 200 hình quạt
đều nhau. Các hình quạt được sơn một trong hai màu xanh hoặc
đỏ. Đĩa lớn có đúng 100 hình quạt được sơn màu đỏ và 100 hình
sơn màu xanh. Chứng minh rằng ta luôn có thể đặt hai đĩa trùng
tâm nhau sao cho màu ở hai đĩa là khớp nhau tại ít nhất 100 hình quạt.
8. Chọn n + 1 số từ tập {1, 2,..., 3n}. Chứng minh rằng trong số đó
luôn tìm được hai số có hiệu không quá 2.
9. Chứng minh rằng trong 52 số nguyên luôn chọn được hai số có
tổng, hoặc hiệu chia hết cho 100.
10. Chứng minh rằng mọi số hữu tỉ đều là số thập phân hữu hạn hoặc vô hạn tuần hoàn.
11. Trong một căn phòng có 10 người có tuổi từ 1 đến 60. Chứng minh
rằng ta luôn tìm được trong số này hai nhóm người (rời nhau) có
tổng số tuổi những người trong nhóm là bằng nhau.
12. Chứng minh rằng trong một nhóm n người luôn có ít nhất hai người
có cùng số người quen trong nhóm.
13. Một bữa tiệc có 100 người. Mỗi người có một số chẵn người quen
trong bữa tiệc. Chứng minh rằng có ít nhất ba người có cùng số
người quen trong bữa tiệc.
14. Chứng mình rằng trong 9 điểm nằm trong một hình lập phương √
cạnh 2, có hai điểm cách nhau không quá 3. 46
Xây dựng cấu hình tổ hợp
15. Chứng minh rằng trong 5 điểm nằm trong một tam giác đều cạnh 1
1, có hai điểm cách nhau không quá 2.
16. Cho 10 điểm không thẳng hàng được nối bằng các đoạn thẳng tô
màu xanh hoặc đỏ. Chứng minh rằng luông tồn tại ba điểm sao cho
ba đoạn thẳng nối chúng được tô màu đỏ hoặc bốn điểm sao cho
sáu đoạn thẳng nối chúng được tô màu xanh.
17. Bộ các tập con khác nhau của tập gồm n phần tử có tính chất hai
tập bất kỳ có ít nhất một phần tử chung. Chứng minh rằng số tập
của bộ không vượt quá 2n−1.
18. Có n chiếc hộp chứa các quả bóng (không có hộp nào rỗng). Các
quả bóng được lấy hết ra và cho vào n + 1 hộp khác sao cho hộp
mới nào cũng có bóng. Chứng minh rằng có hai quả bóng sao cho
(các) hộp mới chứa chúng chứa ít bóng hơn so với (các) hộp cũ chứa chúng.
19. Cho n điểm trên mặt phẳng, không đồng thời thẳng hàng. Chứng
minh rằng luôn tồn tại một đường thẳng đi qua đúng hai điểm.
20. Trên mặt phẳng cho một số hữu hạn hình tròn bán kính đôi một
khác nhau sao cho hai hình bất kỳ có không quá một điểm chung.
Chứng minh rằng tồn tại một hình tròn tiếp xúc với không quá năm hình tròn khác.
21. Trên một bàn cờ vô hạn, mỗi ô được ghi một số nguyên dương sao
cho mỗi số là trung bình cộng của 4 số ghi tại 4 ô kề cạnh với nó.
Chứng minh rằng tất cả các số được ghi trên bàn cờ là bằng nhau.
22. Viết các số từ 1 đến n2 lên một bàn cờ n × n. Chứng minh rằng
luôn tồn tại hai số sao cho được viết trên hai ô kề cạnh hoặc kề góc
nhau sao cho hiệu của chúng không nhỏ hơn n + 1.
23. Cho n điểm xanh và n điểm đỏ trên mặt phẳng sao cho không có
ba điểm nào thẳng hàng. Chứng minh rằng tồn tại n đoạn thẳng nối
một điểm xanh với một điểm đỏ sao cho không có hai đoạn nào cắt nhau.
24. Cho một tập S gồm hữu hạn các điểm trên mặt phẳng sao cho tam
giác tạo bởi ba điểm bất kỳ trong S có diện tích không quá 1. Chứng 3.2 Bài toán liệt kê 47
minh rằng tồn tại tam giác diện tích không quá 4 chứa toàn bộ S.
25. Cho n điểm trên mặt phẳng được tô hai màu xanh và đỏ sao cho
trên đoạn thẳng nối hai điểm cùng màu bất kỳ luôn có một điểm
khác màu. Chứng minh rằng n điểm này thẳng hàng. 3.2 Bài toán liệt kê 3.2.1 Giới thiệu
Giới thiệu bài toán liệt kê
Mã hóa cấu hình tổ hợp 3.2.2
Đại cương về thuật toán
Khái niệm thuật toán
Ngôn ngữ lập trình và giả mã
Các cấu trúc cơ bản của thuật toán 3.2.3
Phương pháp liệt kê
Sinh cấu hình kế tiếp
Thuật toán đệ quy quay lui 3.2.4
Một số bài toán liệt kê cơ bản Liệt kê hoán vị
Liệt kê các tập con Liệt kê tổ hợp
Phân hoạch số tự nhiên
Phân hoạch tập hợp 3.3 Thiết kế tổ hợp Toán rời rạc Bài tập 1 Bài 1
Hãy chứng minh rằng có vô hạn số nguyên tố. Bài 2
Dùng nguyên lý Sắp thứ tự tốt để chứng minh rằng: với mọi số nguyên không âm n, ta luôn có n ≤ 3n/3 (1)
Gợi ý: Hãy kiểm tra (1) với các giá trị n ≤ 4. Bài 3
Với n = 40 giá trị của đa thức p(n) ::= n2 + n + 41 không phải là số nguyên tố. Ta dự
đoán rằng, ngoại trừ các đa thức hằng số, không có đa thức nào chỉ sinh ra các giá trị là các số nguyên tố.
Cụ thể, xét đa thức q(n) với hệ số nguyên dương, và xét c ::= q(0) là số hạng hằng số của q(n).
(a) Chứng minh rằng q(cm) là bội của c với mọi m ∈ Z.
(b) Chứng minh rằng nếu đa thức q không phải đa thức hằng số và c > 1, thì tập
{q(n) | n ∈ N}
chứa vô hạn số không nguyên tố.
(c) Kết luận rằng với mọi đa thức q không phải hằng số, có một số nguyên n sao
cho q(n) không là số nguyên tố. Bài 4
Chứng minh rằng trong một nhóm gồm 9 người luôn có bốn người đôi một quen nhau
hoặc ba người đôi một lạ nhau. Toán rời rạc Bài tập 3
Bài 1: Chứng minh sai
Tìm lỗi sai trong chứng minh dưới đây rằng an = 1 với mọi số nguyên không âm n và a là số thực không âm.
Chứng minh. Ta sẽ chứng minh quy nạp theo n, với giả thiết
P(n) := ∀k ≤ n. ak = 1,
trong đó k là biến nhận giá trị nguyên không âm.
Bước cơ sở: P(0) tương đương với a0 = 1 đúng theo định nghĩa của a0 (kể cả khi a = 0).
Bước quy nạp: Giả sử ak = 1 với mọi k ∈ N thỏa mãn k ≤ n. Nhưng vậy thì an · an 1 · 1 an+1 = = = 1 an−1 1
kéo theo P(n + 1) đúng.
Vậy bởi quy nạp P(n) đúng với mọi n ∈ N, có nghĩa rằng an = 1 đúng với mọi n ∈ N.
Bài 2: Bài toán ô chữ
Trong một trò chơi ô chữ, có 15 chữ cái và một ô trống đặt trên một lưới 4 × 4. Một bước
chuyển gọi là hợp lệ nếu chữ cái chỉ di chuyển sang ô trống kề với nó. Ví dụ, một dãy gồm
hai bước chuyển được mô tả như sau:
Trong cấu hình trái nhất ở hình trên, chữ O và N là sai thứ tự. Liệu có cách chuyển hợp lệ
để có thể hoán đổi vị trí của O và N mà vẫn giữ nguyên vị trí của các chữ khác, và vị trí ô
trống vẫn ở góc phải bên dưới của lưới? Trong bài toán này, bạn sẽ chứng minh câu trả lời là “không thể".
Định lý. Không tồn tại dãy chuyển để đưa từ cấu hình bên trái dưới đây sang cấu hình bên phải. 1
(a) Ta định nghĩa một “thứ tự” của các chữ trên lưới là dãy đi từ dòng trên xuống dòng
dưới, và với mỗi dòng đi từ trái qua phải. Ví dụ, trong lưới bên phải thứ tự các chữ là
A, B, C, D, E, . . . .
Liệu việc di chuyển một chữ theo hàng có làm thay đổi thứ tự trước sau của các cặp
chữ? Có nghĩa rằng, liệu có cặp chữ (L ) 1, L2
thỏa mãn L1 đứng trước L2 nhưng sau khi
di chuyển một chữ theo hàng lại làm L1 đứng sau L2? Chứng minh câu trả lời của bạn.
(b) Có bao nhiêu cặp chữ bị thay đổi thứ tự sau mỗi lần di chuyển một chữ theo cột? Chứng
minh câu trả lời của bạn.
(c) Một cặp chữ (L ) 1, L2
gọi là ngược nếu L1 đứng trước L2 theo thứ tự từ điển, nhưng L1
lại đứng sau L2 theo thứ tự định nghĩa ở câu (a). Ví dụ, cấu hình sau đây:
có đúng bốn cặp ngược: (D, E), (G, H), (F, H) và (F, G).
Việc chuyển một chữ theo hàng ảnh hưởng đến tính chẵn lẻ của số các cặp ngược như
thế nào? Chứng minh câu trả lời của bạn.
(d) Việc chuyển một chữ theo cột ảnh hưởng đến tính chẵn lẻ của số các cặp ngược như
thế nào? Chứng minh câu trả lời của bạn.
(e) Chứng minh bổ đề sau đây:
Bổ đề. Trong mỗi cấu hình đạt được từ cấu hình dưới đây, tính chẵn lẻ của số các cặp
ngược khác với tính chẵn lẻ của hàng chứa ô trống.
(f) Từ các nhận xét (a)–(e), hãy chứng minh định lý đã đưa ra ở trên. Bài 3: Robot
Một robot đi trên một lưới nguyên hai chiều. Nó bắt đầu tại điểm (0, 0), và di chuyển mỗi
bước theo một trong bốn cách sau:
1. (+2, −1): sang phải 2 bước, đi xuống 1 bước.
2. (−2, +1): sang trái 2, đi lên 1 3. (+1, +3) 4. (−1, −3) 2