Bai Tap 5 [PDF]

Zitiervorschau

1. Chươn

g 5. Đếm các phần tử

1. Một phiếu trắc nghiệm đa lựa chọn gồm 10 câu hỏi. Mỗi câu hỏi có 4 phương án trả lời. a) Có bao nhiêu cách điền một phiếu trắc nghiệm nếu mọi câu hỏi đều được trả lời? b) Có bao nhiêu cách điền một phiếu trắc nghiệm nếu có thể bỏ trống? Giải a) Nếu mọi câu hỏi đều được trả lời thì mỗi câu hỏi có 4 khả năng trả lời. Do đó theo qui tắc nhân thì số cách điền một phiếu trắc nghiệm gồm 10 câu hỏi là 410. a) Nếu các câu hỏi có thể trả lời hoặc không thì mỗi câu hỏi có 5 khả năng trả lời. Do đó theo qui tắc nhân thì số cách điền một phiếu trắc nghiệm gồm 10 câu hỏi là 510. 2. Có bao nhiêu tên họ của người Anh có thể viết tắt bằng ba chữ cái khác nhau, trong đó chữ cái đầu tiên là chữ A? Giải Do chữ cái đầu là A nên chữ cái thứ hai có 25 cách chọn và chữ cái thứ ba có 24 cách chọn. Như vậy có tất cả 25.24 = 600 tên họ của người Anh có thể viết tắt bằng ba chữ cái khác nhau, trong đó chữ cái đầu tiên là chữ A. 3. Có bao nhiêu biển đăng ký xe nếu mỗi biển số gồm hai chữ tiếp sau là bốn chữ cái hoặc hai chữ cái theo sau là bốn chữ số? Giải Trường hợp 1: mỗi biển số xe có hai chữ tiếp sau là 4 chữ cái. Có tất cả 266 biển số. Trường hợp 2: mỗi biển số xe có hai chữ tiếp sau là 4 chữ số. Có tất cả 262.104 biển số. Vậy có tất cả 10^2.266 + 262.104 biển số. 4. Có bao nhiêu biển đăng ký xe mỗi biển số gồm hai hoặc ba chữ cái tiếp sau bởi hai hoặc ba chữ số? Giải 1

Trường hợp 1: mỗi biển số xe có hai chữ tiếp sau là 2 chữ số. Có tất cả 262.102 biển số. Trường hợp 2: mỗi biển số xe có hai chữ tiếp sau là 3 chữ số. Có tất cả 262.103 biển số. Trường hợp 3: mỗi biển số xe có ba chữ tiếp sau là 2 chữ số. Có tất cả 263.102 biển số. Trường hợp 4: mỗi biển số xe có ba chữ tiếp sau là 3 chữ số. Có tất cả 263.103 biển số. Vậy có tất cả 262.102(1 + 10 + 26 + 26.10) = 29700.262 biển số. 5. Xâu thuận nghịch độc là một xâu mà khi viết theo thứ tự ngược lại cũng thành chính nó. Hãy tính số xâu nhị phân có độ dài bằng n là thuận nghịch độc. Giải Nếu n chẵn thì để có xâu thuận nghịch độc ta chọn tùy ý một xâu nhị phân có độ dài n/2. Sau đó viết tiếp xâu theo thứ tự ngược lại vào xâu ban đầu. Do đó tất cả có thể có 2n/2 xâu nhị phân có độ dài bằng n là thuận nghịch độc. Nếu n lẻ thì tại vị trí (n+1)/2 có thể đặt tùy ý 0 hoặc 1, còn lại tạo xâu tương tự trường hợp trên với độ dài n-1. Do đó có thể có 2. 2(n-1)/2 = 2 (n+1)/2 xâu nhị phân có độ dài bằng n là thuận nghịch độc. 6. Cô dâu và chú rể mời 4 người bạn đứng thành một hàng để chụp ảnh cùng với mình. Hỏi có bao nhiêu cách sắp hàng nếu cô dâu không đứng cạnh chú rể? Giải Có tất cả 6 người đứng để chụp ảnh. Số cách để cô dâu đứng cạnh chú rể là 2.5.4! = 240. Số cách sắp hàng để cô dâu không đứng cạnh chú rể là 6! - 240 = 720 - 240 = 480 7. Có bao nhiêu xâu nhị phân có độ dài bằng 8 và có ba số 0 liền nhau hoặc bốn số 1 liền nhau? (163) Giải Gọi an là số các xâu nhị phân có độ dài bằng n và có ba số 0 liền nhau. Có a1 = 0; a2 = 0; a3 = 1. Với n > 3 có an = an-1 + an-2 + an-3 + 2n-3. Do đó a4 = 3; a5 = 8; a6 = 20; a7 = 47; a8 = 107. Như vậy có 107 xâu nhị phân độ dài bằng 8 và có ba số 0 liền nhau. Gọi an là số các xâu nhị phân có độ dài bằng n và có bốn số 1 liền nhau. Có a1 = 0; a2 = 0; a3 = 0; a4 = 2

