Bài giảng Toán rời rạc - Bài tập phép đếm

1Trường đại học Cần Thơ
Khoa Công nghệ thông tin và truyền thông
Bộ môn Khoa học máy tính
BÀI TẬP PHÉP ĐẾM
2Bài tập 1
 Có bao nhiêu cách chia 10 cuốn sách cho 3 sinh
viên sao cho Lan nhận 5 cuốn, Cúc nhận 3 cuốn và
Trúc nhận 2 cuốn sách.
3Bài tập 1
 Số cách chia là:
!2!3!5
!10
4Bài tập 2
 Trong thư viện có 3 loại sách máy tính, vật lý, lịch
sử. Giả sử thư viện có ít nhất 6 cuốn cho mỗi loại.
Tính số cách chọn 6 cuốn sách.
5Bài tập 2
 Số cách chọn 6 cuốn sách không phân biệt thứ tự,
cho phép lặp lại từ 3 loại sách trong thư viện là:
C(6 + 3 -1, 3 – 1) = C(8, 2) = 28.
6Bài tập 3
 Hỏi có bao nhiêu dãy nhị phân có chiều dài 10 bit mà
mỗi dãy hoặc bắt đầu bằng 2 chữ số giống nhau
hoặc kết thúc bằng 2 chữ số giống nhau.
7Bài tập 3
 Số dãy nhị phân có chiều dài 10 bit: 210 = 1024
 Số dãy nhị phân có chiều dài 10 bit bắt đầu bằng 2
chữ số khác nhau và kết thúc cũng bằng 2 chữ số
khác nhau: 4.26 = 256
 Số dãy nhị phân có chiều dài 10 bit mà mỗi dãy hoặc
bắt đầu bằng 2 chữ số giống nhau hoặc kết thúc
bằng 2 chữ số giống nhau: 1024 – 256 = 768
8Bài tập 4
 Một con kiến bò theo các cạnh từ điểm M đến điểm
N, theo chiều từ trái sang phải và đi lên hoặc đi
xuống, trên một cái lưới như hình vẽ. Hỏi có bao
nhiêu cách bò?
M
N
9Bài tập 4
 Mỗi hành trình mô tả bởi 1 chuỗi có độ dài 2n (n = 5)
 Mỗi chuỗi nhận được bằng cách chọn n (n = 5) vị trí
đối với đi lên (không quan tâm đến thứ tự) còn lại n
(n = 5) vị trí đi xuống.
 Tổng đường đi: C(2n, n) = C(10, 5) =
!5!5
!10
10
Bài tập 5
 Xét chuỗi MISSISSIPPI. Có bao nhiêu chuỗi khác
nhau khi sắp xếp lại các ký tự của chuỗi này?
11
Bài tập 5
 Chiều dài chuỗi là 11,
có C(11, 2) cách chọn vị trí ký tự P,
có C(9, 4) cách chọn vị trí ký tự S sau khi đã chọn P,
có C(5, 4) cách chọn vị trí ký tự I sau khi đã chọn P, S,
cuối cùng chỉ còn lại vị trí ký tự M sau khi đã chọn P, S, I
=> Tổng các chuỗi khác nhau: C(11,2) C(9,4) C(5,4) =
12
Bài tập 6
 Trong một hội thảo có n người, thảo luận về m chủ đề
(với n > m), mỗi người tham dự vào ít nhất một chủ đề và
có thể tham dự vào một vài chủ đề. Chứng minh rằng có
hai người có số chủ đề tham dự bằng nhau.
13
Bài tập 6
 Gọi ni là số chủ đề mà người thứ i tham dự : 1  ni  m
n số ni nhận m giá trị (n > m)
theo nguyên lý Dirichlet
=> phải có ít nhất 2 số ni nào đó có cùng giá trị.
14
Bài tập 7
 CM rằng trong 37 số nguyên bất kỳ, có thể chọn ra được
7 số mà tổng chia hết cho 7.
15
Bài tập 7
 Số hộp = 7 (số dư của phép chia cho 7)
Số vật = 37
Sắp số vào hộp “số dư của phép chia số đó cho 7”
Nếu không có hộp nào rỗng => 7 số được chọn từ mỗi
hộp một số có tổng chia hết cho 7
Nếu có hộp rỗng, 37 số được sắp vào 6 hộp
Nguyên lý Dirichlet => có hộp chứa  37/6  = 7 số, tổng
của 7 số lấy trong hộp này chia hết cho 7
16
Bài tập 8
 CM rằng trong 100 số nguyên bất kỳ có thể chọn ra được
hai số hiệu của chúng chia hết cho 57.
17
Bài tập 8
 Số hộp = 57 (số dư của phép chia cho 57)
Số vật = 100
Sắp số vào hộp “số dư của phép chia số đó cho 57”
Nguyên lý Dirichlet => có hộp chứa  100/57 = 2 số,
=> 2 số đồng dư trong phép chia cho 57
=> hiệu của 2 số này chia hết cho 57