Tài liệu tham khảo dành cho giáo viên, sinh viên cao đẳng, đại học môn Toán - Bài tập - Toán rời rạc. Đề thi năm 2008: Ta lấy ngẫu nhiên 5 bìa từ một hộp chứa 60 tấm bìa trên đó lần lượt ghi các số 10, 11, ... 69.
AMBIENT/
Chủ đề:
Nội dung Text: Bài tập học môn Toán rời rạc
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
BÀI TẬP
Câu 1. Hãy kiểm tra suy luận sau
t u
r (s t)
( p q ) r
(s u )
______________
p
Câu 2.Đề năm 2005 Kiểm tra tính đúng của suy luận sau:
x R( P( x ) Q ( x ))
x R(P( x ) Q ( x ) R( x ))
_________________________
x R(R( x ) P( x )
Câu 3.
Cho A = 1, 2,3, 4,5,6,7,8,9,10,11,12 . Có bao nhiêu quan hệ tương đương trên A gồm 3 lớp
tương đương mà mỗi lớp có 4 phần tử.
Câu 4. Đề thi 2003.
a) Có bao nhiêu cặp tập hợp con A,B của một tập hợp 8 phần tử sao cho A B =
b) Có bao nhiêu cặp tập hợp con A,B của một tập hợp 8 phần tử sao cho :
AB A+ B.
Câu 5.Đề thi 2008
Ta lấy ngẫu nhiên 5 bìa từ một hộp chứa 60 tấm bìa trên đó lần lượt ghi các số 10, 11, …, 69.
a) Có bao nhiêu trường hợp có thể xảy ra.
b) Có bao nhiêu trường hợp trong đó 5 bìa lấy ra chứa đúng “hai đôi” (mỗi đôi gồm hai bìa
có chữ số cuối giống nhau. Chữ số cuối của hai đôi này là hai chữ số khác nhau và khác
với chữ số cuối của bìa còn lại)
c) Có bao nhiêu trường hợp trong đó chữ số cuối của 5 bìa tạo thành một dãy tăng?
d) Có bao nhiêu trường hợp chữ số cuối của 5 bìa tạo thành một dãy tăng và có ít nhất hai bìa
có chữ số đầu khác nhau.
Câu 6. Đề thi 2009.
Ta lấy ngẫu nhiên 5 bìa từ một hộp chứa 50 tấm bìa trên
đó lần lượt ghi các số 10, 11, …, 59.
a) Có bao nhiêu trường hợp có thể xảy ra.
1
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
b) Có bao nhiêu trường hợp trong đó có đúng hai trong năm bìa lấy ra có chữ số cuối bằng nhau.
Câu 7. Mỗi người sử dụng một hệ thống máy tính của một công ty X phải sử dụng một
password dài từ 6 đến 8 ký tự, trong đó mỗi ký tự là một chữ cái (trong 26 chữ cái) hoặc là
một chữ số (trong 10 chữ số). Mỗi password phải có ít nhất một chữ số. Hỏi có thể lập
được bao nhiêu password khác nhau?
Câu 8. Trong suốt một tháng gồm 30 ngày, một đội bóng phải chơi ít nhất mỗi ngày một trận,
nhưng trong tháng đó không được chơi nhiều hơn 45 trận. Hãy chứng minh rằng có một
giai đoạn gồm một số ngảy liên tiếp mà trong giai đoạn đó đội phải chơi đúng 14 trận.
Câu 9.
Xét 3 chuỗi ký tự trên tập mẫu tự {a, b, c} ( với a < b < c) : s1 = ac, s2 = aacb, s3 = aba.
a) Hãy sắp xếp chúng theo thứ tự tăng đối với thứ tự từ điển.
b) Cho biết giữa s1 và s3 có bao nhiêu chuỗi ký tự có chiều dài 6.
Câu 10 .
a) Tìm nghiệm tổng quát của hệ thức đệ qui sau
an = 6an – 1 – 9an – 2 + (18n – 6 ) 3n – 1
b) Tìm số các chuỗi nhị phân chiều dài n chứa chuỗi con 00.
Câu 11. (KHTN2010)
a)Tìm nghiệm tổng quát của hệ thức đệ qui:
an = an-1 + 6an-2
b)Tìm nghiệm thỏa điều kiện đầu a0 = 8, a1 = 5 của hệ thức đệ qui:
an = an-1 + 6an-2 + 10n(-2)n - 3(-2)n-1
Câu 12.Đề thi năm 2005
Một người gửi 100 triệu đồng vào một quĩ đầu tư vào ngày đầu của một năm. Ngày cuối
cùng của năm người đó được hưởng hai khoản tiền lãi. Khoản thứ nhất là 20% tổng số tiền
có trong tài khoản cả năm, khoản lãi thứ hai là 45% của tổng số tiền có trong tài khoản của
năm trước đó. Gọi Pn là số tiền có trong tài khoản vào cuối năm thứ n.
a. Tìm công thức truy hồi cho Pn
b. Tìm biểu thức của Pn theo n
Câu 13.Đề thi 2004
Một bãi giữ xe được chia thành n lô cạnh nhau theo hàng ngang để xếp xe đạp và xe máy.
Mỗi xe đạp chiếm 1 lô còn mỗi xe máy chiếm 2 lô. Gọi Ln là số cách xếp cho đầy n lô.
a. Tìm công thức đệ qui thỏa bởi Ln
b. Tìm biểu thức của Ln theo n
Câu 14. Tìm hệ thức đệ qui cho xn, trong đó xn là số miền của mặt phẳng bị phân chia bởi n
đường thẳng trong đó không có 2 đường nào song song và không có ba đường nào đồng qui. Tìm
xn .
Câu 15. Cho hàm Bool của 4 biến
f ( x, y, z, t ) x t ( z y) x z ( y t ) y (t z)
a) Tìm các tế bào lớn của Kar( f ).
2
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
b) Tìm tất cả các công thức đa thức tối tiểu của f.
Câu 16.
Cho đồ thị G = (V, E) , V = { v1, v2, v3, v4, v5, v6 , v7 ,v8,v9,v10} có ma trận khoảng cách là
0 1 10 6 3
1 0 4 10
4 0 5 1 2
5 0 2 8 5
10 10 1 0 4 1 4
D=
2 2 4 0 5
8 1 5 0 3 6 3
6 4 3 0 2
3 6 2 0 8
5 3 8 0
Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ v1 đến các đỉnh v2, v3, v4,v5, v6,v7 ,v8
,v9,v10.
Câu 17.(KHTN2010) Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z và
chiều dài của nó trong đồ thị vô hướng có trọng lượng sau:
Câu 18.
Có bao nhiêu hàm Bool của 5 biến mà dạng nối rời chính tắc của nó gồm 6 từ tối tiểu?
Câu 19.
Một đơn đồ thị vô hướng G gọi là tự bù nếu G G . Chứng minh rằng nếu G tự bù thì số đỉnh
của G là 4k hay 4k+1 với k nguyên dương.
Câu 20.
a) Vẽ cây nhị phân có được bằng cách chèn lần lượt các khóa K1,K2,…,K14 sao cho khóa ở
mỗi nút lớn hơn khóa của các nút thuộc cây con bên trái và bé hơn khóa của các các nút thuộc
cây con bên phải.Thứ tự của các khóa như sau:
3
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
Câu 26.
a) Một dãy số thực {xn} được nói là thuộc O(n) nếu tồn tại số thực dương C và số tự nhiên
m sao cho xn < C n mỗi khi n m. Hãy sử dụng mệnh đề lượng từ hóa để viết lại định
nghĩa trên.
b) Viết ra mệnh đề lượng từ hóa cho một dãy số thực không thuộc O(n).
Câu 27.
Cho G là đơn đồ thị vô hướng có n đỉnh và bậc của mỗi đỉnh không nhỏ hơn n/2. Chứng
minh rằng :
a) G liên thông.
b) Nếu bỏ đi một đỉnh tùy ý của G thì đồ thị thu được vẫn còn liên thông.
Câu 28.
CMR nếu bỏ đi một cạnh tùy ý của đồ thị vô hướng G thì số thành phần liên thông tăng lên
không quá 1.
Câu 29.
Cho G là đồ thị có n đỉnh và m cạnh. Chứng minh rằng G có không ít hơn n – m thành phần
liên thông.
5
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
LỜI GIẢI TÓM TẮT , ĐÁP SỐ
Câu 1.
t u (1)
r (s t) (2)
( p q ) r (3)
(s u ) (4)
______________
p
s u( Do tiền đề (4) và luật đối ngẫu ) (5)
u (Do (5) và luật đơn giản nối liền) (6)
t ( Do (1),(6) và luật phủ định) (7)
s (Do (5) và luật đơn giản nối liền) (8)
t s ( Do (7), (8) và phép tóan nối liền) (9)
(t s) ( Do (9) và luật đối ngẫu) (10)
r (Do (2), (10) và luật phủ định) (11)
( p q) (Do (3), (11) và luật phủ định) ( 12)
p q ( Do (12) và luật đối ngẫu) (13)
p (Do (13) và luật đơn giản nối liền)
Câu 2
1) x R(P( x) Q( x) R( x)) (Tiền đề)
2) P(a) Q(a) R(a) (Qui tắc đặc biệt phổ dụng với a bất kỳ)
3) P(a) Q(a) R(a) (Luật kéo theo)
4) Q(a) P(a) R(a) (Luật kéo theo)
5) x R( P( x) Q( x) (Tiền đề)
6) P(a) Q(a) (Qui tắc đặc biệt hóa phổ dụng với a bất kỳ)
7) P(a) Q(a) (Luật kéo theo)
8) P(a) P(a) R(a) (Từ 4 và 7, Tam đọan luận)
9) P(a) P(a) R(a) (Luật kéo theo)
10) P ( a ) R( a ) (Luật lũy đẳng)
11) R(a) P(a) (Luật kéo theo)
12) x R(R( x) P( x)) (Qui tắc tổng quát hóa phổ dụng)
Câu 3.
C12 .C84 .1
4
= 5775
3!
6
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
Câu 4
a) 3281 b) 29615.
Câu 5
a) 5461512. b) 486000. c) 1959552. d) 1958040
Câu 6
a) 2118760. b) 1050000
Câu 7.
(366 – 266) + (367 – 267 ) + (368 – 268) = 2684483063360.
Câu 8.
Đặt aj là số trận mà đội bóng chơi cho đến hết ngày thứ j trong tháng. Ta có a1, a2, …, an là một
dãy tăng gồm các số nguyên dương khác nhau từng đôi và aj ≤ 45. Hơn nữa, a1+14 , a2 + 14, …,
a30 + 14 cũng là một dãy số tăng gồm các số nguyên dương khác nhau với 15 ≤ aj +14 ≤59.
Ta thấy rằng 60 số nguyên dương a1, a2, …, a30, a1 +14, a2 +14, …, a30 + 14 đều nhỏ hơn hoặc
bằng 59. Áp dụng nguyên lý Dirichlet ta thấy có ít nhất hai trong 60 số nguyên dương nói trên
phải bằng nhau. Như thế phải có ít nhất hai chỉ số i và j sao cho ai = aj +14. Do đó đúng 14 trận
được đội bóng chơi từ ngày thứ j + 1 đến ngày thứ i.
Câu 9.
a) s2 < s3 < s1
b) s3 = aba < ab * * * * < s1 = ac
Mỗi vị trí * có 3 cách chọn. Do đó có 3* 3 *3 *3 = 81 chuỗi.
Câu 10.
a) an = ( A + n B) 3 n + (n – 2) n 2 3 n
b) Tìm số các chuỗi nhị phân chiều dài n chứa chuỗi con 00.
Gọi an là số chuỗi nhị phân chứa chuỗi con 00.
Ta có a0 = 0, a1 = 0.
Ta tính an:
- TH1 : Nếu bit đầu tiên là bit 1 thì có a n – 1 cách chọn n – 1 bit còn lại.
- TH2 : Nếu bit đầu tiên là bit 0 thì có hai TH xảy ra:
Bit thứ 2 là bit 1 : có a n – 2 cách chọn n – 2 bit còn lại
Bit thứ 2 là bit 0 : có 2n – 2 cách chọn n – 2 bit còn lại ( các bit này chọn 0 hay 1
đều được)
Vậy an = an – 1 + an – 2 + 2n – 2 ( n 2) (1)
Hệ thức đệ qui TTTN : an = an – 1 + an – 2 (2)
PTĐT : x2 – x – 1 = 0 có 2 nghiệm đơn là
7
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
b. Giải hệ thức đệ qui tuyến tính thuần nhất với P0 =100, P1 = 120 ta được
n n
250 3 50 3
Pn =
3 2 3 10
Câu 13.
a. Gọi Ln là số cách xếp số xe máy, xe đạp cho đầy n lô
- số cách xếp cho đầy n lô với vị trí đầu tiên là xe đạp là Ln-1
- số cách xếp cho đầy n lô với vị trí đầu tiên là xe máy là Ln-2
Vậy:
Ln = Ln-1 + Ln-2
b. Giải hệ thức đệ qui với điều kiện đầu:
L0 = 1, L1 = 1 ta được
n 1 n 1
1 1 5 1 1 5
Ln
5 2 5 2
Câu 14.
Giả sử n-1đường thẳng chia mặt phẳng thành xn-1 thỏa mãn điều kiện
Đường thẳng thứ n cắt n-1 đường thẳng cho trước tại n-1 giao điểm .
Trong đó:
- có n-2 đọan thẳng hữu hạn
- có 2 đọan có một đầu vô hạn
Mỗi đọan thẳng này phân miền mặt phẳng nó đi qua thành 2 miền
Do vậy sẽ tăng thêm n miền.
Vậy:
xn = xn-1 + n
Giải hệ thức đệ qui tuyến tính không thuần nhất với điều kiện đầu x0 = 1, x1 = 2 ta được
n(n 1)
xn 1
2
Câu 15.
a) Các tế bào lớn:
y t , z y , x zt ,, x yt , x y z , x z t
b) ĐS : Có ba công thức đa thức tối tiểu là
y t y z x zt x y z ,
y t y z x yt x y z ,
y t y z x yt x z t
Câu 16.
10
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-)
- (1,v1)* ( ,-) ( ,-) (10, v1) ( ,-) ( ,-) (6,v1) (3,v1) ( ,-)
- -
(5, v2) ( ,-) (10, v1) ( ,-) ( ,-) (6,v1) (3,v1)* ( ,-)
- - (5, v2)* ( ,-) (10, v1) ( ,-) (9,v9) (5,v9) - (11,v9)
- - - (10, v3) (6,v3) (7,v3) (9,v9) (5,v9)* - (11,v9)
- - - (10, v3) (6,v3)* (7,v3) (9,v9) - - (11,v9)
-
- - - (10, v3) (7,v3)* (7,v5) - - (11,v9)
- - - (9,v6) - - (7,v5)* - - (11,v9)
- - - (9,v6)* - - - - - (10, v7)
- - - - - - - - - (10, v7)*
11
- TS. NGUYỄN VIẾT ĐÔNG BÀI TẬP TOÁN RỜI RẠC
August 1, 2010
Câu 20.
K4< K5
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