1. Với n > 4 có an = an-1 + an-2 + an-3 + an-4 + 2n-4. Do đó a5 = 3; a6 = 8; a7 = 20; a8 = 48. Như vậy có 64 xâu nhị phân độ dài bằng 8 và có bốn số 1 liền nhau. Số các xâu độ dài 8 có 3 số 0 liền nhau và 4 số 1 liền nhau là 2x4 = 8. Số cách chọn các xâu nhị phân độ dài 8 có ba số 0 liền nhau hoặc bốn số 1 liền nhau là 107 + 48 - 8 = 147. 8. Có bao nhiêu số nguyên dương không lớn hơn 100 chia hết cho 4 hoặc cho 6? Giải Trong các số nguyên dương ≤ 100 có tất cả [100/4] = 25 số chia hết cho 4, [100/6] = 16 số chia hết cho 6 và [100/12] = 8 số chia hết cho cả 4 và 6. Theo nguyên lý bù trừ có tất cả 25 + 16 - 8 = 33 số chia hết cho 4 hoặc 6. 9. Giả sử rằng trong tương lai mọi máy điện thoại trên thế giới được gán một con số (số điện thoại) gồm mã quốc gia dài từ 1 tới 3 chữ số, tức là nó có dạng X, XX, hoặc XXX; tiếp theo là số điện thoại 10 chữ số dạng NXX-NXX-XXXX, trong đó N có thể nhận giá trị từ 2 đến 9, X biểu thị một chữ số từ 0 đến 9. Theo cách đánh số này, sẽ có bao nhiêu số điện thoại khác nhau có thể dùng được trên toàn cầu? Giải Số các số điện thoại 10 chữ số dạng NXX-NXX-XXXX là 64.108. Trường hợp 1: mã quốc gia là 1 chữ số. Có tất cả 10 khả năng. Trường hợp 2: mã quốc gia là 2 chữ số. Có tất cả 102 khả năng. Trường hợp 3: mã quốc gia là 3 chữ số. Có tất cả 103 khả năng. Vậy có tất cả 64.108(10 + 102 + 103) = 7.104.000.000 số điện thoại. 3

10. Dùng biểu đồ cây tìm số xâu nhị phân độ dài 4 không có 3 số 0 liền nhau. Giải Có tất cả 6 + 7 = 13 xâu nhị phân độ dài 4 không có 3 số 0 liền nhau. 11. Có bao nhiêu cách sắp xếp các chữ a,b,c và d sao cho chữ b không đi liền sau chữ a? Giải Số các cách sắp xếp 4 chữ cái a, b, c, d là 4! = 24. Số các cách sắp xếp 4 chữ cái a, b, c, d sao cho b đi liền sau a là 3*2! = 6. Do đó số các cách sắp xếp các chữ a,b,c và d sao cho chữ b không đi liền sau chữ a là 24 - 6 = 18. 12. Dùng biểu đồ cây hãy xác định số các tập con của tập {3,7,9,11,24} sao cho tổng giá trị các phần tử của tập con nhỏ hơn 28? Giải - Tập con không phần tử : 1 thỏa mãn tổng các phần tử ≤ 28 - Tập con 1 phần tử: 5 thỏa mãn tổng các phần tử ≤ 28 - Tập con 2 phần tử: 4 + 2 + 1 = 7 thỏa mãn tổng các phần tử ≤ 28 - Tập con 3 phần tử: 4 thỏa mãn tổng các phần tử ≤ 28 - Tập con ≥ 4 phần tử: 0 thỏa mãn tổng các phần tử ≤ 28 Theo qui tắc cộng có tất cả 17 tập con thỏa mãn tổng các phần tử ≤ 28 13. Dùng quy tắc nhân hãy chứng tỏ rằng có 22n bảng chân lý khác nhau đối với các mệnh đề được lập từ n biến. Giải Từ n biến có thể lập được 2n biểu thức mệnh đề. Với một mệnh đề n biến, mỗi biến nhận một trong 2 giá trị đúng hoặc sai nên có tất cả 22n bảng chân lý khác nhau. 4

