Tài liệu Bài tập và hướng dẫn giải chi tiết môn toán rời rạc

TOÁN RỜI RẠC Bài 2: ta có bảng chân trị sau: p ¬p q ¬q ¬p ^q ¬p ^ ¬p p ¬¿ ¬p T T T F F T F F Từ bảng chân trị trên  ¬ p F F F F T F T F T T T F ¬p ¬p ^( ^ q) = ^ ¬p F F F T v( ^ q)) F F F T Bài 3: Ta có bảng giá trị: p q pq 1 1 1 1 0 0 0 1 0 0 0 0 Ta thấy : VT=VP (đpcm). pvq 1 1 1 0 (p  q)( p v q) 1 1 1 1 T 1 1 1 1 Câu 4 Ta có bảng giá trị p q p→q q→p p↔q (p → q) ˄ (q → p) 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 1 1 Theo bảng giá trị ta thấy mệnh đề (p ↔ q) và mệnh đề (p → q) ˄ (q → p) có cùng các giá trị chân lý Vậy (p ↔ q) = (p → q) ˄ (q → p) Bài 6: Sử dụng bảng giá trị, chứng minh : (pr)(qr)=(pq)r Giải p q r pr qr pq 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 1 ( p  r )  ( q  ( p  q)  r) r 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 Vậy ( p  r )  ( q  r ) = ( p  q )  r Bài 7: Cho tập A={1,2,3,4,5,6,7,8,9}.Sử dụng thuật toán sinh hoán vị theo thứ tự từ điển,tìm 4 hoán vị liền kề tiếp theo của hoán vị 568397412. Bài làm: j=3 , k=7 => hoán vị tiếp theo 568421379 j=6 k=8 => hoán vị tiếp theo 568427913 j=8 k=9 => hoán vị tiếp theo 568427931 j=5 k=8 => hoán vị tiếp theo 568431297 Bài 8: A={1,2,3,4,5,6,7,8,9}. n=9; a[]=(458796321). Hoán vị 1: i=4; k=5 → a[]=(4587912367). Hoán vị 2: i=8; k=9 → a[]=(458912376). Hoán vị 3: i=7; k=9 → a[]=(458912637). Hoán vị 4: i=8; k=9 → a[]=(458912673). Vậy 4 hoán vị liền kề tiếp theo của hoán vị 45879321 là: 458912367 458912376 458912637 458912673 Bài 9: Cho tập A={1, 2, … , 9}. Sử dụng phương pháp sinh hội theo thứ tự từ điển, tìm 4 hoán vị liền kề tiếp theo của 236897541. Giải: *Phương pháp: Cho hoán vị ban đầu: a1a2...an. +Bước 1: Tìm từ phải qua trái của hoán vị ban đầu phần tử ak đầu tiên thỏa mãn akak. +Bước 3: Đổi chỗ ai và ak. +Bước 4: Đảo ngược thứ tự các phần tử từ ak+1 đến an. *Bài giải: Hoán vị đầu tiên: 236897541. +n=9. +k=4: ak=a4=8 < ak+1=a5=9. +i=5: ai=a5=9. +Đổi chỗ a4 và a5. Sau đó đảo ngược thứ tự từ a5 đến a9, ta được hoán vị kế tiếp: 236914578. Sinh hoán vị kế tiếp: +n=9. +k=8: a8=7 tổ hợp tiếp theo 3,5,7,9 i=3=> tổ hợp tiếp theo 3,5,8,9 i=2=> tổ hợp tiếp theo 3,6,7,8 i=4=> tổ hợp tiếp theo 3,6,7,9 Bài 13: Cho tập A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Sử dụng phương pháp sinh tổ hợp chập k của một tập hợp theo thứ tự từ điển, hãy tạo 4 tổ hợp chập 4 liền kề tiếp theo của tổ hợp 4,6,7,9. Giải Tổ hợp liền kề của tổ hợp chập 4 {4,6,7,9} của tập A phải là tổ hợp lớn hơn và tổ hợp {4,6,7,9}nhỏ nhất Do đó các tổ hợp tiếp theo là: {4,6,8,9} - Tổ hợp thứ 1 {4,7,8,9}- Tổ hợp thứ 2 {5,6,7,8}- Tổ hợp thứ 3 {5,6,7,9}- Tổ hợp thứ 4 Bài 14. Tập hợp A = {1,2,3,4,5,6,7,8,9} Cấu hình hiện tại : (1,5,6,8) n=4,k=4 → tổ hợp tiếp theo : 1,5,6,9 n=4,k=3 → tổ hợp tiếp theo : 1,5,7,8 n=4,k=4 → tổ hợp tiếp theo : 1,5,7,9 n=4,k=3 → tổ hợp tiếp theo : 1,5,8,9 Câu 15 TH1 2 thành phần đầu là các chữ cái in hoa 3 thành phấn sau là các chữ số từ 0 → 9 Ta có 262 cách chọn 2 chữ cái để đưa vào 2 thành phần đầu Có 103 cách chọn 3 chữ số để đưa vào 3 thành phần sau Theo quy tắc nhân ta có 262 103 . biển số thỏa mãn TH2 2 thành phần đầu là các chữ cái in hoa 4 thành phấn sau là các chữ số từ 0 → 9 Ta có Có 104 262 cách chọn 2 chữ cái để đưa vào 2 thành phần đầu cách chọn 4 chữ số để đưa vào 4 thành phần sau Theo quy tắc nhân ta có 262 104 . biển số thỏa mãn TH3 3 thành phần đầu là các chữ cái in hoa 3 thành phấn sau là các chữ số từ 0 → 9 Ta có Có 103 263 cách chọn 3 chữ cái để đưa vào 3 thành phần đầu cách chọn 3 chữ số để đưa vào 3 thành phần sau Theo quy tắc nhân ta có 263 103 . biển số thỏa mãn TH4 3 thành phần đầu là các chữ cái in hoa 4 thành phấn sau là các chữ số từ 0 → 9 Ta có 263 cách chọn 2 chữ cái để đưa vào 2 thành phần đầu Có 104 cách chọn 4 chữ số để đưa vào 4 thành phần sau Theo quy tắc nhân ta có 263 104 . biển số thỏa mãn Vậy theo quy tắc cộng, ta có số biển số xe thỏa mãn là 262 103 . + 262 104 . + 263 103 . + 263 104 . = 200 772 000 Bài 16: Số cách chọn chữ: 1. Số cách chọn 3 chữ cái in hoa đầu biển số : 263 2. Số cách chọn 4 chữ cái in hoa đầu biển số : 264 Số cách chọn số: 1. Số cách chọn 2 chữ số kết thúc biển số : 102 2. Số cách chọn 3 chữ số kết thúc biển số : 103  Số cách tạo biển số xe thỏa mãn là: (102+103)(263+264)= 522007200. Câu 17: Có bn so nguyên từ 1000 đến 5000 chia hết cho 6 hoặc 9: +[0;1000] ⋮ 6 : 166 số. +[0;5000] ⋮ 6 : 833 số. =>[1000;5000] ⋮ 6 :833-166=677 số. +[0;1000] ⋮ 9 : 111 số. +[0;5000] ⋮ 9 : 555 số. =>[1000;5000] ⋮ 9 :555-111=444 số. Những số chia hết cho 18 thì chia hết cho cả 6 và 9 Nên [1000;5000] có 5000:18-1000:18 = 222 số chia hết cả 6 và 9. Vậy [1000;5000] có 677+444-222 = 899 số chia hết cho 6 hoặc 9. Bài 18: Số các số chia hết cho 8 trong khoảng từ 5000 đến 9999 là : N 1= [ ][ ] 9999 5000 − =1249−625=624 (số) 8 8 Số các số chia hết cho 12 trong khoảng từ 5000 đến 9999 là : N 2= [ ][ ] 9999 5000 − =833−416=417 (số) 12 12 Ta có BCNN của 8 và 12 là 24. Số các số vừa chia hết cho 12 và 8 trong khoảng từ 5000 đến 9999 là : N 3= [ ][ ] 9999 5000 − =416−208=208 (số) 24 24 Số các số chia hết cho 12 hoặc 8 trong khoảng từ 5000 đến 9999 là : Theo nguyên tắc bù trừ : N 4 =N 1+ N 2−N 3=624 +417−208=833( số ) .Câu 19: +)Ta có:Chọn bắt đầu bằng mã quốc gia dài từ 1 đến 3 =>Có 10+100+1000=1110(cách) +)Tiếp theo là 10 chữ số dạng NXX-NXX-XXXX ,N có thể nhận giá trị từ 1 đến 6 =>Có 62(cách chọn N) +)X biểu thị một chữ số từ 0 đến 9 =>Có 108(cách chọn X) Vậy:Số số điện thoại có thể dùng là 1110.62.108=39960.108(số) Bài 20: Có 3 dạng số điện thoại: X – NNX – NXX - XXXX XX – NNX – NXX - XXXX XXX - NNX- NXX - XXXX *Dạng 1: Chọn 8 số X: Có 108 cách Chọn 3 số N: Có 53 cách ¿>¿ Lập được 108 x 53 số dạng 1 *Dạng 2: Chọn 8 số X: Có 109 cách Chọn 3 số N: Có 53 cách ¿>¿ Lập được 109 x 53 số dạng 2 *Dạng 3: Chọn 8 số X: Có 1010 cách Chọn 3 số N: Có 53 cách ¿>¿ Lập được 1010 x 53 số dạng 3 ¿>¿ Lập được 53 x (108 + 109 + 1010) số điện thoại thỏa mãn. Bài 21: Lớp học có 55 bạn nam và 35 bạn nữ. Hãy cho biết có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam bằng số bạn nữ, biết rằng đội văn nghệ cần ít nhất 6 thành viên và nhiều nhất 10 thành viên. Giải Ta có đội văn nghệ cần ít nhất là 6 nhiều nhất là 10 người và số nam phải bằng số nữ nên ta chỉ có thể chọn 3 nam-3 nữ hoặc 4 nam-4 nữ hoặc 5 nam-5 nữ Chọn ngẫu nhiên 3 bạn nam trong số 55 bạn: số cách chọn là 1 tổ hợp chập 3 của 55: C(55,3) Chọn ngẫu nhiên 3 bạn nữ trong số 35 bạn: số cách chọn là 1 tổ hợp chập 3 của 35: C(35,3) Chọn ngẫu nhiên 4 bạn nam trong số 55 bạn: số cách chọn là 1 tổ hợp chập 4 của 55: C(55,4) Chọn ngẫu nhiên 4 bạn nữ trong số 35 bạn: số cách chọn là 1 tổ hợp chập 4 của 35: C(35,4) Chọn ngẫu nhiên 5 bạn nam trong số 55 bạn: số cách chọn là 1 tổ hợp chập 5 của 55: C(55,5) Chọn ngẫu nhiên 5 bạn nữ trong số 35 bạn: số cách chọn là 1 tổ hợp chập 5 của 35: C(35,5) Số cách chọn đội văn nghệ là : C(55,3) x C(35,3) + C(55,4) x C(35,4) + C(55,5) x C(35,5) = 1.147 x 10^12 (cách) Câu 22: Lớp học có 60 bạn nam và 42 bạn nữ. Hãy cho biết có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam bằng số bạn nữ, biết rằng đội văn nghệ cần ít nhất 4 thành viên và nhiều nhất 8 thành viên. Bài giải Gọi số bạn nam trong đội văn nghệ là x1 , số bạn nữ là Vì số nam và nữ trong đội băng nhau nên ta có: x1 = x2 x2 . . Mà đội cần ít nhất 4 thành viên và nhiều nhất 8 thành viên nên: 4 ≤ x 1+ x2 ≤ 8↔ 4 ≤2 x 1 ≤ 8 ↔2 ≤ x1 ≤ 4 . Vậy x1 có thể nhận các giá trị 2,3,4 . Do x 1=x 2 nên x2 cũng có thể nhận các giá trị là 2,3,4. TH1: số nam= số nữ=2: 2 2 Số cách chọn đội văn nghệ là: C60 ×C 42 . TH2: số nam= số nữ =3: 3 3 Số cách chọn đội văn nghệ là: C60 ×C 42 . TH3: số nam = số nữ =4: 4 4 Số cách chọn đội văn nghệ là: C60 ×C 42 . Vậy số cách chọn đội văn nghệ thỏa mãn bài toán là: C260 ×C 242+C 360 × C342+C 460 ×C 442=54975355120 . Bài 23. Số người trong đội văn nghệ thóa măn yêu cầu bài toán là : 6,9,12 trong 3 trường hợp. TH 1. Đội văn nghệ có 6 người : Số cách chọn 4 bạn nam từ 50 nam và 2 bạn nữ từ 20 nữ tại thành đội văn nghệ 6 người là : 4 2 C50 .C 20 (cách) TH 2. Đội văn nghệ có 9 người : Số cách chọn 6 bạn nam từ 50 nam và 3 bạn nữ từ 20 nữ tại thành đội văn nghệ 9 người là : C650 .C 320 (cách) TH 3. Đội văn nghệ có 12 người : Số cách chọn 9 bạn nam từ 50 nam và 4 bạn nữ từ 20 nữ tại thành đội văn nghệ 12 người là : 8 4 C50 .C 20 (cách) Vậy có cách lập thành một đội văn nghệ là : 4 2 6 3 8 4 C50 .C 20 +C50 .C 20 +C50 .C 20 (cách) Bài 24. Số người trong đội văn nghệ thóa măn yêu cầu bài toán là: 3,6,9 theo 3 trường hợp. TH 1: Đội văn nghệ có 3 người: Số cách chọn 2 bạn nam từ 60 nam và 1 bạn nữ từ 25 bạn nữ tạo thành đội văn nghệ 3 người là: 2 C60 1 C25 (cách) TH 2: Đội văn nghệ có 6 người: Số cách chọn 4 bạn nam từ 60 nam và 2 bạn nữ từ 25 bạn nữ tạo thành đội văn 4 nghệ 6 người là: C60 2 C25 (cách) TH 3: Đội văn nghệ có 9 người: Số cách chọn 6 bạn nam từ 60 nam và 3 bạn nữ từ 25 bạn nữ tạo thành đội văn 6 nghệ 9 người là: C60 3 C25 (cách) Vậy có cách lập thành một đội văn nghệ là: 6 C60 3 C25 C260 C125 4 + C60 C225 + (cách), Câu 25: Thi đại học có 2 môn lý, hóa. Mỗi môn có 50 câu, mỗi câu có 4 p/a. Tối đa chọn 1 p/a mỗi câu, đúng được 0,25, sai chả sao. a,Có bn cách điền phiếu trắc nghiệm môn lý. b,Cần có bn thí sinh tham gia để ít nhất 10 bạn có tổng lý, hóa bằng nhau. a, Có 50 câu trắc nghiệm môn lý, mỗi câu có 5 sự lựa chọn 50 vậy có 5 cách điền phiếu trắc nghiệm môn lý. b, Tổng điểm lý + hóa nhận giá trị từ 0->20 với khoảng cách 0,2 Vậy có 101 giá trị khác nhau. Để chắc chắn có 9 học sinh giống điểm nhau ta cần 101*9 = 909 học sinh Gọi n là số thí sinh nhỏ nhất để có 10 học sinh giống điểm nhau n = 909+1 = 910 học sinh. Bài 29. x 1+ x 2 + x 3=0 a) x 1 ≥ 1, x 2 ≥ 3 , x3 ≥ 0 Gọi N là số nghiệm của hệ phương trình: x 1+ x 2 + x 3=13 x 1 ≥ 1, x 2 ≥ 3 , x3 ≥ 0 Đặt x '1 x 1=1+ ¿ ' x 2=3+ x 2  N cùng là số nghiệm của hệ: X '1 + x '2+ x'3 =9 ' ' ' x 1 ≥ 0 , x 2 ≥0 , x 3 ≥ 0  N=C 93+9 −1 9 = C12=220 b)  Gọi N là số nghiệm của HPT : x 1+ x 2 + x 3=13 x 1 ≥ 0 , x 2 ≥3 , x 3 ≥ 5  Gọi N1 là số nghiệm của HPT : x 1+ x 2 + x 3=13 x 1 ≥ 0 , x 2 ≥3 , x 3 ≥ 0 Đặt ' x 2=3+ x 2 ' x 1+ x 2 + x 3=10  N1 cùng là nghiệm của HPT : x 1 ≥ 0 , x '2=0 , x 3 ≥0 10 10  N1 = C3 +10−1 = C12=66  Gọi N2 là số nghiệm của HPT : x 1+ x 2 + x 3=13 x 1 ≥ 0 , x 2 ≥3 , x 3 ≥ 6 Đặt : ' x 2=3+ x 2 ' x 3=6+ x 3 '  N2 cùng là số nghiệm của hệ ' 2+¿ x 3=4 x1 + x¿ x 1 ≥ 0 , X '2 ≥ 0 , x '3 ≥ 0 4 4  N2 = C3 +4−1 = C6 = 15  N = N1 – N2 = 66 – 15 =51 Bài 31. x 1+ x 2 + x 3=14 a) Gọi N là số nghiêm hệ phương trình : xz 1 ≥ 0 , x2 ≥3 , x 3 ≥ 1 ' Đặt : x 2=3+ x 2 ' x 3=1+ x 3 ' ' N cùng là số nghiệm của hệ : x 1+ x 2 + x 3=10 ' ' x 1 ≥ 0 , x 2 ≥0 , x 3 ≥ 0 10 10 N=C 3+10−1=C 12=66 b)  Gọi N là số nghiệm của hệ phương trình : x 1+ x 2 + x 3=14 x 1 ≥ 0 , x 2 ≤6 , x 3 ≥3  Gọi N1 là số n0 của hệ : x 1+ x 2 + x 3=14 x 1 ≥ 0 , x 2 ≥0 , x 3 ≥ 3 ' Đặt x 3=3+ x 3 N1 cùng là số n0 của hệ : x 1+ x 2 + x '3=14 ' x 1 ≥ 0 , x 2 ≥0 , x 3 ≥ 0 11 11 N 1=C 3+11−1=C13 =78  Gọi N2 là số n0 của hệ : x 1+ x 2 + x 3=14 x 1 ≥ 0 , x 2 ≥7 , x 3 ≥ 3 ' x 2=7+ x 2 Đặt : ' x 3=3+x 3 N2 cùng là số n0 của hệ : ' ' x 1+ x 2 + x 3=4 x 1 ≥ 0 , x '2 ≥0 , x '3 ≥ 0 4 4 N 2=C 3+4 −1=C6 =15 N=N 1 −N 2=78−15=63 Bài 33: a, Giải hệ thức truy hồi sau: a0=2, a1=6, an=3an-1-2an-2 với n≥2 b, Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n chứa 3 số 0 liên tiếp. c, Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n=7. Giải: a, Xét phương trình đặc trưng: k2-3k+2=0 (1) Phương trình (1) có hai nghiệm phân biệt r1=1; r2=2 Do đó {an} có công thức tổng quát: an=α1.r1n+α2.r2n= α1+ α2.2n a0=2, a1=6 nên ta có hệ : { a0=α 1 +α 2 ⋅2 0 a 1=α 1+ α 2 ⋅2 { α 1 +α 2=2 α 1 +2 α 2 =6 { a1=−2 α 2=4 n Vậy an= (−2 )+ 4. 2 b, Gọi an là số các xâu nhị phân có độ dài n và chưa ba số 0 liên tiếp. Ta có: a0=0 a1=0 a2=0 a3=1 Với n≥4 ta xét xâu nhị phân Xn có độ dài n và chứa 3 số 0 liên tiếp. +, Nếu X[n]=1 có an-1 xâu thỏa mãn +, Nếu X[n]=0 xét X[n-1] :  Nếu X[n-1]=0 ta xét X[n-2] : o Nếu X[n-2]=0 có 2n-3 xâu thỏa mãn o Nếu X[n-2]=1 có an-3 xâu thỏa mãn  Nếu X[n-1]=1 có an-2 xâu thỏa mãn Vậy an=an-1+an-2+an-3+2n-3 C, n=7 ta có : a4=a1+a2+a3+21=3 a5=a2+a3+a4+22=8 a6=a3+a4+a5+23=20 a7= a4+a5+a6+24=47 Câu 34: a, giải hệ thức truy hồi sau a0=4, a1=8. an  an 1  2an  2 với n �2 Giải Phương trình đặc trưng của hệ thức truy hôì là �r  2 r2  r  2  0 � � �r  1 Theo định nghĩa dãy { an  1 2n   2 (1) n với an } là nghiệm của hệ thức truy hồi: 1  2 , là hằng số.  0  1   2  2 � � 1  21   2 (1)  7 �  3 � � �1  2  1 � Vậy nghiệm của biểu thức truy hồi là:  n  3.2n  2(1) n . Với n �2