Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Toán rời rạc - Phần 4

Nội dung text: Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Toán rời rạc - Phần 4

1. TOÁN TÔ HỢP – RỜI RẠC (Phần 4) Bài 1. Cho S là một tập hợp có tính chất: i) Một phần tử là một dãy 15 kí tự viết liền nhau, mà chỉ gồm hai kí tự a và b ii) Hai phần tử phân biệt của là hai dãy khác nhau tại ít nhất 3 vị trí. Chứng minh rằng số phần tử của không vượt quá 211 . Hướng dẫn giải: Để cho đơn giản ta mã hóa a là 0, b là 1. Thế thì đơn giản là tập các dãy nhị phân có độ dài 15 sao cho hai dãy bất kì có ít nhất ba vị trí khác nhau. Với mỗi phần tử sS , có đúng 15+1=16 dãy nhị phân độ dài 15 (bao gồm cả s ) khác tại nhiều nhất một vị trí. Ta kí hiệu Bs là tập các dãy như vậy (các phần tử của ngoại trừ đều không nằm trong ). Với s,t S phân biệt ta có BBst vì một dãy thuộc khác tại nhiều nhất một vị trí do vậy khác t tại ít nhất 2 vị trí và như thế không thể thuộc Bt . 15 11 Do đó, S .16  Bss  B 2 cho nên S2 . sS sS Bài 2. Cho một bảng hình vuông gồm 2013 2013ô vuông. Hỏi có bao nhiêu cách tô hai màu xanh hoặc đỏ vào các ô vuông trong bảng sao cho mỗi hình vuông 22 có số ô được tô bởi hai màu bằng nhau. ( Hai cách tô được gọi là khác nhau nếu có một ô vuông nào đó mà trong cách này thì được tô màu đỏ còn cách kia thì được tô màu xanh). Hướng dẫn giải: Gọi Sn là số cách tô trong bảng n n,  n 1. Xét tập Tn gồm các ô vuông nằm trong cột n (tính từ trái sang) và hàng n (tính từ trên xuống). Ta gọi An là số các cách tô sao cho hai ô kề nhau trong có cùng màu và Bn là số các cách tô sao cho các ô trong có màu xen kẽ. Nhận xét 1: mỗi cách tô thuộc sẽ ứng với một cách tô thuộc Bn1 , còn mỗi cách tô thuộc sẽ ứng với một cách tô thuộc An1 và một cách tô thuộc . ( Điều này suy ra khi xét bảng ô vuông n 1 n 1 có được từ bảng nn sau khi bỏ ) Nhận xét 2: Mỗi cách tô thuộc sẽ ứng với một cách tô thuộc Tn1 , Mỗi cách tô thuộc sẽ ứng với một cách tô thuộc Tn2 , Từ đó ta có: Bn B, n 1 A n A n 1 B, n 1 n2 Sn A n B n A n 1 B n 1 B n ,  n 2 Suy ra: Sn 2(A n 1 B)(A n 1 n 2 B n 2 ), n3 1
2. = 2Sn 1 S n 2 ,  n 3 (1) Nhận xét 3: S62 và S3 14 Đ X X Đ X X Đ Đ X Đ Đ X X Đ Đ X Đ Đ X X X Đ Đ X X Đ X Đ X Đ X Đ Đ Đ Đ X Đ X Đ X Đ X X X X X Đ X X Đ X Đ X X X X Đ X Đ X X Đ X Đ Đ Đ Đ X Đ X Đ X X Đ Đ Đ Đ X Đ X Đ X Đ X X X X Đ X Đ X Đ X Đ X X X X Đ X Đ X Đ X Đ Đ Đ Đ Từ (1) ta suy ra Sn S n 1 = S n 1 S n 2 . . . =S 3 S 2 8 Đ X Đ Đ X Đ X Đ Đ Đ Đ X Đ X Đ Đ X Đ X X X Sn 8S n 1 S n S 2 (n2)88n10 X Đ X Đ X Đ Đ X X X X Đ X Đ X Đ X Đ Đ Đ Đ Vậy có S2013 8 2013 10 16094 cách tô màu thỏa yêu cầu bài toán. Bài 3. Trong mặt phẳng tọa độ Oxy, xét tập hợp S x,y |1 x,y 12;x,y . Mỗi điểm của S được tô bởi một trong ba màu xanh, đỏ, vàng. Chứng minh rằng tồn tại hình chữ nhật có các cạnh song song với hai trục tọa độ, cố bốn đỉnh thuộc S và được tô cùng một màu. Hướng dẫn giải: Từ giả thiết suy ra số phần tử của S là 144. Không giảm tính tổng quát, giả sử tô các điểm được tô đỏ của S là nhiều nhất. Theo nguyên llý Dirichlet, số các điểm đỏ trong S ít nhất là 48. 12 Ký hiệu các điểm màu đỏ có tung độ i là mi , i 1,2,...,12 ta có mi 48. i1 m m 1 Số các cặp điểm màu đỏ có tung độ là C2 ii . mi 2 Sô có cặp điểm màu đỏ có cùng tung độ trong S là : 12 12m m 1 11 12 12 C22 ii m m mii   m  i i 1 i 12 2 i 1 2 i 1 2 1 12 1 12 1 12 12 1 mi  m i  m i  m i 12 .48 48 12 72 24 i 1 2 i 1 24 i 1 i 1 24 2
3. Vậy số các cặp điểm màu đỏ có cùng tung độ trong S ít nhất là 72 cặp. 2 Mặt khác số cặp điểm trên trục hoành có tung độ là các số nguyên từ 1 đến 12 là C12 66. Do đó khi chiếu các cặp điểm màu đỏ lên trục hoành có ít nhất 2 cặp hình có chiều trùng nhau, hai cặp điểm này xác định hình chữ nhật thỏa mãn yêu cầu. Bài 4. Cho n là một số nguyên dương chẵn lớn hơn hoặc bằng 4. Ta tô màu mỗi n số trong các số nguyên dương từ 1 đến sao cho số trong chúng được tô màu xanh và số còn lại 2 được tô màu đỏ. Với mỗi cách tô như vậy, kí hiệu fn là số các số nguyên dương bất kì mà nó có thể viết được dưới dạng tổng hai số khác màu. a. Tìm tất cả các giá trị của f.4 b. Khi n 8, chứng minh rằng fn 2n 3. Hãy chỉ ra một cách tô màu thỏa mãn fn 2n 5. Hướng dẫn giải: +) Không mất tổng quát, coi 1 được tô xanh. Ta có các trường hợp sau: 1X 2X (suy ra 3Đ 4Đ) : f34 (các số viết dưới dạng tổng của hai số khác màu là 4; 5; 6); 1X 2Đ 3X (suy ra 4Đ) : (các số viết dưới dạng tổng của hai số khác màu là 3; 5; 7); 1X 2Đ 3Đ (suy ra 4X) : f44 (các số viết dưới dạng tổng của hai số khác màu là 3; 4; 6; 7); Vậy f4 3;4 . +) Ta xét với n 8. Rõ ràng fn 2n 3,do các số có thể viết dưới dạng tổng của hai số khác màu luôn lớn hơn hoặc bằng 3 và nhỏ hơn hoặc bằng 2n 1. Nếu fn 2n 3thì từ 3 đến (n 1) đều viết được dưới dạng tổng của hai số khác màu. Và do đó, ta có thể coi 1X, 2Đ. Lại vì các số từ 4 đến cũng viết được dưới dạng tổng của hai số khác màu nên n 3Đ, 4Đ, , (n 2) Đ. Lúc này, các số được tô Đ vượt quá , vô lý. Vậy 2 Ta chỉ ra cách tô màu thỏa mãn fn 2n 5. Thật vậy, giả sử n 2k, ta tô X các số 1; 2; 4;  ; 2k 2, tô Đ các số 3; 5;  ; 2k 1; 2k. Khi đó, các số viết được dưới dạng tổng của hai số khác màu là tất cả các số từ 4 đến 4k 2, tức có 4k 5 số mà nó có thể viết được dưới dạng tổng của hai số khác màu. 3
4. Bài 5. Cho tập hợp gồm 2014 phần tử sau: 1;2; 3;.....; 2014 . Cần loại bỏ ít nhất bao nhiêu phần tử khỏi tập hợp trên, sao cho tập hợp còn lại có tính chất: không có phần tử nào bằng tích hai phần tử còn lại khác. Hướng dẫn giải: Trước hết, ta loại bỏ các số 2, 3, 4, 5, .., 44, và chứng minh tập các số còn lại là {1;45;46; ..;2014} thỏa mãn đề bài. Thật vậy, nếu trong 2 số có một số bằng 1 thì hiển nhiên 1.x x y luôn đúng với mọi x {45; 46; ..; 2014} và y {45; 46; ..; 2014}\{x}. Nếu không số nào bằng 1, tức là x, y {45; 46; ..; 2014} và xy , thì xy 452 2025 2014 sẽ không thuộc tập đã cho. Như vậy, ta đã chỉ ra một cách loại bỏ 43 phần tử thỏa mãn đề bài. Bây giờ, ta xét một cách loại bỏ bất kỳ ít hơn 43 phần tử. Xét 43 bộ số: (2; 87; 2 87) (3; 86; 3 86) (4; 85; 4 85) . (44; 45; 44 45) Do tất cả các số trong các bộ trên đôi một khác nhau, và ta chỉ loại bỏ ít hơn 43 phần tử, nên trong tập còn lại sẽ chứa ít nhất một trong số các bộ trên. Bộ ba số ấy sẽ không thỏa mãn đề bài, nên cách loại bỏ đang xét cũng không thỏa mãn bài toán. Vậy ta cần loại bỏ ít nhất 43 phần tử. Bài 6. Trong một lớp học có 30 học sinh gồm 15 học sinh nam và 15 học sinh nữ. Các học sinh này được đánh số thứ tự từ 1 đến 30 (mỗi học sinh chỉ được đánh một số và mỗi số chỉ được đánh cho đúng một học sinh) theo nguyên tắc: Các học sinh nam được đánh số lẻ, các học sinh nữ được đánh số chẵn. Từ 30 học sinh trên có bao nhiêu cách chọn ra một nhóm học sinh mà tổng số thứ tự của các học sinh trong nhóm không nhỏ hơn 233 đồng thời số học sinh nam và số học sinh nữ trong nhóm bằng nhau. Hướng dẫn giải: Cho tương ứng mỗi nhóm học sinh được chọn với một tập con M của tập hợp A {1,2,3.,...,30} thỏa mãn: “S(M)  a 233 và trong thì số lượng các số chẵn bằng số lượng các số lẻ” (*). Ta sẽ đếm aM số các tập con như vậy. 4
5. Trước hết ta xét các tập con của A có số lượng các số chẵn bằng số lượng các số lẻ. Số cách chọn ra k k phần tử chẵn là C15 và số cách chọn ra phần tử lẻ là , với k {0,1,...,15}. Do đó, số cách chọn ra 15 15 k k k 2 tập con có số lượng các số chẵn bằng số lượng các số lẻ là C15 .C 15 (C 15 ) . k 0 k 0 15 k 2 15 Chứng minh được: (C15 ) C 30 . k0 Gọi (A) là tập các tập con của có số lượng các số chẵn bằng số lượng các số lẻ (coi  là một tập như vậy). Ta thấy, nếu M  (A) thì A \ M  (A). Bởi vậy xét ánh xạ f: (A)  (A),M f(M) A\M. Dễ thấy f là một song ánh. Vì a 465 nên nếu S(M) 233 thì S(A \ M) 232 . Suy ra, nếu thỏa mãn (*) thì aA và không thỏa mãn (*), do đó số cách chọn ra nhóm học sinh thỏa mãn bài toán là | (A) | C15 30 . 22 Bài 7. Giả sử có sự phân hoạch thành hai tập hợp A, B. Chứng minh rằng  n tồn tại a,b phân biệt lớn hơn n sao cho { a, b, a + b } là tập con của A hoặc B. Hướng dẫn giải: Do  AB. - Nếu B là tập hữu hạn tồn tại m là phần tử lớn nhất của B. Với mọi n lấy a, b > max{n, m } thì a, b, a + b > m a,b,a b  A . - Nếu B là tập vô hạn lấy b, c B phân biệt sao cho b, c > n. Lấy aB sao cho a – b > n, a > c a > n. Giả sử không tồn tại a, b phân biệt sao cho a,b,a  b A a c,b c A a,b,a  b B Do a – b > n, a, b B mà a – b+ b = a a b A . M Mà ( a – b) + (b + c) = a + c A a b,b c,a c  A ( mâu thuẫn ). a, b, a+b  A Vậy a,b ,a,b n sao cho a, b, a+b  B. 5
6. Bài 8. Xếp 10 học sinh ngồi quanh một bàn tròn. Ngân hàng đề có tất cả 5 loại đề thi. Hỏi có bao nhiêu cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh nhau có cùng đề thi? Hướng dẫn giải: Gọi Sn là số cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh nhau có cùng đề thi Cố định một học sinh làm vị trí đầu tiên và các học sinh bên tay phải của học sinh đó là vị trí thứ 2, thứ 3, , thứ n.( học sinh ở vị trí thứ n ngồi cạnh học sinh ở vị trí thứ nhất) Ta thấy: Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi khác nhau thì sẽ có 3 cách phát đề cho học sinh ở vị trí thứ n. Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi giống nhau thì có 4 cách phát đề cho học sinh ở vị trí thứ n. Do đó ta có hệ thức: Sn 3S n 1 4S n 2 n 4 Sử dụng phương pháp sai phân để tính . Xét phương trình đặc trưng: 2 x1 n n x 3x 4 0 Sn a( 1) b4 x4 Do S23 5.4 20,S 5.4.3 60 Ta có: a 16b 20 a 4 a 64b 60 b 1 n n 10 Vậy Sn 4 1 4 S 10 4 4 Bài 9. Cho S 1,2,...,2014, với mỗi tập tập con khác rỗng TS , ta chọn một phần tử của nó làm phần tử đại diện. Tìm số cách ký hiệu phần tử đại diện cho mọi tập con khác rỗng của S thỏa mãn với mỗi tập khác rỗng là hợp của các tập khác rỗng không giao nhau A,B,C S , thì phần tử đại diện của D cũng là phần tử đại diện của một trong ba tập A, B, C. Hướng dẫn giải: + Với mỗi tập XS , ký hiệu rX là phần tử đại diện của X. Giả sử x1 r S . Trước hết ta chứng minh khẳng định sau: Nếu xX1 và thì x1 r X . - Nếu X 2012, ta viết S thành hợp của ba tập không giao nhau gồm X và hai tập con khác nữa của S. Từ giải thiết suy ra . 6
7. - Nếu X 2013, xét phần tử y S, y x1 . Coi S là giao của ba tập không giao nhau gồm x1 , y và hai tập khác nữa, áp dụng trường hợp , ta suy ra r x11 , y x , nên y r X (vì theo giả thiết phần tử đại diện của một trong ba tập cũng là phần tử đại diện của X, mà r x1 , y y và hai tập còn lại đều không chứa y). Do y lấy tùy ý nên r X y,  y X, y x1 . Từ đó ta có r X x1 . - Chú ý rằng khẳng định trên vẫn còn đúng với mọi tập con của S có từ 5 phần tử trở lên. + Ta có 2014 cách chọn , với mọi x1  X S thì . Xét S21 S\ x . Tương tự ta có 2013 cách chọn x22 r S , với mọi x22  X S thì r X x2 . Lặp lại tương tự quá trình này ta có 2014.2013 .5 cách chọn x1 ,x 2 ,....,x 2010 S với mỗi i 1,2,...,2010, r X xi , xi  X S\ x,x,...,x 1 2 i 1. Bây giờ còn lại 4 phần tử của S ký hiệu là Y y1 , y 2 , y 3 , y 4. Ta có 4 cách chọn rY , giả sử y1 r Y , chứng minh tương tự trên ta có ry,y 1 2 ry,y 1 3  ry,y 1 4  y 1 Còn 7 tập chưa có phần tử đại diện là 22 y,y,y123 ,y,y,y 134 ,y,y,y 124 ,y,y,y 234 , y,y2 3 ,y,y 2 4 ,y,y 3 4 , phần tử đại diện của các tập này được chọn tùy ý nên có 34.23 cách chọn. + Vậy tổng cộng có 2014.2013 .4.34.23 = 2014!.108 cách xếp phần tử đại diện cho các tập con. Bài 10. Gọi hình chữ nhật kích thước 2 3(hoặc 32 ) bị cắt bỏ một hình vuông 11 ở một góc là hình chữ nhật khuyết đơn (xem hình 1). Gọi hình chữ nhật kích thước 23 (hoặc ) bị cắt bỏ hai hình vuông ở hai góc đối diện là hình chữ nhật khuyết kép (xem hình 2). Người ta ghép một số hình vuông , một số hình chữ nhật khuyết đơn và một số hình chữ nhật khuyết kép với nhau sao cho không có hai hình nào chờm lên nhau để tạo thành một hình chữ nhật kích thước 2013 2014 . Gọi s là tổng số các hình vuông và hình chữ nhật khuyết kép cần dùng trong mỗi cách ghép hình nói trên. Tìm giá trị lớn nhất của s. x1 r S X 2012 Hình 1 Hình 2 Hình vuông 2 x 2 Hướng dẫn giải: 7
8. Tổng quát 2013 2m 1(dòng) và 2014 2n (cột) với m 1006; n 1007 gọi s là tổng số các hình vuông và hình chữ nhật khuyết kép, gọi y là số các hình chữ nhật khuyết đơn. Ta có đẳng thức về diện tích các hình: 4s 5y 2n(2m 1) Ta đánh dấu vào các ô có tọa độ (2r; 2t) với 1 r m và 1 t n ta được mn dấu . 1 2 3 4 5 6 ... 2013 2014 1 ... 2 ... 3 ... 4 ... 5 ... 22 ... ... ... ... ... ... ... ... ... ... 2012 ... 2013 ... Dễ thấy trên hình: i. Hình vuông và mỗi hình chữ nhật kép chứa đúng một dấu ii. Hình chữ nhật khuyết đơn chứa một hoặc hai dấu ta có bất đẳng thức sau về số dấu trên hình: mn s y vậy thì 5m.n 5(s y) 4s 5y s hay 5mn 2n(2m 1) s suy ra s 5m.n 2n(2m 1) mn 2n n(m 2) Áp dụng vào bài với ta được kết quả s 1011028 . Sự tồn tại của cách ghép với s 1011028 như trên hình vẽ: 8
9. 1 2 3 4 5 6 ... 1 2 1007 hình chữ 3 nhật khuyết kép 4 5 6 7 1003 x 1007 hình vuông 2 x 2 Bài 11. Cho tập X = {1 ; 2 ; ... ; 2016}. Với 3 ≤ k ≤ 2016, ta kí hiệu Fk là họ các tập con gồm k phần tử của X sao cho hai tập bất kì có chung không quá k 2 phần tử. Chứng minh tồn tại tập con Mk của X sao cho |Mk| ≥ 11 và Mk không chứa tập con nào thuộc Fk. Hướng dẫn giải: Nếu k 11 thì mọi tập k gồm 11 phần tử đều thỏa mãn. Xét k 11: Chọn K là tập con lớn nhất của X không chứa tập nào thuộc Fk . Khi đó, với mọi xX K , tồn tại AFxk sao cho Ax  K x Đặt BAxx x ta có: Bxx K, B k 1. Dễ thấy Bx đôi một khác nhau. Do đó: k1 X KC. K 9
10. k1 Đặt Km , ta có: 2016 m C10 (1). k 10 10 i 0 1 k 1 k 1 Mặt khác 2  C10 C 10 C 10 C 10 11 C 10 i0 k 1 k 1 Do đó, nếu m 10 thì 2016 m 2006 C10 C m trái với (1). Bài 12. Cho bảng hình chữ nhật kích thước m n (m n) . Một số ô có một số ngôi sao, giả sử mỗi cột có ít nhất một ngôi sao. Chứng minh rằng có ít nhất hai ngôi sao mà hàng chứa nó có nhiều ngôi sao hơn cột chứa nó. Hướng dẫn giải: N ngôi sao được đánh số từ 1 tới N Đặt aii ,b tương ứng là số ngôi sao ở cột và hàng chứa ngôi sao thứ i. Ta cần chứng minh baii với ít nhất hai chỉ số i nào đó. . Nhận xét: Nếu aki thì mọi ngôi sao cùng cột với ngôi sao thứ i có a j tương ứng là . 1 Từ đó suy ra  n ai 11 11  mn  1 baii abii 11 Suy ra tồn tại hai chỉ số i để 0 hay với hai chỉ số. abii đpcm. Bài 13. Trên đường tròn ngoại tiếp đa giác lồi 2n đỉnh (n lẻ, lớn hơn 2), ta đặt tại đỉnh thứ i số ( 1)i .i . Một phép biến đổi là thay hai số tại hai đỉnh tùy ý bởi hai số mới : số mới tăng 1 đơn vị so với số cũ nếu số cũ âm và giảm 1 đơn vị so với số cũ nếu số cũ không âm. Sau một số phép biến đổi như vậy ta có thể thu được tất cả các số tại 2n đỉnh của đa giác là các số bằng nhau không? Hướng dẫn giải: Xét đa giác A1 A 2 ...A 2n và tại đỉnh A1 ta đặt số -1, tại đỉnh A2 ta đặt số 2, , tại đỉnh thứ 2n ta đặt số 2n. Tổng tất cả các số trên đường tròn ban đầu là n (số lẻ). Xét tính chất chẵn, lẻ của tổng 2n số trên đường tròn sau mỗi phép biến đổi thì tính chất này không đổi. Thật vậy, có ba trường hợp sau 10