ÔN THI
MÔN TOÁN RỜI RẠC
Phần 1. Chương 2. Bài toán đếm
Các công thức cơ bản trong lý thuyết tổ hợp:
Chỉnh hợp không lặp
k
n
A n(n 1)(n 2) (n k 1)= − − − +
- Chỉnh hợp lặp
k k
n
L n=

- Hoán vị không lặp P
n
= n!
- Hoán vị lặp
n 1 2 k
1 2 k
n!
P (n , n , , n )
n !n ! n !
=
- Tổ hợp không lặp
k
n
n!
C
k!(n k)!
=

Các nguyên lý đếm.
1) Nguyên lý cộng: Nếu
1 2 m
B B B B= ∪ ∪ ∪
và
i j
B B , i j∩ ≠ ∅ ∀ ≠

thì
1 2 m
B B B B= + + +

⇒

m
i
i 1
B B
=
=
∑
2) Nguyên lý nhân : Nếu
1 2 m
B B xB x xB=
thì
1 2 m
B B . B B=
3) Nguyên lý loại trừ: Nếu
A B
⊂

 
 
 
con chim (n và k nguyên dương). Trong đó
n
k
 
 
 
là số
nguyên nhỏ nhất trong các số nguyên
n
k
≥
Thí dụ + Nếu n = 21 và k = 3 thì
n
k
 
 
 
= 7 =
n
k
+ Nếu n = 22 và k = 3 thì
n
k
 
 
 
= 8 >

m m m
r C C C 2
−
= + + + =
b) Cây và cây bao trùm( cây khung)
Cây là đồ thị vô hướng liên thông và không chứa chu trình, khi đó m=n-1. Cây
chứa moị đỉnh của đồ thị là cây bao trùm.
- Định lý Kelly: Số cây bao trùm chứa trong một đồ thị vô hướng đủ có n đỉnh là:
n 2
n
T n
−
=
c) Đồ thị Euler là đồ thị chứa chu trình Euler, đó là chu trình đi qua tất các cạnh mỗi
cạnh 1 lần.
- Định lý Euler: Điều kiện cần và đủ để một đồ thị vô hướng, liên thông là đồ thị
Euler là bâc của tất cả các đỉnh đều là các số chẵn.
- Chú ý: Đồ thị đủ n đỉnh thì bậc của mọi đỉnh đều bằng n-1, nếu đồ thị này là đồ
thị Euler thì n-1 phải là số chẵn, nghiã là n phải là số lẻ. Sử dụng kiến thức này để
giải bài tập số 17 và 18.
2) Đồ thị có hướng.
a) Bài toán tìm đường đi ngắn nhất và thuật toán Dijkstra.
1
1
1
( ) ( , )
k
i i
i
w P w v v

2. Một người 10 quân, một người 12 quân, một người 14 quân và một
người 16 quân.
Bài 3.
1. Có bao nhiêu cách chia 7 quyển vở cho 5 em bé sao cho em nào cũng
được nhận vở?
2. Có bao nhiêu cách gọi 5 sinh viên để trả lời 7 câu hỏi khác nhau sao
cho sinh viên nào cũng được gọi để trả lời câu hỏi?
Bài 4. Phương trình x
1
+ x
2
+ x
3
+ x
4
= 8 có bao nhiêu nghiệm nếu:
1. x
i
≥ 0 ( i = 1,4 ) và nguyên.
2. x
i
nguyên ( i = 1, 4 ); x
1
≥ 1, x
2
≥ 1, x
3
≥ 1, x
4
≥ 2

1. Cả 3 nữ ngồi gần nhau.
2. Có đúng 2 nữ ngồi gần nhau.
3. Cả 3 nữ không ngồi gần nhau.

Bài 11. Có 4 đề thi khác nhau được phát cho 10 sinh viên dự thi, mỗi sinh viên
một đề sao cho 2 sinh viên ngồi gần nhau thì nhận được 2 đề khác nhau.
Hỏi có bao nhiêu trường hợp khác nhau nếu :
1. Các sinh viên ngồi thành một dãy ngang ?
2. Các sinh viên ngồi thành 2 dãy ngang cách biệt, mỗi dãy 5 người?
3. Các sinh viên ngồi quanh một bàn tròn trên 10 ghế có ghi số?

Bài 12. Có 5 câu hỏi thi khác nhau, mỗi câu hỏi thi được in thành 2 phiếu.
Giáo viên phát cho 5 sinh viên dự thi mỗi sinh viên 2 phiếu.
Hỏi có bao nhiêu trường hợp mà :
1.Tất cả 5 sinh viên đều nhận được 2 câu hỏi khác nhau ?
2. Có đúng 3 sinh viên nhận được 2 câu hỏi khác nhau ?
Bài 13. Cho hình cầu tâm O bán kính R. Vẽ n đường tròn lớn ( có tâm O và bán
kính
R như hình cầu ); trong đó không có 3 đường tròn nào cùng đi qua một
điểm. Ký hiệu T
n
là số phần mặt cầu tạo nên bởi n đường tròn đó.
1. Lâp và giải phương trình truy hồi để tìm công thức của T
n
. Tính T
10
.
2. Tính T
10
trong trường hợp có 3 đường tròn cùng đi qua một điểm.

2
+ T
2
2
+ … + T
n
2
= T
n
. T
n+1
- 1

Bài 16 Một người phải trả 1 món tiền n nghìn đồng bằng cách trả lần lượt từng
tờ một trong 2 loại giấy bạc có mệnh giá 1 nghìn đồng và 2 nghìn đồng.
Ký hiệu T
n
là số cách trả tiền như thế.
1. Lập và giải phương trình truy hồi đối với T
n
.
2. Bằng phương pháp quy nạp chứng minh rằng:
T
1
.T
2
+ T
2
.T
3


Bài 3. Lấy một cách tuỳ ý 7 điểm trong một hình lục giác đều có cạnh bằng 1.
Chứng minh rằng luôn tìm được 2 điểm có khoảng cách < 1.
Bài4. Lấy 6 số bất kỳ trong các số nguyên dương nhỏ hơn 121.
Chứng minh rằng trong các số đó luôn tìm được ít nhất 2 số x và y
mà │
x
-
y
│ < 2

Bài 5. Lấy 30 số nguyên dương nhỏ hơn 60. Chứng minh rằng:
1. Có ít nhất 8 cặp số mà hiệu của chúng bằng nhau.
2. Có ít nhất 4 cặp số mà tổng của chúng bằng nhau.

Bài 6. Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
1. Có bao nhiêu tập con gồm 4 phần tử của A?
2. CMR có ít nhất 8 tập con mà tổng các chữ số của chúng bằng nhau.
.
Bài 7. Có 11 sinh viên nữ và 9 sinh viên nam xếp ngẫu nhiên thành một hàng
ngang . CMR có ít nhất 2 nữ sinh viên mà giữa họ có 4 người khác
đứng xen vào.

Bài 8. Xếp 12 quân cờ một cách tuỳ ý lên một bàn cờ vua có 8x8=64 ô vuông.
Chứng minh rằng luôn tìm được 4 hàng và 4 cột chứa tất cả 12 quân cờ nói
trên.

Bài 9. Cho A = {1,2,3,…, 21}. Hỏi có thể chia A thành các nhóm rời nhau và
trong mỗi nhóm số lớn nhất bằng tổng các số còn lại của nhóm được
hay không?