14. Cho n là một số nguyên dương. Chứng tỏ rằng trong mọi tập n số nguyên liên tiếp có đúng một số chia hết cho n. Giải Khi chia một số nguyên x cho n ta được một số dư trong các số từ 0 đến n-1. Do n số nguyên liên tiếp x, x+1, …, x+n-1 khi chia cho n có các số dư khác nhau nên có đúng 1 số chia cho n dư 0, tức là chia hết cho n. 15. Trong một trường đại học có 38 ca học phân cho các lớp. Nếu có 677 lớp khác nhau thì cần có ít nhất bao nhiêu phòng học? (18). Giải Số phòng học cần là x ≥ [677/38] + 1 = 18. Do đó số phòng học cần ít nhất là 18. 16. Một mạng máy tính gồm có 6 máy. Mỗi máy nối trực tiếp hoặc không nối với các máy khác. Chỉ ra rằng có ít nhất hai máy mà số máy khác nối với chúng là bằng nhau. Giải Một máy có thể nối trực tiếp từ 0 đến 5 máy. Nếu có một máy có nối đến 5 máy thì không có máy nào được nối với 0 mày. Do đó số các máy nối đến một máy nhận 1 trong 5 giá trị. Có 6 máy nên phải có 2 máy có giá trị như nhau, tức là có ít nhất hai máy mà số máy khác nối với chúng là bằng nhau. 17. Một tập hợp 100 phần tử có bao nhiêu tập con có nhiều hơn hai phần tử? Giải Số tập con có nhiều hơn hai phần tử của tập hợp gồm 100 phần tử bằng số tất cả các tập con trừ đi số lượng các tập con 0 phần tử và 1 phần tử. Số các tập con 0 phần tử là 1. Số các tập con 1 phần tử là C(100, 1) = 100. 5

Số lượng các tập con có số phần tử ≥ 2 phần tử là 2100 -101 - 4950 = 2100 - 5051. 18. Giả sử một tổ bộ môn có 10 nam và 15 nữ. Có bao nhiêu cách chọn một hội đồng gồm 6 ủy viên trong đó số ủy viên nam bằng số ủy viên nữ? Giải Trong hội đồng gồm 6 ủy viên với số ủy viên nam bằng số ủy viên nữ có 3 nam và 3 nữ. Số cách chọn 3 ủy viên nữ là C(15, 3) = 455. Số cách chọn 3 ủy viên nữ là C(10,3) = 120. Tổng số cách chọn hội đồng là C(10,3).C(15,3) = 120.455 = 54.600. 19. Từ tập các số nguyên dương không vượt quá 100, có thể tạo được bao nhiêu chỉnh hợp chập 4 chứa 3 số nguyên liên tiếp a) Theo trật tự thông thường và có thể bị phân cách bởi các số khác của chỉnh hợp. b) Tại những vị trí liên tiếp của chỉnh hợp? Giải a) Trước hết chọn các bộ 3 số nguyên liên tiếp: có tất cả 98 bộ. Tiếp theo chọn số nguyên thứ tư khác các số trong bộ 3 đã chọn: có 97 khả năng. Số nguyên thứ tư có thể đứng tại một vị trí bất kỳ trong 4 vị trí. Như vậy có tất cả 98.97.4 = 37.624 chỉnh hợp. Trong số các chỉnh hợp trên đã tính thừa các bộ chứa 4 số nguyên liên tiếp: số lượng là 96. Vậy có tất cả 37.528 chỉnh hợp thỏa mãn. b) Chọn các bộ 3 số nguyên liên tiếp: có tất cả 98 bộ. Tiếp theo chọn số nguyên thứ tư khác các số trong bộ 3 đã chọn: có 97 khả năng. Như vậy có 98.97.2 = 18.812. Đã tính thừa các bộ chứa 4 số nguyên liên tiếp là 96. Vậy có tất cả 18.716 chỉnh hợp thỏa mãn. 6

