Ktl-icon-tai-lieu

Toán rời rạc

Được đăng lên bởi nguyenthithuhahd95
Số trang: 8 trang   |   Lượt xem: 584 lần   |   Lượt tải: 0 lần
ĐỀ THI MÔN TOÁN RỜI RẠC
ĐỀ 46

Câu 1: 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)
2)

Không có bức thư nào đúng địa chỉ
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ỉ
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)

1

Câu 2: 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à: C 49 = 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

¿
118
¿
¿ =8
15

Vậy sẽ có ít nhất 8 tập con có tổng các chữ số bằng nhau.

2

Câu 3: Cho 9 mặt phẳng trong không gian 3 chiều, h ỏi chúng chia không gian
thành bao nhiêu phần trong các trường hợp sau đây:
1)
2)

Tất cả các bộ 3 mặt phẳng đều cắt nhau tại 1 điểm và không có m ột
bộ 4 mặt phẳng nào cắt nhau tại 1 điểm.
Nếu vẽ thêm 1 mặt phẳng đi qua 3 giao điểm của các m ặt phẳng đã
cho.
Trả lời:

Giả sử có...
Đ THI MÔN TOÁN R I R C
Đ 46
Câu 1: B ng u nhiên 6 b c th vào 6 phong bì đ s n đ a ch . H i 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) 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 ư
G i D
n
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ó: D
1
= 0
D
2
= 1
D
3
= 2 = (3 – 1).(1 + 0)
D
4
= 9 = (4 – 1).(2 + 1)
……
D
n
= (n – 1).( D
n-1
+ D
n-2
)
V y ta có công th c truy h i: D
n
= (n – 1).( D
n-1
+ D
n-2
)
1) S cách đ b 6 b c th không có b c th nào đúng đ a ch : ư ư
D
6
= (6 – 1).(D
5
+ D
4
) = 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 : ư ư
C
3
6
. D
3
= C
3
6
. 2 = 40 (cách)
1
Toán rời rạc - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Toán rời rạc - Người đăng: nguyenthithuhahd95
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
8 Vietnamese
Toán rời rạc 9 10 778