TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN

Đề thi toán rời rạc Hutech có lời giải
Đề số: 62
Câu 1: Cho đường tròn tâm O bán kính R. Vẽ n đường tròn nhỏ nằm ở miền trong
đường tròn đã cho sao cho mọi cặp đường tròn nhỏ đều cắt nhau nhưng không có 3
đường tròn nào cùng đi qua một điểm. Các đường tròn này chia miền trong của
đường tròn (O, R) thành Tn phần.
1) Lập và giải phương trình truy hồi để tìm công thức của Tn. Tính T10.
2) Tính T10 trong trường hợp có 3 đường tròn cùng đi qua 1 điểm.
Trả lời:
1) *Tìm công thức Tn:
Gọi Tn là số phần mặt phẳng được tạo ra bởi n đường tròn
Theo điều kiện ban đầu ta có:
Tn = Tn-1 + 2 ( n-1 )
Ta suy ra:
T1 = 2 = 2 + 2.0
T2 = 2 + 2.1
T3 = 4 + 2.2 = 2 + 2 (1+2)
T4 = 8 + 2.3 = 2 + 2 (1+2+3)
T5 = 14 + 2.4 = 2 + 2 (1+2+3+4)
……
Tn = 2 + 2 [ 1+2+3+…+ (n-1) ]
<=> Tn = 2 + 2.

n (n−1)
2

<=>Tn = 2 + n (n-1)
https://ttnguyen.net/

TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN
*Tính T10 :
T10 = 2 + 10 (10-1) = 92.
2) Tính T10 trong trường hợp có 3 đường tròn cùng đi qua 1 điểm:
 Theo điều kiện ban đầu thì ta có:
Tn = Tn-1 + n
Ta suy ra:
T1 = 2 = T0 + 1 = 1+1
T2 = 4 = T1 + 2 = 1+1+2
T3 = 7 = T2 + 3 = 1+1+2+3
T4 = 11 = T3 + 4 = 1+1+2+3+4
T5 = 16 = T4 +5 = 1+1+2+3+4+5
…..
Tn = Tn-1 + n = 1+1+2+3+ … +n
<=> Tn = 1 +

n ( n+1 )
2

 Tính T10:
T10 = 1 +

10 (10+1)
2

= 56

Câu 2: Bỏ ngẫu nhiên 6 bức thư vào 6 phong bì đề sẵn địa chỉ. Hỏi có bao nhiêu
cách bỏ thư trong các trường hợp sau đây:
1) Không có bức thư nào đúng địa chỉ
2) Có 3 bức thư đúng địa chỉ và 3 bức thư sai địa chỉ
Trả lời:
Bỏ 6 bức thư vào 6 phong bì có ghi sẵn địa chỉ

https://ttnguyen.net/

TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN
Gọi Dn là số cách bỏ 6 bức thư sao cho không bức thư nào đúng địa chỉ. Cách bỏ
thư thỏa mãn yêu cầu bài toán số mất thứ tự:
Ta có: D1 = 0
D2 = 1
D3 = 2 = (3 – 1).(1 + 0)
D4 = 9 = (4 – 1).(2 + 1)
……
Dn = (n – 1).( Dn-1 + Dn-2 )
Vậy ta có công thức truy hồi: Dn = (n – 1).( Dn-1 + Dn-2 )
1) Số cách để bỏ 6 bức thư không có bức thư nào đúng địa chỉ là:
D6 = (6 – 1).(D5 + D4) = 5.(44 + 9) = 265 (cách)
2) Số cách để 3 bức thư đúng địa chỉ và 3 bức thư sai địa chỉ là:
C36 . D3 = C36 . 2 = 40 (cách)
Câu 3: Có bao nhiêu cách xếp chỗ cho 5 gia đình, mỗi gia đình có 3 người quanh
một bàn tiệc tròn có 15 chiếc ghế sao cho những người trong một gia đình thì
ngồi gần nhau? Giải bài toán trên trong trường hợp 15 ghế được xếp thành 1 dãy
ngang.
 Xếp bàn tròn:
