Bài giải toán rời rạc ( Đề thi sau Đại học)

GIẢI ĐỀ THI TOÁN RỜI RẠC SAU ĐẠI HỌC
Câu I
1- Dùng quy tắc suy diễn chứng minh rằng :


Giải


--------------

tương đương của (2)

tương đương của (3)

tam đoạn luận của (4) và (5)

tương đương của (1)

tương đương của (7)

tam đoạn luận của (6) và (8)
2- Có
quả cầu, trong đó là
quả cầu đỏ còn lại là trắng, được xếp trong một số hộp sao cho trong mỗi hộp có không quá
quả cầu đỏ. Chứng minh rằng luôn có thể tìm được hai hộp chứa cùng một số lượng quả cầu.
Giải
Gọi
là số hộp, nhận xét rằng

Gọi
là số quả cầu trong hộp
theo thứ tự tăng dần.
Giả sử rằng không có hai hộp nào chứa cùng số lượng quả cầu, vậy :





, suy ra

Vậy

Vì
nên mỗi hộp có đúng
quả cầu đỏ, suy ra :





: vô lý
Câu II
1- Giải hệ phương trình bool :


Giải


Kết quả :
+ x=1, y=1, u=0, z tùy ý
+ x=1, y=0, u=1, z tùy ý
2- Tìm công thức tối tiểu bằng phương pháp Karnaugh của hàm bool 4 biến
có dãy nhị phân được cho như sau :


Giải
Sơ đồ Karnaugh và cell lớn





Ô (2,1) nằm duy nhất trong cell 3.
Ô (4, 3) nằm duy nhất trong cell 4
Chọn tiếp tục :
3/4/1/6/8 :

3/4/2/5/7 :

Câu III
1- Hỏi có bao nhiêu dãy nhị phân có chiều dài
mà mỗi dãy hoặc bắt đầu bằng
chữ số giống nhau hoặc kết thúc bằng
chữ số giống nhau.
Giải
Số dãy nhị phân có chiều dài
là :

Số dãy nhị phân bắt đầu bằng
chữ số khác nhau và kết thúc bằng
chữ số khác nhau là :

Số dãy nhị phân hoặc bắt đầu bằng
chữ số giống nhau hoặc kết thúc bằng
chữ số giống nhau :


2- Có
câu hỏi và
câu trả lời đúng cho
câu hỏi đó. Ghép ngẫu nhiên mỗi câu hỏi với một câu trả lời. Tính xác suất để ghép đúng với ít nhất
câu trả lời.
Giải
Số cách ghép là :

Số cách ghép đúng đúng 2 câu :

Số cách ghép đúng đúng 3 câu :

Số cách ghép đúng đúng 4 câu :

Số cách ghép đúng đúng 5 câu :

Xác suất ghép đúng ít nhất 2 câu là :

Câu IV
1- Một đồ thị vô hướng có
cạnh,
đỉnh. Mỗi đỉnh đều có bậc lớn hơn hoặc bằng
. Chứng minh rằng :


Giải
Nhận xét : tổng số bậc = 2 lần số cạnh là

Theo đề bài thì : tổng số bậc

Suy ra :

2- Dùng giải thuật Dijkstra tìm đường đi ngắn nhất từ đỉnh
đến các đỉnh còn lại trên đồ thị có hướng
có ma trận trọng số được cho như sau :


1
2
3
4
5
6

1

7
1




2



4

1

3

5


2
7

4







5

2

5



6




3


Giải
Khởi tạo :
G
1
2
3
4
5
6



2,3
4,6
2,5,6


2,4
5



0
7
1







p(i)

1
1





Giải thuật :
Chọn i = 3
Chọn i = 5
Chọn i = 2
Chọn i = 6
Chọn i = 4

Bảng kết quả :

G
1
2
3
4
5
6



0
5
1
8
3
6

p(i)

5
1