Xemtailieu Tải về 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 pq 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 : (pr)(qr)=(pq)r Giải p q r pr qr pq 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=7Có 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 21 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 Tải về bản full