20. Có bao nhiêu xâu nhị phân độ dài 10 chứa ít nhất 3 số 0 và ít nhất ba số 1? (912) Giải - Xâu nhị phân độ dài 10 chứa 3 số 0: C(10, 3) = 120 - Xâu nhị phân độ dài 10 chứa 4 số 0: C(10, 4) = 210 - Xâu nhị phân độ dài 10 chứa 5 số 0: C(10, 5) = 252 - Xâu nhị phân độ dài 10 chứa 6 số 0: C(10, 6) = 210 - Xâu nhị phân độ dài 10 chứa 7 số 0: C(10, 7) = 120 Vậy tổng cộng có 912 xâu nhị phân độ dài 10 chứa ít nhất 3 số 0 và ít nhất ba số 1. 21. Giả sử S là một tập cho trước. Chứng minh rằng số các tập con của S có số phần tử là lẻ cũng bằng số các tập con có số phần tử là chẵn. Giải - Số các tập con của S có số phần tử là lẻ bằng L = C(n,1) + C(n, 3) + … - Số các tập con của S có số phần tử là chẵn bằng C = C(n,0) + C(n, 2) + … Suy từ tính chất của các hệ số trong khai triển nhi thức Niuton: L = C. 22. Phương trình x1 + x2 + x3 + x4 =17 có bao nhiêu nghiệm nguyên không âm? Giải Mỗi nghiệm của phương trình tương ứng với một cách chọn 17 phần tử từ một tập có 3 loại, sao cho có x1 phần tử loại 1, x2 phần tử loại 2, x3 phần tử loại 3 và x4 phần tử loại 4 được chọn. Vì vậy số nghiệm bằng số tổ hợp lặp chập 17 từ tập có 4 phần tử. Số đó bằng: C(4+17 -1,17) = (20.19.18)/(1.2.3) = 1140. 23. Có bao nhiêu số nguyên dương nhỏ hơn 1 000 000 có tổng các chữ số của nó bằng 19? (30492) Giải Gọi số các số nguyên dương có k chữ số và tổng các chữ số bằng n là f(k, n). Khi đó có: 7

f(k,n) = f(k-1, n) + f(k-1, n-1) + … + f(k-1,n-i) với k > 1, i ≤ 9 sao cho n-i ≥ 0. Số lượng các số thỏa mãn điều kiện bài ra là f(6, 19) tương ứng k = 6 và n = 19. Các giá trị f(1, n), 1 ≤ n ≤ 19 được tính trực tiếp. Quá trình tính toán cho trong bảng sau đây:

1 2 3 4 5 6

1 1 1 1 1 1 1

2 1 2 3 4 5 6

3 1 3 6 10 15 21

4 1 4 10 20 35 56

5 1 5 15 35 70 126

6 1 6 21 56 126 252

7 1 7 28 84 210 462

8 1 8 36 120 330 792

9 1 9 45 165 495 1287

10 0 9 54 219 714 2001

11 0 8 61 279 992 2992

12 0 7 66 342 1330 4317

13 0 6 69 405 1725 6027

14 0 5 70 465 2170 8162

15 0 4 69 519 2654 10746

16 0 3 66 564 3162 13782

17 0 2 61 597 367 172

Như vậy, tất cả các số < 1.000.000 có tổng các chữ số 19 sẽ là 25212 số.

24. Có bao nhiêu cách sắp xếp n cuốn sách lên k giá sách khác nhau nếu: a) Các cuốn sách là các bản chụp của cùng một đầu sách. b) Không có hai cuốn cùng đầu sách, và có kể tới vị trí của các cuốn sách trên giá. Giải a) Số cách sắp xếp n cuốn sách là các bản chụp của cùng một đầu sách lên k giá sách bằng số nghiệm nguyên không âm của phương trình x1 + … + xk = n. Do đó số cách sắp xếp bằng tổ hợp chập k có lặp của n phần tử là C(k + n - 1, n) = (k+n-1)!/(n!(k-1)!). 8

b) Trong trường hợp không có hai cuốn cùng đầu sách, và có kể tới vị trí của các cuốn sách trên giá thì số cách sắp xếp là: ∑x1!... xk !

x1 +... +xk =n

25. Tìm hoán vị liền sau theo thứ tự từ điển của mỗi hoán vị sau đây: 1432, 54123, 6714235, 31528764 Giải 1432 → 2134; 54123 → 54213; 6714235 → 6714253; 31528764 → 31542678

9