Số cách xếp gia đình thứ nhất là: 15. 3! = 90 (cách)
Mỗi cách sắp xếp gia đình đầu tiên sẽ có số cách: 4! 3! 3! 3! 3! (cách)
Nên cách sắp xếp những gia đình còn lại là: 15.3!4!(3!)4 (cách)
 Xếp bàn thẳng:
Coi mỗi gia đình là 1 nhóm
Nên ta có số cách sắp xếp 5 nhóm là: 5! (cách)
Trong mỗi nhóm lại có số cách sắp xếp là: 3! (cách)

https://ttnguyen.net/

TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN
Nên cách sắp xếp các thành viên là: 5! . (3!)5 (cách)

Câu 4: Cho A ={ 1, 2, 3, 4, 5, 6, 7, 8, 9}. Chứng minh rằng trong số các tập con gồm
4 chữ số của A có ít nhất 8 tập có tổng các chữ số là phần tử của chúng bằng nhau.
Trả lời:
A= {1, 2, 3, 4, 5, 6, 7, 8, 9}
Số tập con gồm 4 phần tử của A là: C49 = 126 (tập)
Tập có tổng các chữ số lớn nhất là: Smax = 6 + 7 + 8 + 9 = 30
Tập có tổng các chữ số nhỏ nhất là: Smin = 1 + 2 + 3 + 4 = 10
126 tập con có tổng các chữ số là các phần tử của chúng lấy giá trị từ 10 đến
30, gồm 21 giá trị khác nhau.
Ta loại trừ tập có tổng là 10, 11 là 2 tập có tổng là giá trị nhỏ nhất, không còn
tập gồm 4 số nào có thể bằng một trong hai giá trị trên nên ta loại 2 giá trị 10
và 11.
Tương tự, 2 tập có tổng là 29, 30 là 2 tập có tổng là giá trị lớn nhất, không còn
tập gồm 4 số nào có thể bằng một trong hai giá trị trên, nên ta loại 2 giá trị 29,
30 ra khỏi vùng xét.
Với tập con có tổng bằng 12, ta có thể tìm được các cặp 4 số như sau : có 2 cặp
thỏa mãn là : (1; 2; 3; 6) với (1; 2; 4; 5)
Với tập con có tổng bằng 28, cũng chỉ có 2 cặp là : (9; 8; 7; 4) với (9; 8; 6; 5)
Ta cũng loại 4 giá trị trên ra khỏi vùng xét.
Như vậy, số tập con còn lại là: 126 - 8 = 118 (tập)
Với 118 tâp con có tổng các chữ số từ 13 đến 27 gồm 15 giá trị khác nhau
Theo định lí Dirichlet sẽ có ít nhất

https://ttnguyen.net/

]

118
15

