TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 LỜI GIẢI TÓM TẮT HOẶC ĐÁP SỐ t u r  (s  t) (  p q )  r  (s  u ) ______________ p 1) (1) (2) (3) (4)  s  u ( Do tiền đề (4) và luật đối ngẫu ) (5) (6) (7) (8) (9) (10) (11) ( 12) (13) (Do (5) và luật đơn giản nối liền) ( Do (1),(6) và luật phủ định) s (Do (5) và luật đơn giản nối liền)  t   s ( Do (7), (8) và phép tóan nối liền)  (t s) ( Do (9) và luật đối ngẫu) r (Do (2), (10) và luật phủ định) (  p q) (Do (3), (11) và luật phủ định) ( Do (12) và luật đối ngẫu) p  q p (Do (13) và luật đơn giản nối liền). u t 2) a) C > 0,  m , n ,( n  m  xn < C n ). b)  C > 0,  m , n ,( n  m  xn  C n ). 3) a)C > 0, d   ,  m , n  ( n ≥ m ⃓T(n)⃓ < C nd). b) C > 0,  d  ,  m ,  n  ( n ≥ m ⃓ T(n)⃓ ≥ C nd). 4) (tiền đề) 1) (q  s) 2) q  s 3) q và s 4) p  q 5) p 6) p s 7) ( p  s) (luật De Morgan) (luật đơn giản) (tiền đề) (PP phủ định) (Từ 3, 5 và định nghĩa phép nối liền) (luật De Morgan) 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 8) r  (p s) (tiền đề) 9) r (PP phủ định) 10) (t  p)  r (tiền đề) 11) (t  p) (PP phủ định) 12) t p (luật De Morgan) 13) t (luật đơn giản) Vậy suy luận đã cho là đúng. 5) (Tiền đề) 1) x  R(P( x)  Q( x)  R( x)) 2) P(a)  Q(a)  R(a) (Qui tắc đặc biệt phổ dụng với a bất kỳ) 3) P(a)  Q(a)  R(a) (Luật kéo theo) 4) Q(a)  P(a)  R(a) (Luật kéo theo) 5) x  R( P( x)  Q( x) (Tiền đề) 6) P(a)  Q(a) (Qui tắc đặc biệt hóa phổ dụng với a bất kỳ) 7) P(a)  Q(a) (Luật kéo theo) 8) P(a)  P(a)  R(a) (Từ 4 và 7, Tam đọan luận) 9) P(a)  P(a)  R(a) (Luật kéo theo) 10) P(a)  R(a) (Luật lũy đẳng) 11) R(a)  P(a) (Luật kéo theo) 12) x  R(R( x)  P( x)) (Qui tắc tổng quát hóa phổ dụng) 7) 8) C124 .C84 .1 = 5775. 3! a) 3281 b) 29615. a)5461512; b) 486000; c) 1959552; d) 1958040 9) a)2118760; b) 1050000 6) 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 10) 11) (366 – 266) + (367 – 267 ) + (368 – 268) = 2684483063360. X = {x  N: 1  x  20} với quan hệ  thông thường. a) min(A) = 8 và |A|  10  A = B {8} với B  Y = {9, 10,…, 20}, |B|  9. Số tập con A thỏa min(A) = 8 và |A|  10 = Số tập con B  Y = {9, 10,…, 20}, |B|  9 9 10 11 12  C12  C12  C12  C12  299 b) min(A) = 6 và max(A) = 18  A = {6, 18} C với C  Z = {7, 8,…, 17}. Số tập con A thỏa min(A) = 6 và max(A) = 18= Số tập con C  Z = {7, 8,…, 17}. = 211= 2048. 12) Đặt aj là số trận mà đội bóng chơi cho đến hết ngày thứ j trong tháng. Ta có a1, a2, …, an là một dãy tăng gồm các số nguyên dương khác nhau từng đôi và aj ≤ 45. Hơn nữa, a1+14 , a2 + 14, …, a30 + 14 cũng là một dãy số tăng gồm các số nguyên dương khác nhau với 15 ≤ aj +14 ≤59. Ta thấy rằng 60 số nguyên dương a1, a2, …, a30, a1 +14, a2 +14, …, a30 + 14 đều nhỏ hơn hoặc bằng 59. Áp dụng nguyên lý Dirichlet ta thấy có ít nhất hai trong 60 số nguyên dương nói trên phải bằng nhau. Như thế phải có ít nhất hai chỉ số i và j sao cho ai = aj +14. Do đó đúng 14 trận được đội bóng chơi từ ngày thứ j + 1 đến ngày thứ i. 13) a) s2 < s3 < s1 s3 = aba < ab * * * * < s1 = ac b) Mỗi vị trí * có 3 cách chọn. Do đó có 3* 3 *3 *3 = 81 chuỗi. 14) ĐS: 42580. 15) a) xn – xn–1 – 2xn–2  0. Phương trình đặc trưng 2 –  – 2 = 0 Có hai ngiệm thực là 1 = –1, 1 = 2. Nghiệm tổng quát là xn = C1(–1)n + C22n b) xn – xn–1 – 2xn–2  (6n – 5)2n–1 (1) thỏa điều kiện đầu x0 = 7, x1 = 4. 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Vì 2 là nghiệm đơn của phương trình đặc trưng nên (1) có một nghiệm riêng dạng xn = n(an + b)2n Thế vào (1) ta được n(an + b)2n – (n – 1)[a(n –1) + b]2n – 1 – 2(n – 2)[a(n – 2) + b]2n – 2 = (6n – 5)2n – 1  12an – 10a + 6b = 12n – 10  12a = 12, – 10a + 6b = –10  a = 1, b = 0. Vậy một nghiệm riêng của (1) là xn = n22n. Nghiệm tổng quát của (1) là xn = C1(–1)n + C22n + n22n Thế điều kiện x0 = 7, x1 = 4 ta được C1  C2  7 C  4  1  C1  2C2  2  4 C2  3 Vậy xn = 4(–1)n + 3.2n + n22n 16) a) ĐS: an = c 3n +dn 3n . b)ĐS: an = (2 +n )3n + 𝑛2 2 (n + 3) 3n 17) a) an = ( A + n B) 3 n + (n – 2) n 2 3 n b) Tìm số các chuỗi nhị phân chiều dài n chứa chuỗi con 00. Gọi an là số chuỗi nhị phân chiều dài n chứa chuỗi con 00. Ta có a0 = 0, a1 = 0. Ta tính an: 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012   TH1 : Nếu bit đầu tiên là bit 1 thì có an – 1 cách chọn n – 1 bit còn lại. TH2 : Nếu bit đầu tiên là bit 0 thì có hai TH xảy ra: Bit thứ 2 là bit 1 : có an – 2 cách chọn n – 2 bit còn lại Bit thứ 2 là bit 0 : có 2n – 2 cách chọn n – 2 bit còn lại ( các bit này chọn 0 hay 1 đều được) Vậy an = an – 1 + an – 2 + 2n – 2 ( n  2) (1). Hệ thức đệ qui TTTN : an = an – 1 + an – 2 (2) PTĐT : x2 – x – 1 = 0 có 2 nghiệm đơn là 𝑥1,2 = 𝑛 1+ 5 Nghiệm tổng quát của (2) là an = A 2 1± 5 +𝐵 2 1− 5 2 𝑛 Ta tìm một nghiệm riêng của (1) dưới dạng an = C2n. Thay vào (1) : C2n = C2n – 1 + C2n – 2 + 2n – 2  4C = 2C + C + 1  C = 1. Nghiệm TQ của (1) là an = A 2 Sử dụng ĐK đầu : A + B + 1 = 0 A 1+ 5 2  A=an = − 5+3 5 1+ 5 10 2 𝑛 +𝐵 5+3 5 10 − 𝑛 1+ 5 1− 5 2 ,B=- 5−3 5 10 1− 5 +𝐵 2 𝑛 + 2n . +2 = 0. 5−3 5 10 𝑛 1− 5 2 + 2n 18) a) an = an-1 + 6an-2 được viết lại an - an-1 - 6an-2 = 0 (1) Phương trình đặc trưng của (1) là x2 - x - 6 = 0 có 2 nghiệm là x = -2 và x = 3. Nên nghiệm tổng quát của (1) là an = C1(-2)n + C23n. b) Đặt fn = 10n(-2)n - 3(-2)n-1 = (-2)n(10n + 3/2).Vì -2 là 1 nghiệm của phương trình đặc trưng nên nghiệm riêng có dạng n(-2)n(An + B). (3) Thế (3) vào hệ thức ban đầu ta có: n(-2)n(An + B) = (n-1)(-2)n-1(A(n-1) + B) + 6(n-2)(-2)n-2(A(n-2) + B) + (-2)n(10n + 3/2) (4). 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Thế n = 2 vào (4), ta có: 2(-2)2(2A + B) = (-2)(A + B) + (-2)2(10.2 + 3/2) ⇔ 16A + 8B = -2A - 2B + 86 ⇔ 18A + 10B = 86 ⇔ 9A + 5B = 43 (5) Thế n = 1 vào (4), ta có: (-2)(A + B) = 6(-1)(-2)-1(B - A) + (-2)(10 + 3/2) ⇔ -2A - 2B = 3B - 3A - 23 ⇔ A - 5B = -23 (6) Từ (5) và (6) ta có hệ phương trình 9𝐴 + 5𝐵 = 43 𝐴 − 5𝐵 = −23 Giải hệ này ta có: A = 2 và B = 5 Như vậy nghiệm tổng quát của hệ thức là: an = C1(-2)n + C23n + n(-2)n(2n + 5) (7) Thế điều kiện đầu vào (7), ta có: a0 = 8 = C1(-2)0 + C230 + 0(-2)0(2.0 + 5) ⇔ C1 + C2 = 8 (8) a1 = 5 = C1(-2)1 + C231 + 1(-2)1(2.1 + 5) ⇔ -2C1 + 3C2 = 19 (9) Từ (8) và (9) ta có hệ phương trình: C1 + C2 = 8 -2C1 + 3C2 = 19 Giải hệ phương trình trên ta có C1 = 1 và C2 = 7. Vậy nghiệm của hệ thức đệ qui (1) là: an = (-2)n + 7.3n + n(-2)n(2n + 5). 19) a)Gọi Pn là tổng số tiền có trong tài khoản vào cuối năm thứ n. Như vậy: 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Số tiền có trong tài khoản vào ngày đầu của năm thứ nhất sẽ là: P0 = 100 triệu Số tiền có trong tài khoản vào ngày cuối năm của năm thứ nhất là: P1 = P0 + Lãi 1 + Lãi 2 Trong đó: Lãi 1 = 20% tổng số tiền có trong tài khoản cả năm = 0.2 * P0 Lãi 2 = 45% tổng số tiền có trong tài khoản của năm trước đó = 0.45 *0 Vậy : P1 = P0 + 0.2 P0 Số tiền có trong tài khoản vào ngày cuối năm thứ hai sẽ là: P2= P1 + 0.2*P1 + 0.45*P0 Tổng số tiền có trong tài khoản vào cuối năm thứ n sẽ là: Pn= Pn-1 + 0.2*Pn-1 + 0.45*Pn-2 = 0.45*Pn-2 +1.02*Pn-1 b)Giải hệ thức đệ qui tuyến tính thuần nhất với P0 =100, P1 = 120 ta được n Pn = n 250  3  50  3       3 2 3  10  . 20) a)Gọi Ln là số cách xếp số xe máy, xe đạp cho đầy n lô số cách xếp cho đầy n lô với vị trí đầu tiên là xe đạp là Ln-1 số cách xếp cho đầy n lô với vị trí đầu tiên là xe máy là Ln-2 Vậy: Ln = Ln-1 + Ln-2 b)Giải hệ thức đệ qui với điều kiện đầu: L0 = 1, L1 = 1 ta được 1 1 5  Ln    5 2  n 1 1 1 5     5 2  n 1 21) Giả sử n-1 đường thẳng chia mặt phẳng thành xn-1 miền. 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Đường thẳng thứ n cắt n-1 đường thẳng cho trước tại n-1 giao điểm . Trong đó: có n-2 đọan thẳng hữu hạn có 2 đọan có một đầu vô hạn Mỗi đọan thẳng này phân miền mặt phẳng nó đi qua thành 2 miền . Do vậy sẽ tăng thêm n miền. Vậy: xn = xn-1 + n Giải hệ thức đệ qui tuyến tính không thuần nhất với điều kiện đầu x0 = 1, x1 = 2 ta được xn  1  22) n(n  1) 2 . Tìm tất cả các công thức đa thức tối tiểu của hàm Bool 4 biến sau: f ( x, y, z, t)  xyz  y(xz  zt )  xy(z t  z ). f ( x, y, z, t)  xyz  x yz  y zt  xyz t  xy z. Vẽ kar(f): x x x x z z 2 z 4 5 z 6 7 y y 1 t 3 t t 8 y t y Các tế bào lớn: x yz , x yt , yzt , xyt , xz , y zt . 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 x x x z z 2 z 4 5 z 6 7 y y t z 3 t z 2 t z 4 5 t z 6 7 y y y x yz x x x z z 2 z 4 5 z 6 7 y y x x x x z z 2 z 4 5 z 6 7 y y t z 3 t z 2 t z 4 5 t z 6 7 y y y x 1 t 3 t t 8 t y y x x 1 t 3 t t 8 t y y xyt x x x 1 t z 3 t z 2 t z 4 5 t z 6 7 y y 8 y x 1 yzt x x x yt 8 y x 1 8 y x x y xz x x 1 t 3 t t 8 t y y y zt Tế bào lớn nhất thiết phải chọn: xz . 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Các công thức đa thức tương ứng với các phủ tối tiểu gồm các tế bào lớn: f  xz  yzt  x yt (F1 ) f  xz  yzt  xyz  yzt (F2 ) f  xz  xyt  x yz  x yt (F3 ) f  xz  xyt  x yz  y zt (F4 ) So sánh ta thấy công thức (F1) thực sự đơn giản hơn các công thức khác. Suy ra f có một công thức đa thức đối tiểu là f  xz  yzt  x yt (F1) 23) a)Biểu đồ Karnaugh của f gồm các ô gạch chéo Suy ra biểu đồ Karnaugh của 𝑓 gồm các ô trắng. b)Dạng nối rời chính tắc ( dạng tuyển chuẩn tắc) của 𝑓 . 𝑓 = 𝑥 𝑦 𝑧 t  x 𝑦 𝑧𝑡  x y z 𝑡  𝑥 y z 𝑡  𝑥 y z t  𝑥 y 𝑧 t 24) a) Các tế bào lớn: y t , z y , x zt ,, x yt , x y z , x z t b) ĐS : Có ba công thức đa thức tối tiểu là y t  y z  x zt  x y z , y t  y z  x yt  x y z , y t  y z  x yt  x z t 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 25) G đẳng cấu với G’. f(u1) = v6, f(u2) =v3, f(u3) = v4, f(u4) = v5, f(u5) = v1, f(u6) = v2  u  1  u2  M G   u3  u4   u5 u  6 u1 u2 0 1 1 0 0 1 u3 u4 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 u5 u6  0 0  0 1  0 0 1 0  0 1 1 0  MG'  v  6  v3    v4  v5   v1 v  2 v6 0 1 0 1 0 0 v3 v4 1 0 0 1 1 0 0 1 0 0 1 0 v5 1 0 1 0 1 0 v1 v2  0 0  0 1  0 0 1 0  0 1 1 0  MG = MG’ 26) 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 v1 0 - v2 (  ,-) (1,v1)* - v3 (  ,-) (  ,-) (5, v2) (5, v2)* - v4 (  ,-) (  ,-) (  ,-) (  ,-) (10, v3) (10, v3) (10, v3) (9,v6) (9,v6)* - v5 (  ,-) (10, v1) (10, v1) (10, v1) (6,v3) (6,v3)* b (  ,-) (4,a) (4,a) (4,a)* - c (  ,-) (3,a) (3,a)* - d (  ,-) (  ,-) (  ,-) (9,b) (9,b)* - e (  ,-) (  ,-) (10, c) (10, c) (10, c) (10, c) - - - v6 (  ,-) (  ,-) (  ,-) (  ,-) (7,v3) (7,v3) (7,v3)* - v7 (  ,-) (  ,-) (  ,-) (9,v9) (9,v9) (9,v9) (7,v5) (7,v5)* - v8 (  ,-) (6,v1) (6,v1) (5,v9) (5,v9)* - f (  ,-) (  ,-) (  ,-) (  ,-) (14,d) (14,d) (12,g) (12,g)* - g (  ,-) (  ,-) (  ,-) (  ,-) (11,d) (11,d) (11,d)* - z (  ,-) (  ,-) (  ,-) (  ,-) (  ,-) (  ,-) (15,g) (15,g) (15,g)* v9 (  ,-) (3,v1) (3,v1)* - v10 (  ,-) (  ,-) (  ,-) (11,v9) (11,v9) (11,v9) (11,v9) (11,v9) (10, v7) (10, v7)* 27) a 0 0* - - - Đường đi ngắn nhất từ a đến z là abdgz với chiều dài 15. 28) s x y z t 0* (, - ) (, - ) (, - ) (, - ) (10, s ) (5, s )* (, - ) (, - ) (8, y ) (14, y ) (7, y )* (8, y )* (13, t ) (9, x )* d(s, x) = 8. Đường đi : syx ; d(s,y) = 5. Đường đi: sy; d(s,z) = 9. Đường đi: syxz d(s, t) = 7. Đường đi: syt Tương tự ta được bảng sau với đồ thị mới 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 s 0* - x (, - ) (10, s ) (2, y )* - y (, - ) (5, s )* - z (, - ) (, - ) (14, y ) (3, x )* - t (, - ) (, - ) (7, y ) (7, y ) (7, y )* Tuy nhiên kết quả bây giờ không phải là đường đi ngắn nhất. Chẳng hạn trong cột y ta được đường đi sy với chiều dài 5. Tuy nhiên đường đi syxy có chiều dài là 5 – 3+2 = 4 < 5. 29) a) Dùng thuật toán Dijkstra ta tìm được đường đi ngắn nhất từ a đến các đỉnh e (độ dài 6): a b c d e f g h 0* (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (6,a) (3,h)* (, ) (,) (, ) (10, h) (4,h) (4,a) (8,b) (9,b) (, ) (8,b) (9,b) (, ) (5,b)* (8,b) (9,b) (5,b) (2,a)* (4,h)* (6,f)* b a 2 1 h 2 f 1 e b) Đường đi ngắn nhất từ đỉnh a đến đỉnh d nhưng phải đi qua đỉnh e gồm các đường đi ngắn nhất từ a đến e và đường đi ngắn nhất từ e đến d. Dùng thuật toán Dijkstra tìm được đường đi ngắn nhất từ e đến d (độ dài 4) như sau: 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 e a b c d f g h 0* (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (1,e)* (5,e) (1, e) (, ) (, ) (, ) (6,c) (4,c) (1,e)* (, ) (,) (, ) (3,f)* (4,c) (10,f) (9,f) (7,b) (4,c)* (17,f) (4,h) c 3 d 1 e Suy ra đường đi cần tìm như sau (có độ dài là 6 + 4 = 10): b a 2 c 1 h 3 2 d 1 f 1 e Trong tập hợp các hàm Boole của 5 biến có 25 = 32 từ tối tiểu. 6 Số cách chọn 6 từ tối tiểu trong 32 từ tối tiểu là 𝑐32 = 906102 31) Đồ thị đủ Kn có n(n – 1 )/ 2 cạnh. Do đó G có n(n – 1 )/ 4 cạnh. Suy ra n chia hết cho 4 hoặc n – 1 chia hết cho 4. 30) 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 32) K4< K5 <K2 <K11 <K9 <K3<K6<K1<K10<K8<K7<K14<K12<K13 K1 K7 K2 K4 K5 K8 K3 K9 K6 K10 K12 K14 K13 K11 Để chèn thêm khóa K với K6 < K < K1 ta cần so sánh nó với K1, K2, K3, K6. Do đó cần 4 phép so sánh. 33) Tính chất: Nếu T là cây nhị phân đủ gồm N nút trong thì T có N + 1 nút lá. CM. Mỗi nút trong của cây nhị phân đủ đều có bậc ra là 2, còn mỗi nút lá của nó đều có bậc ra bằng 0. Do đó tổng bậc ra của tất cả các nút là 2N. Theo định lý về bậc thì số cạnh m = 2N. (1) Vì T là cây nên số cạnh của nó là m = N + l – 1 .( Ở đây l là số nút lá).(2) Từ (1) , (2) ta có : 2N = N + l – 1 . Suy ra l = N + 1. Giải câu 33. a) Gọi T là một cây nhị phân đủ ( mỗi nút trong có đúng hai nút con) với N nút trong và có chiều cao h. Chứng minh rằng : h ≥ 𝑙𝑜𝑔2 (𝑁 + 1) 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Ta CM qui nạp theo chiều cao h BĐT l  2h Rõ ràng bất đẳng thức đúng khi h = 1( lúc này l = 2). Giả sử BĐT đúng với mọi cây có chiều cao  h – 1 . Xét T là cây có chiều cao h. Gọi l1, l2 là số nút lá của cây con T1, T2 là cây con bên trái và bên phải của nút gốc. Để ý rằng T1 và T2 là các cây có chiều cao  h – 1 nên theo giả thiết qui nạp ta có l =l1 +l2  2. 2h-1 = 2h. Vậy h  log2l  h  log2(N + 1)  h ≥ 𝑙𝑜𝑔2 (𝑁 + 1) . b) Do cây là cây cân bằng nên các nút ở mức  h – 2 đều là nút trong. Vì vậy tổng số nút mức h – 1 là 2h -1 . Tổng số nút lá ở mức h bằng 2 lần số nút trong ở mức h – 1 nên 2h – 1 < N + 1  2h  h – 1 < log2(N + 1)  h  h = 𝑙𝑜𝑔2 (𝑁 + 1) Giải thích : N + 1 = l= lh + lh – 1 = 2Nh – 1 + lh – 1 = Nh – 1 +Nh – 1 + lh – 1 = Nh – 1+ 2h – 1 > 2h – 1 . 34) . R không phải là thứ tự toàn phần vì (1, 2) và (2, 1) không so sánh được với nhau. Định nghĩa quan hệ R’ trên  2 bởi ( a, b) R’ (c, d) khi và chỉ khi a < c hoặc a = c và b  d. Rõ ràng R’ là thứ tự toàn phần trên  2 . Giả sử A là một tập con khác rỗng của  2 . Khi ấy tập các thành phần thứ nhất của những phần tử trong A là một tập con khác rỗng của  nên có phần tử bé nhất là m. Khi đó tập con các thành phần thứ hai của những cặp trong A với thành phần thứ nhất là m sẽ có phần tử bé nhất là n . Rõ ràng (m ,n ) là phần tử bé nhất của A. 35) Vì 2310 = 2*3*5*7*11 nên mỗi ước 1 của 2310 là tích của các số nguyên tố thuộc một tập con của S ={2, 3, 5, 7, 11}. Ta có thể đồng nhất ước này với dãy số nguyên a1a2 …am trong đó 2  a1 < a2 <…<am  11, và {a1, a2, …, am} S. Thứ tự R được định nghĩa sao cho 1 là phần tử bé nhất. Nếu hai ước a  1 b được biễu diễn bởi hai dãy a1 a2 …am và b1b2…bp ta định nghĩa a R b khi và chỉ khi m < p hoặc m = p và a1 a2 …am trội b1b2…bp theo thứ tự tự điển. Chứng minh dễ dàng R là thứ tự toàn phần trên U. 36) . 37) . 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 38)   D   4 7 5   7 6      1 11     D1     4 7   1 5 7  9  6       D3     4 7   1 5 13 7 6     8 7   Q   1 2   2   Q1     1 2 3   3 4      2 1  2 3 2  3 4      2 2 2   Q3     1 3 3  3  4       D2     4 17 10 D4     4 7   1 7 7  1 5 13 7 6     8 7 5 13 7 6     8 7   Q2     1 2 4 Q4     1 2 3 2  3 4      2 2 2 2 3 2 4 3 4      2 2 2 39) a) Ta CM bằng phản chứng. Giả sử G không liên thông. Khi đó G có ít nhất hai thành phần liên thông, trong đó phải tồn tại thành phần liên thông H với < n/2 đỉnh. Trong H bậc của 𝑛 mỗi đỉnh < − 1, trái giả thiết. 2 b) Theo câu a) thì G liên thông. Gọi G’ là đồ thị thu được từ G bằng cách bỏ đi một đỉnh. Nếu G’ không liên thông thì tồn tại một thành phần liên thông H có  𝑛−1 đỉnh. Trong H mỗi đỉnh 2 40) − 1. Khi đó trong G đỉnh P có bậc  𝑛−1 . Trái giả thiết. P có bậc  𝑛−1 2 2 Rõ ràng ta chỉ cần CM cho G liên thông là đủ. Ta CM bằng phản chứng. Giả sử G liên thông và G - e có ít nhất 3 thành phần liên thông. Trả lại cạnh e cho G. Ta thấy e chỉ có thể nối nhiều lắm là 2 trong 3 thành phần liên thông của G – e với nhau, và do đó G có ít nhất hai thành phần liên thông. Trái giả thiết G liên thông. 41) Ta CM qui nạp theo số cạnh m của G. Với m = 0 thì khẳng định hiển nhiên đúng ( Mỗi đỉnh là một thành phần liên thông). 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Giả sử kết luận bài tóan đúng cho m = k cạnh. Xét G tùy ý có k+ 1 cạnh. Bỏ một cạnh ra khỏi G ta thu được G’ có k cạnh. Trong G’ có ít nhất n – k thành phần liên thông. Theo Câu 17 số thành phần liên thông trong G’ không vượt quá 1 so với G. Do đó số thành phần liên thông trong G không ít hơn n – k – 1 = n – ( k + 1). Vậy kết luận đúng cho m = k+1. 42) a) (a + b)2 + c : +  + a b 2 c ab+2c+ a + b2 + c : + + a  b 2 c ab2+c+ 2 2 (a + b) = a + b2 + 2ab :  + a b 2 = + + a 2 b 2 * 2 * ab a b + 2  = a 2 b 2 + 2 a b * * + 2 b) (a + b) / (c – d ) [(x + y)2 – (x – y )2]/(x*y) 43) a)Vẽ cây biểu diễn của biểu thức + + ^ + x ^ x x ^ x 4 3 2 b)duyệt cây theo tiền thứ tự ta được biểu thức theo ký pháp Ba Lan: + + + x^ x 2 ^ x 3 ^ x 4 . 44) a) 3 x  y z /  x y  2 / z ^  18 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 + – ^ 3 / / * x – z y x z 2 y b) Biểu thức trên được viết theo ký pháp thông thường như sau: z y xy 3x     . z  2  19 CuuDuongThanCong.com https://fb.com/tailieudientucntt