[=8

TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN
Vậy sẽ có ít nhất 8 tập con có tổng các chữ số bằng nhau.

Câu 5:
1, Cho đồ thị vô hướng, đủ, có 9 đỉnh. Hỏi:
A, Có bao nhiêu đồ thị bộ phận?
B, Có bao nhiêu đồ thị con là đồ thị Euler?
C, Có bao nhiêu đồ thị con không là đồ thị Euler?
2, Áp dụng thuật toán Kruskal,tìm cây bao trùm ngắn nhất trên đồ thị dưới đây:

a

a

Bài giải:
1, Đồ thị đã cho là đồ thị vô hướng, đủ,có 8đỉnh nên ta có số cạnh là:
C29 = 36(cạnh)
A, Số đồ thị bộ phận của đồ thị đã cho có từ 0 đến 27 cạnh là:
i
36
r =∑35
𝑖=0 𝐶 36 = 2 -1

B,Số đồ thị con là đồ thị Euler là: t = C39 + C59 + C79 =246
C,Số đồ thị con không là đồ thị Euler là: u = C29 + C49 + C69 = 246
2, - Đồ thị A là Euler, vì A là đồ thị liên thông và tất cả các đỉnh có bậc là bậc
chẵn. Chu trình Euler được biểu diễn theo đường mũi tên trên hình vẽ A.
-

Đồ thị B, C không phải là Euler hoặc nửa Euler.

https://ttnguyen.net/

TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN
- Đồ thị D là đồ thị nửa Euler, vì D là đồ thị liên thông và có đúng 2 đỉnh bậc
lẻ tại đỉnh a và b. Chu trình nửa Euler được biểu diễn theo đường mũi tên
như hình D.
Câu 6: Cho hàm đại số logic F(x, y, z) = (x|y)  (y↓z)
1) Lập bảng giá trị của hàm F(x, y, z)
2) Tìm dạng hội chuẩn tắc và biến đổi nó về dạng chỉ có dấu hội và phủ định.
3) Thiết kế mạch logic thực hiện hàm F(x, y, z) với các cổng NOT,AND và OR
Bài giải:
a) Bảng chân lý:
x
y
z
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

(x|y)

(y↓ z)

(x|y)  (y↓ z)

1
1
1
1
1
1
0
0

1
0
0
0
1
0
0
0

1
0
0
0
1
0
1
1

H1 = 𝑥̅ ˄⋀ 𝑦̅ ˄⋀𝑧̅
T1 = 𝑥 ˅⋁𝑦 ⋁˅ 𝑧̅
T2 = 𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧
T3 = 𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧̅
H2 = 𝑥 ˄⋀ 𝑦̅ ⋀𝑧̅
T4 = 𝑥̅ ˅⋁𝑦⋁ ˅ 𝑧̅
H3 = 𝑥 ⋀ ˄𝑦⋀ ˄𝑧̅
H4 = 𝑥 ⋀ ˄𝑦 ⋀˄ 𝑧

b) Dạng hội chuẩn tắc:
F(x, y, z) = T1 ˄⋀ T2 ˄⋀ T3 ˄⋀T4 = (𝑥 ˅⋁𝑦 ⋁˅ 𝑧̅) ˄⋀(𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧)
˄⋀( 𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧̅) ˄⋀(𝑥̅ ˅⋁𝑦⋁ ˅ 𝑧̅)
= (𝑥 ˅⋁𝑦 ⋁˅ 𝑧̅) ˄⋀(𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧) ˄⋀( 𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧̅) ˄⋀(𝑥̅ ˅⋁𝑦⋁ ˅ 𝑧̅)
= (𝑥̅ ⋀˄𝑦̅ ⋀𝑧) ˄⋀ (𝑥̅ ⋀𝑦˄⋀𝑧̅) ˄⋀ (𝑥̅ ⋀𝑦⋀𝑧) ˄⋀ (𝑥˄⋀𝑦̅⋀𝑧)
c) Thiết kế mạch logic:
F(x, y, z) = (𝑥 ˅⋁𝑦 ⋁˅ 𝑧̅) ˄⋀(𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧) ˄⋀( 𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧̅) ˄⋀(𝑥̅ ˅⋁𝑦⋁ ˅ 𝑧̅)

https://ttnguyen.net/

TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN

Mạch logic:
𝑥 ˅⋁𝑦 ⋁˅ 𝑧̅

X

Y

z

𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧

X

Y

z

F(x, y, x)
𝑥 ˅⋁𝑦̅ ⋁˅ 𝑧̅

X

Y

z

𝑥̅ ˅⋁𝑦⋁ ˅ 𝑧̅

X

Y

AND

z
OR

Câu 7: Áp dụng thuật toán Dijkstra, tìm đường đi ngắn nhất từ S đến Z trên đò thị
dưới đây:

4

1

3

S

7

6

9

6
2

https://ttnguyen.net/

5

8

Z

TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN

Bài làm
Gọi L là đường đi ngắn nhất từ S đến Z
Ta gán 0 cho đỉnh S => λ (S) = 0.
+ Trong các đỉnh không thuộc L = {S} và kề với S có 4 đỉnh 1,2,3,5. Ta có:
λ (1) = min { λ (s) + l(s,1)} = min {0 + 8} = 8.
λ (2) = min { λ (s) + l(s,2)} = min {0 + 6} = 6.
λ (3) = min { λ (s) + l(s,3)} = min {0 + 15} = 15
λ (5) = min { λ (s) + l(s,5)} = min {0 + 22} = 22
Ta có: λ (2) nhỏ nhất nên 2  L.  L = {S,2}.
+ Trong các đỉnh không thuộc L mà kề với 2 có 2 đỉnh là 3,5
λ (3) = min { λ (2) + l(2,3)} = min{6+6} = 12
λ (5) = min { λ (2) + l(2,5)} = min{6+14} =20
Ta có: λ (3) nhỏ nhất nên 3  L  L = {S,2,3}
+ Trong các đỉnh không thuộc L mà kề với 3 có 3 đỉnh là 4,5,6
λ (4) = min { λ (3) + l(3,4)} = min{12+8} = 20
λ (5) = min { λ (3) + l(3,5)} = min{12+7} = 19
λ (6) = min { λ (3) + l(3,6)} = min{12+17} =29
Ta có: λ (5) nhỏ nhất nên 5  L  L = {S,2,3,5}
+ Trong các đỉnh không thuộc L mà kề với 5 có 3 đỉnh là 6,8,9
λ (6) = min { λ (5) + l(5,6)} = min{19+9} = 28
λ (8) = min { λ (5) + l(5,8)} = min{19+18} = 37
λ (9) = min { λ (5) + l(5,9)} = min{19+26} =45
https://ttnguyen.net/

TOÁN RỜI RẠC-KHOA CÔNG NGHỆ THÔNG TIN
Ta có: λ (6) nhỏ nhất nên 6  L  L = {S,2,3,5,6}
+ Trong các đỉnh không thuộc L mà kề với 6 có 3 đỉnh là 7,8,9
λ (7) = min { λ (6) + l(6,7)} = min{28+8} = 36
λ (8) = min { λ (6) + l(6,8)} = min{28+8} = 36
λ (9) = min { λ (6) + l(6,9)} = min{28+16} =44
Ta có: λ (7) = λ (8) và nhỏ nhất nên xét 2 trường hợp
Th1: λ (7)
+ Trong các đỉnh không thuộc L mà kề với 7 có 2 đỉnh là 9 và Z
λ (9) = min { λ (7) + l(7,9)} = min{36+7} = 43
λ (Z) = min { λ (7) + l(7,Z)} = min{36+22} = 58
Th2: λ (8)
+ Trong các đỉnh không thuộc L mà kề với 8 có 2 đỉnh là 9 và Z
λ (9) = min { λ (8) + l(8,9)} = min{36+9} = 45
λ (Z) = min { λ (8) + l(8,Z)} = min{36+25} = 61
Ta có: λ (7) đến 9 và Z nhỏ hơn L(8) đến 9 và Z => 7  L  L =
{S,2,3,5,6,7}
Nhìn vào Th1 ta có L(9) nhỏ nhất nên 9  L  L = {S,2,3,5,6,7,9}
+ Các đỉnh kề với 9 mà không thuộc L : Z
λ (Z) = min { λ (9) + l(9,Z)} = min{43+15} = 58 = min {L(7) + l(7,Z)} =
min{36+22}
Vậy, đường đi ngắn nhất từ S đến Z là: S,2,3,5,6,7,9,Z hoặc S,2,3,5,6,7,Z với độ
dài là 58

https://ttnguyen.net/