Tài liệu ôn thi học sinh giỏi Toán Lớp 11 - Chuyên đề: Tổ hợp (Phần 6) - Ngô Tùng Hiếu

Nội dung text: Tài liệu ôn thi học sinh giỏi Toán Lớp 11 - Chuyên đề: Tổ hợp (Phần 6) - Ngô Tùng Hiếu

1. Câu 1. Trên mặt phẳng có 25 điểm, không có 3 điểm nào trong chúng thẳng hàng. Tìm số màu k nhỏ nhất sao cho ta có thể tô màu tất cả các đoạn thẳng nối hai điểm trong mặt phẳng bởi k màu ( mỗi đoạn thẳng được tô đúng một màu) và các cạnh của một tam giác bất kì tạo bởi 3 điểm trong chúng được tô bởi đúng hai màu. Hướng dẫn giải Dùng định lí Ramsey chứng minh được: Tô màu các cạnh của đồ thị 퐾17( đồ thị đầy đủ 17 đỉnh) bằng 3 màu một cách tùy ý thì luôn có một 퐾3có ba cạnh cùng màu. ( trong các cuốn sách về đồ thị đều trình bày chứng minh, học sinh phải chứng minh lại). Khi đó ≥ 4. Ta đi chứng minh: bằng 4 màu ta có thể tô được các cạnh của 퐾25 thỏa mãn bài ra. Thật vậy, chia 25 điểm thành 5 tập hợp 5 điểm 1, 5. Trong mỗi 푖 lấy các đỉnh trên một ngũ giác đều. Cạnh của ngũ giác con này tô màu 1 và các đường chéo của nó tô màu 2. Sau đó mỗi tập hợp 푖coi là đỉnh một ngũ giác và thực hiện việc tô màu nối các đoạn thẳng của các nhóm 푖, 푗cũng theo cách tương tự với 2 màu còn lại. Ta đi chứng minh cách tô màu này thỏa mãn bài toán Câu 2. Tìm số các hoán vị (a 1, a2, , a2009) của (1, 2, 3, , 2009) thỏa mãn tính chất: tồn tại đúng một chỉ số i 1,2,3, ,2008 sao cho ai > ai+1. Hướng dẫn giải Câu 3. Cho một bảng ô vuông có 100 100 ô vuông , mỗi ô đều điền một dấu + . Ta thực hiện phép biến đổi như sau: đổi dấu toàn bộ một hàng hoặc một cột của bảng ( dấu + thành dấu - , dấu - thành dấu +). Hỏi sau một số lần thực hiện phép biến đổi như trên thì bảng có thể có đúng 98 dấu - được không? Hướng dẫn giải Giả sử sau một số lần biến đổi bảng có đúng 98 dấu - Gọi xi là số lần đổi dấu ở hàng thứ i ( i = 1, 2 ,100 , tính từ trên xuống) Gọi yj là số lần đổi dấu ở cột thứ j ( j = 1, 2 ,100 , tính từ trái sang phải) Gọi m là các số lẻ trong các số x1; x2 ; ; x100 và n là các số lẻ trong các số y1; y2 ; ; y100 . Ta có m , n 0,1,2 100 Ta có số lượng các dấu - trên bảng là m(100-n) + n( 100-m) = 100m +100n - 2mm Bảng có đúng 98 dấu - nên ta có 100m +100n - 2mm = 98 m 50 (n 50) 502 72 m 50 n 50 43.57 (*) m 50 n 50 57 mà 57 là số nguyên tố nên m-50  57 hoặc n-50  57 Ta có m-50 , n-50 50; 49; ;49;50 nên m-50 = 0 hoặc n-50 = 0 mâu thuẫn với (*). Vậy bảng không thể có đúng 98 dấu - Câu 4. Một ngân hàng câu hỏi Toán có 30 câu hỏi khác nhau gồm: 5 câu hỏi khó, 10 câu hỏi trung bình và 15 câu hỏi dễ. Từ ngân hàng này lập một đề thi gồm 5 câu hỏi khác nhau. Tính xác suất để sao cho trong mỗi đề được chọn nhất thiết phải có đủ cả 3 loại câu hỏi (khó, trung bình, dễ) và số câu hỏi dễ không ít hơn 2? Hướng dẫn giải Số đề thi thỏa mãn yêu cầu bài toán là: 56875. Tổng số đề thi có thể có là: 142506. 625 Xác suất cần tìm là: P . 1566
2. Câu 5. 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) (1 điểm) 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 3Sn 1 4Sn 2 n 4 Sử dụng phương pháp sai phân để tính Sn . Xét phương trình đặc trưng: x2 3x 4 0 x 1 x 4 S a( 1)n b4n n Do S2 5.4 20, S3 5.4.3 60 Ta có: a 16b 20 a 4 a 64b 60 b 1 Vậy S 4 1 n 4n S 4 410 n 10 Câu 6. Điền 29 số nguyên dương đầu tiên vào các ô vuông con của bảng 6 x 5 bằng cách sau: Cho phép thay đổi vị trí của các số trong bảng theo quy tắc: Mỗi lần, lấy một số nằm ở ô kề với ô trống rồi chuyển số đó sang ô trống. Hỏi bằng cách thực hiện liên tiếp một số hữu hạn lần phép chuyển số nói trên đối với bảng số ban đầu ta có thể nhận được bảng số sau đó hay không? 1 2 3 4 5 29 2 3 4 5 6 7 8 9 10 6 7 8 9 10 11 12 13 14 11 12 13 14 15 16 17 18 19 20 21 22 23 24 15 16 17 18 19 25 26 27 28 1 20 21 22 23 24 25 26Bảng27 1 28 29 Hướng dẫn giải Bảng 2 Giả sử nhờ phép chuyển số theo qui tắc của đề bài, từ Bảng 1 ta có thể nhận được Bảng 2 (*) Ta coi ô trống của mỗi bảng là ô được điển số 0. Với mỗi bảng số nhận được trong quá trình chuyển số, ta liệt kê tất cả các số trong bảng theo thứ tự từ hàng trên xuống hàng dưới và trong mỗi hàng thì từ trái qua phải. Khi đó ứng với mỗi bảng số ta sẽ có một hoán vị của 30 số tự nhiên đầu tiên. Và do đó, điều giả sử (*) tương đương với: Từ hoán vị (1, 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11, 12, 0, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29) (gọi là hoán vị a) có thể nhận được hoán vị (29, 2, 3, 4, ,11. 12, 0, 13, 14, 15, 27, 28, 1) (gọi là hoán vị b)
3. nhờ việc thực hiện liên tiếp một số hữu hạn lần phép đổi chỗ hai số trong hoán vị theo qui tắc: Mỗi lần, lấy hai số 0 của hoán vị rồi đổi vị trí của số 0 đó cho một số liền kề với số 0 đó. (1) +) Giả sử (a1, a2, a3, , a30) là một hoán vị của 30 số tự nhiên đầu tiên. Ta gọi cặp số ai ;a j là cặp số ngược của hoán vị vừa nêu nếu ai a j và i j . Dễ thấy, sau một lần thực hiện phép đổi chỗ hai số kề nhau đối với hoán vị (a1, a2, a3, , a30) thì số cặp số ngược của hoán vị đó sẽ tăng hoặc giảm đi một đơn vị. ai +) Khi chuyển chỗ hai số ai và ai n ( n 1 tùy ý) trong một hoán vị, cũng tức là chuyển liên a tiếp qua n số kề với nó và chuyển i n liên tiếp qua n – 1 số kề với nó, nghĩa là chuyển 2n – 1 (một số lẻ lần) hai số kề nhau, do đó cặp số ngược của hoán vị đó sẽ tăng hoặc giảm một số lẻ đơn vị. (2) +) Ta có: Số cặp số ngược của của hoán vị a là 12 và số cặp số ngược của hoán vị b là 67. Từ đó, kết hợp với (2), suy ra từ hoán vị a ta chỉ có thể nhận được hoán vị b sau một số lẻ lần thực hiện phép đổi chỗ hai số nào đó. Điều này cho thấy, nếu từ Bảng 1 ta nhận được Bảng 2 thì số lần đổi chỗ hai số ở hai ô nào đó phải là số lẻ. (3) +) Tô màu tất cả các ô vuông con của bảng 6 x 5 bởi hai màu xanh, đỏ sao cho hai ô kề nhau có màu khác nhau. Sau mỗi lần đổi chỗ hai số ở hai ô kề nhau, trong đó có số 0 ở ô trống, theo cột hay theo hàng thì số 0 được chuyển từ ô có màu này sang ô có màu kia. Và vì thế do số 0 ở bảng 1 và số 0 ở bảng 2 nằm ở hai ô cùng màu nên từ bảng 1 ta chỉ nhận được bảng 2 sau một số chẵn lần đổi chỗ hai số ở hai ô kề nhau, trong đó có số 0. Điều này mâu thuẫn với (3) và mâu thuẫn đó cho thấy: Từ Bảng 1 ta không thể nhận được Bảng 2 nhờ một số hữu hạn lần đổi chỗ ở hai ô kề nhau, trong đó có số 0 ở ô trống, theo quy Câu 7. Cho bộ số 1;2;3 . 1) Chúng ta thực hiện phép biến đổi trên các bộ 3 số như sau: thay hai số trong chúng, ví dụ a và b, bởi a b và a b . Hỏi có thể nhận được bộ số sau: a1;b1;c1 thỏa mãn a1 b1 c1 10 sau khi thực hiện hữu hạn phép biến đổi từ bộ số ban đầu 1;2;3 ? 2) Nếu chúng ta thực hiện phép biến đổi trên các bộ 3 số như sau: thay hai số trong chúng, ví a b a b dụ a và b, bởi và . Hỏi có thể nhận được bộ số 28;4;2014 sau khi thực hiện 2 2 hữu hạn phép biến đổi từ bộ số ban đầu 1;2;3 Hướng dẫn giải Ta thực hiện theo cấu hình sau 1;2;3 3; 1;3 3;2; 4 3;2; 4 7;2; 1 a1;b1;c1 Dễ thấy: a1 b1 c1 10 Trong mọi cấu hình ta luôn có: Tổng bình phương các số là không đổi Lại có: 12 22 32 282 42 20142 Vậy câu trả lời là phủ định. Ta có: 23 1  3 m Ta chỉ ra rằng với mọi số nguyên dương m , ta có: 23 1  3m Với m 1, khẳng định đúng.
4. Giả sử khẳng định đúng với m nguyên dương nào đó, tức là tồn tại k nguyên dương sao cho m 23 k.3m 1. Ta có: m 1 3 23 3m.k 1 33m.k3 32m 1.k2 3m 1.k 1 3m 1.t 1 với t là một số nguyên dương nào đó. Như vậy, khẳng định được chứng minh Câu 8. Mỗi điểm trong mặt phẳng được tô bằng một trong hai màu xanh hoặc đỏ. Chứng minh rằng luôn tồn tại một tam giác mà ba đỉnh và trọng tâm cùng màu. Hướng dẫn giải Lấy 5 điểm tùy ý sao cho không có 3 điểm nào thẳng hàng trong mặt phẳng. Khi đó vì chỉ dùng hai màu để tô các điểm nên theo nguyên lý Dirichlet phải tồn tại ba điểm trong số đó cùng màu. Giả sử đó là 3 điểm A, B, C màu đỏ. Gọi G là trọng tâm tam giác ABC. Nếu G có màu đỏ thì ta được tam giác có 3 đỉnh và trọng tâm màu đỏ. Nếu G có màu xanh. Kéo dài GA, GB, GC các đoạn AA', BB', CC' sao cho AA'=3GA, BB'=3GB, CC'=3GC. Gọi M, N, P tương ứng trung điểm BC, CA, AB thì AA'=3GA=6GM, suy ra AA'=2AM. Tương tự BB'=2BN, CC'=2CP. Do đó tam giác A'BC, B'CA, C'AB tương ứng nhận A, B, C làm trọng tâm. Mặt khác ta cũng có tam giác ABC, A'B'C' có cùng trọng tâm G. Có hai trường hợp có thể xảy ra a) Nếu A', B', C' có cùng màu xanh, khi đó tam giác A'B'C' và trọng tâm G có màu xanh. b) Nếu ít nhất một trong các điểm A', B', C' màu đỏ. Không giảm tổng quát, giả sử A' đỏ. Khi đó tam giác A'BC và trọng tâm A có màu đỏ. A' A P N G C M B C' B' Câu 9. Các số nguyên dương 1,2,3, ,2014 được sắp xếp trên một hàng theo một thứ tự nào đó. Ta thực hiện quy tắc đổi chỗ các số như sau: nếu số đầu tiên là k thì ta đổi k số đầu tiên theo thứ tự ngược lại. Chứng minh rằng sau một số hữu hạn lần thực hiện quy tắc trên thì số 1 sẽ xuất hiện ở vị trí đầu tiên. Hướng dẫn giải
5. Giả sử k,1 k 2014 là số lớn nhất xuất hiện ở vị trí đầu tiên trong tất cả các quá trình đổi chỗ. Giả sử số k xuất hiện ở lần thứ h. Khi đó ở lần thực hiện sau lần thứ h thì số k sẽ giữ nguyên vị trí. Trong các quá trình đổi chỗ sau đó ta gọi k1 là số lớn nhất xuất hiện ở vị trí đầu tiên. Giả sử số k1 xuất hiện ở lần thứ h1 . Khi đó sau lần thứ h1 thì số k1 sẽ giữ nguyên vị trí, cứ tiếp tục như vậy thì sau một số hữu hạn bước phải dừng lại. Khi không thực hiện việc thực hiện quy tắc đổi chỗ của bài toán tức là số ở vị trí đầu tiên sẽ là số 1. Bài toán được chứng minh Câu 10. Trong một cuộc hội nghị, mỗi đại biểu bắt tay ít nhất 6 đại biểu khác. Người ta đếm được tất cả 97 lần bắt tay. Hỏi hội nghị đó có tối đa bao nhiêu đại biểu. Hướng dẫn giải Gọi n là số đại biểu. Ta xây dựng đồ thị G với đỉnh là các đại biểu, còn hai đỉnh bất kỳ được nối với nhau bằng cạnh khi và chỉ khi hai đại biểu tương ứng của hai đỉnh đó bắt tay với nhau. Khi đó đồ thị G có 97 cạnh. Theo bổ đề bắt tay, trong một đồ thị, tổng số bậc của các đỉnh bằng hai lần số cạnh, do đó 97x2 6n n 32 Vậy hội nghị có tối đa 32 đại biểu. Câu 11. Gọi a1a2 an với ai 2;0 là một xâu có độ dài n. Gọi xâu 20 là xâu OLIMPIC nếu 2 và 0 là hai phần tử liên tiếp theo thứ tự đó ở trong xâu có độ dài n đã cho ( ví dụ như xâu 2220022 có độ dài là 7 và trong đó có 1 xâu OLIMPIC). Xét các 9 xâu có độ dài 30 và chứa k xâu OLIMPIC, biết rằng có C31 xâu như thế. Tìm k? Hướng dẫn giải Gọi H là số là xâu chứa toàn là số 2 có độ dài lớn hơn hay bằng 1 Gọi K là số là xâu chứa toàn là số 0 có độ dài lớn hơn hay bằng 1. Ta có các trường hợp sau: Trường hợp 1. HKHKHK HK (*) ( có k xâu loại H, k xâu loại K) Trường hợp 2. HKHKHK HKH ( có k+ 1 xâu loại H, k xâu loại K) Trường hợp 3. KHKHK KHK ( có k xâu loại H, k+1 xâu loại K) Trường hợp 4. KHKHK KHKH( có k+1 xâu loại H, k+1 xâu loại K) Xét trường hợp 1. Gọi x1 là số phần tử ở xâu H ( H ở vị trí đầu tiên trong (*)) , x1 1 Gọi x2 là số phần tử ở xâu K ( K ở vị trí thứ hai trong (*)) , x2 1. Gọi x2k là số phần tử ở xâu K ( K ở vị trí cuối trong (*)) , x2k 1 Ta có : x1 x2 x2k 30 . Theo bài toán chia kẹo Euler : Số xâu có độ dài 30 và chứa k xâu OLIMPIC trong trường hợp 1 2k 1 là C29 . Tương tự như vậy ta có các trường hợp còn lại và kết hợp với quy tắc cộng ta có : 2k 1 2k 2k 2k 1 9 C29 C29 C29 C29 C31 2k 1 9 9 2k 1 C31 C31 k 4 9 31 (2k 1) Vậy k=4. Câu 12. Cho khai triển:
6. 2 3 2010 2011 2 3 4042110 (1 x x x x ) a0 a1x a2 x a3 x a4042110 x . Tính tổng a0 a2 a4 a4042110 . Hướng dẫn giải Thay x=1 Câu 13. Từ các chữ số 0,1,2,3,4,5 lập các số tự nhiên có ba chữ số đôi một khác nhau. Lấy ngẫu nhiên một số vừa lập. Tính xác suất để lấy được số không chia hết cho 3. Hướng dẫn giải Từ các chữ số 0,1,2,3,4,5 lập các số có ba chữ số đôi một khác nhau. Lấy ngẫu nhiên một số vừa lập. Tính xác suất để lấy được số không chia hết cho 3. + Tìm số có ba chữ số khác nhau lập được từ tập E 0,1,2,3,4,5 Số cần tìm có dạng abc . Chọn a E, a 0 có 5 cách. 2 Chọn 2 trong 5 số còn lại của E \ a xếp vào hai vị trí b, c có A5 cách. 2 Vậy có 5.A5 100 (số) + Tính số lập được chia hết cho 3. Số cần tìm có dạng abc , a b c3 Xét các tập con gồm 3 phần tử của tập E 0,1,2,3,4,5 , ta thấy chỉ có các tập sau thoả mãn điều kiện tổng các chữ số chia hết cho 3 là: A1 0,1,2 , A2 0,1,5 ,A3 0,2,4 ,A4 0,4,5 A5 1,2,3,A6 1,3,5 , A7 2,3,4 , A8 3,4,5 Khi a,b,c A1, A2 , A3 , A4 mỗi trường hợp lập được 4 số thoả mãn yêu cầu. Khi a,b,c A5; A6 ; A7 ; A8 mỗi trường hợp lập được 6 số thoả mãn yêu cầu. Vậy có 4.4 4.6 40(số) Suy ra số không chia hết cho 3 là100 40 60 (số) 60 Xác suất cần tính là P 0,6 . 100 Câu 14. Tìm tất cả các số tự nhiên n sao cho trong mặt phẳng tồn tại n đường thẳng mà mổi đường thẳng cắt đúng 2014 đường khác Hướng dẫn giải Xét n đường trong mặt phẳng, mà mổi đường thẳng cắt đúng 2014 đường khác Nếu a là một đường thẳng trong n đường và có đúng k đường song song với nó (0 ≤ k Số giao điểm của mỗi đường với các đường khác là (k+1)(S 1) = 2014 Mà 2014 = 2.19.53 và k + 1 là ước nguyên dương của 2014 => k + 1 {1; 2; 19; 53; 38; 106; 1007; 2014} n = (k + 1)S = 2014 + (k + 1) => n {2015; 2016; 2033; 2067; 2120; 2510; 3021; 4028} Câu 15. Với mỗi số nguyên dương m, kí hiệu C(m) là số nguyên dương k lớn nhất sao cho luôn tồn tại một tâp S gồm m số nguyên dương để mỗi số nguyên chạy từ 1 đến k hoặc thuộc S hoặc là tổng
7. hai phần tử thuộc S (hai phần tử này không nhất thiết phân biệt). Chứng minh: m(m 6) m(m 3) C(m) 4 2 Hướng dẫn giải Trước tiên ta tính thử một vài giá trị ban đầu của C(m) để cảm nhận bài toán. Dễ thấy: C(1)=2; C(2)=4; C(3)=8 Nhận xét: Việc tính C(m) quy về việc đếm số phần tử của tập A xác định bởi: A S  (S S) ; S S x y | x, y S m(m 3) C(m) +) Chứng minh: 2 2 | S | (| S | 3) m(m 3) | A | | S | | S S | | S | | S | C|S| 2 2 Chú ý : Để đánh giá số phần tử của tập S+S ta chia hai trường hợp x trùng y và x khác y. Rõ ràng {1;2;3; ;k} là một tập con của A nên ta được đpcm. m(m 6) C(m) +) Chứng minh: 4 Ta sẽ chỉ ra một tập B sao cho với mọi số nguyên chạy từ 1 đến m(m+6)/4 hoặc thuộc B hoặc là tổng hai số (không nhất thiết phân biệt) thuộc S(m). Khi đó C(m)>=m(m+6)/4. Xét hai trường hợp sau: TH1: m = 2n. Xét tập B(m) = {1; 2; 3; ; n; 2n+1; 3n+2; ; (n+1)n+n} gồm m phần tử và dễ thấy tập B  (B B) chứa dãy số liên tiếp từ 1 đến (n+1)n + 2n và rõ ràng (n+1)n + 2n = 2n(2n+6)/4 TH2: m = 2n+1 Khi đó ta xây dựng tập B(m)={1;2;3; ; n+1;2n+3;3n+5; ;(n+1)n+2n+1}gồm m phần tử và tập B  (B B) chứa dãy số liên tiếp từ 1 đến (n+1)n+3n+2 và rõ ràng (n+1)n+3n+2 > (2n+1)(2n+7)/4 Từ hai TH trên ta được đpcm. Câu 16. Gọi X là tập hợp các số tự nhiên gồm sáu chữ số đôi một khác nhau được tạo thành từ các chữ số 1, 2, 3, 4, 5, 6, 7, 8, 9. Chọn ngẫu nhiên một số từ tập hợp X. Tính xác suất để số được chọn chứa đúng ba chữ số lẻ. Hướng dẫn giải Gọi X là tập hợp các số tự nhiên gồm sáu chữ số đôi một khác nhau được tạo thành từ các chữ số 1, 2, 3, 4, 5, 6, 7, 8, 9. Chọn ngẫu nhiên một số từ tập hợp X. Tính xác suất để số được chọn chứa đúng ba chữ số lẻ. 6 Số phần tử không gian mẫu: n  A9 Gọi A là biến cố số được có đúng ba chữ số lẻ. 3 Ta có: Số cách chọn 3 chữ số lẻ từ 1,3,5,7,9 là C5 3 Số cách chọn 3 chữ số chẵn từ 2,4,6,8 là C4 Số các số có 6 chữ số được lập từ 6 chữ số trên là: 6! 3 3 Từ đó suy ra: n A C5 .C4 .6! 3 3 n A C5 .C4 .6! 30 Vậy xác suất biến cố A là: P A 6 n  A9 63 Câu 17. Quần đảo Hoàng Sa có 3 loài chim bồ câu đang sinh sống, mỗi loài mang một màu sắc khác nhau , loài màu xám có 133 con, loài màu nâu 155 con và loài màu xanh có 177 con. Giả sử
8. cứhai con bồ câu khác màu gặp nhau thì chúng đồng thời đổi sang màu thứ ba và hai con bồ câu cùng màu gặp nhau thì chúng giữ nguyên không đổi màu. Có xảy ra tình trạng tất cả loài chim bồ câu đang sống trên đảo trở thành cùng một màu hay không? Hướng dẫn giải Khi chia các số 133; 155; 177 cho 3 được lần lượt các số dư là:1; 2; 0 Ta xét: Nếu 1 con bồ câu xám gặp 1 con bồ câu nâu, thì chúng đồng thời đổi thành màu xanh. Khi đó ta có 132 con xám, 154 con nâu, và 179 con xanh. Những số dư của 132; 154; 179 cho 3 tương ứng là 0;1 và 2, nghĩa là lại gặp lại đầy đủ các số dư đã có. Nếu 1 con bồ câu xám gặp con bồ câu màu xanh thì chúng đồng thời đổi sang màu nâu. Khi đó ta có 132 con bồ câu xám, 157 con bồ câu nâu, và 176 con bồ câu xanh. Lấy những số trên chia cho 3 cho số dư tương ứng là 0,1 và 2, nghĩa là lại gặp cả 3 khả năng của số dư. Nếu bồ câu nâu và bồ câu xanh gặp nhau, thì chúng cùng đổi thành màu xám. Khi đó có 135 con bồ câu xám, 154 con ồ câu nâu và 176 con ồ câu xanh. Số dư củ những con bồ câu trên chia cho 3 tương ứng là 0,1và 2, vẫn có đầy đủ các số dư khi chia cho 3 Bất biến ở đây là dù thay đổi mầu như thế nào thì số dư của các sô lượng bồ câu chia cho 3 đều có đầy đủ 0,1,2. Số lượng tất cả thằn lằn trên đảo là 133+ 155+ 177= 465 là một số chia hết cho 3. Nếu tất cả các con bồ câu đều cùng một màu thì số dư của số lượng bồ câu màu xám, nâu và đỏ chia cho 3 tương ứng là 0,0,0. Điều này vô lý vì các số dư phải có đầy đủ các số dư này khi chia cho 3. Như vậy câu trả lời là không thể được. Câu 18. Từ các chữ số 1, 2, 3, 4, 5, 6, 7, 8, 9 có thể lập được bao nhiêu số có 6 chữ số khác nhau trong đó có ba chữ số chẵn và ba chữ số lẻ. Trong các số trên có bao nhiêu số mà các chữ số được sắp xếp theo thứ tự tăng dần. Hướng dẫn giải Có 5 số lẻ và 4 số chẵn từ chín số 1, 2, 3, 4, 5, 6, 7, 8, 9 3 Suy ra có C5 cách chọn 3 số lẻ từ năm số 1, 3, 5, 7, 9 3 và có C4 cách chọn 3 số chẵn từ bốn số 2, 4, 6, 8 Cứ ba chữ số lẻ ghép với ba chữ số chẵn ta được một tập gồm 6 phần tử. Theo quy tắc nhân có 3 3 C4 .C5 cách chọn các tập hợp mà mỗi tập có 3 số chẵn và 3 số lẻ từ các số trên Ứng với mỗi tập có 6! cách sắp xếp thứ tự các phần tử và mỗi cách sắp xếp thứ tự đó ta được một số thỏa mãn bài toán 3 3 Do đó theo quy tắc nhân có C4 .C5 .6! = 28800 số có 6 chữ số khác nhau gồm 3 chữ số chẵn và 3 chữ số lẻ từ các số trên. 3 3 * Có C4 .C5 tập hợp gồm ba chữ số lẻ và ba chữ số chẵn. Ứng với mỗi tập có duy nhất một cách sắp xếp các phần tử theo thứ tự tăng dần 3 3 Do đó mỗi tập hợp tương ứng với một số. Vậy có C4 .C5 = 40 số thỏa mãn Câu 19. Có 1000 học sinh gồm 499 học sinh nam và 501 học sinh nữ được xếp thành 10 hàng dọc, mỗi hàng 100 học sinh. Người ta muốn chọn từ 1000 học sinh này ra một nhóm 4 học sinh, trong đó số học sinh nữ được chọn là lẻ và thoả mãn điều kiện sau đây: 4 học sinh này được chọn từ 2 hàng khác nhau và có 2 cặp học sinh có cùng thứ tự đứng trong hàng (tính từ người đứng đầu tiên của hàng đó). Chứng minh rằng số cách chọn các nhóm như vậy là một số lẻ. Hướng dẫn giải Gọi mỗi nhóm 4 học sinh lấy từ hai hàng thỏa mãn yêu cầu bài toán là một đội. Đặt S = { | là một đội}, O = { S|  có số lẻ học sinh nữ}, E = { S|  có số chẵn học sinh nữ}. Ta cần chứng minh rằng | O | là lẻ.
9. Với mỗi tập con A của S, ta định nghĩa f (A)  g( ), trong đó g() là số học sinh nữ  A của . Vì OE =  và OE = S nên f (S) f (O) f (E) . Hơn nữa f (E) là chẵn, suy ra f (S)  f (O) (mod 2) . Mặt khác, xét một học sinh nữ bất kì. Để tạo thành một đội, học sinh này có thể bắt cặp với một học sinh khác trong hàng bởi 99 cách, sau đó tìm 2 học sinh khác ở hàng khác bởi 9 cách. Suy ra, học sinh nữ này là thành viên của 99.9 = 891 đội. Có nghĩa là học sinh nữ này được tính 891 lần trong f (S) . Vì ta có 501 học sinh nữ nên f (S)  891.501 1 (mod 2) . Vì mỗi  O chứa một số số lẻ các học sinh nữ nên f (O) | O | (mod 2) . Suy ra | O | f (O)  f (S) 1 (mod 2) . Như vậy số cách chọn những đội là một số lẻ Câu 20. Trên mặt phẳng, kẻ vô hạn các ô vuông (dạng bàn cờ) và mỗi ô vuông được điền một trong hai số 0 hoặc 1 sao cho bất cứ hình chữ nhật nào có kích thước 2x3 thì có đúng hai ô điền số 1. Xét một hình chữ nhật bất kì có kích thước 2016x2017. Tính tổng các số có trong các ô của nó. Hướng dẫn giải Thật vậy, giả sử tồn tại hình chữ nhật có kích thước 1x3 có số ô có số 1 khác 1. Không mất tính tổng quát ta giả sử đó là hình chữ nhật AKHD kích thước 1x3 có đúng hai ô điền số 1 (nếu không thì không có ô nào chứa số 1 nhưng không thể là ba ô điền số 1 vì trong mọi hình chữ nhật có kich thước 2x3 có đúng 2 ô điền số 1). Có thể cho coi hai ô chứa số 1 của AKHD là ô 7 và ô 8 (Nếu ở các ô khác thì lập luận tương tự). Xét hình chữ nhật BFNA có kích thước 2x3 nó có đúng hai ô chứa số 1 các ô 1,2,4,5 là các ô điền số 0. Xét hình chữ nhật BCHK, từ giả thiết và do các ô 1,2,4,5 đều điền số 0 nên các ô 3,6 phải điền số 1. Xét hình chữ nhật ECDM kích thước 2x3, ta thấy do ô 3,6,8 điền số 1 nên dẫn đến mâu thuẫn. Trường hợp AKHD không có ô nào điền số 1, lập luận tương tự ta cũng dẫn đến mâu thuẫn. Vậy giả thiết phản chứng là sai hay ta có điều phải chứng minh. Vì 2016=3x672 nên hình chữ nhật kich thước 2016x2017 chia thành 672x2017 hình chữ nhật có kích thước 1x3. Vậy tổng các số điền trong ô của hình chữ nhật này là: 672.2017=1355424. Câu 21. Tô các số từ 1 đến 2017 bằng các màu khác nhau sao cho không có hai số nào cùng màu chia hết cho nhau. Cần ít nhất bao nhiêu màu ?
10. Hướng dẫn giải Thật vậy, với 11 màu khác nhau mà ta gọi là màu 1, màu 2, , màu 11, xét cách tô màu sau: Số 1 tô màu 1 Các số 2 và 3 tô màu 2 Các số từ 4 đến 7 tô màu 3 Các số từ 8 đến 15 tô màu 4 Các số từ 16 đến 31 tô màu 5 Các số từ 32 đến 63 tô màu 6 Các số từ 64 đến 127 tô màu 7 Các số từ 128 đến 255 tô màu 8 Các số từ 256 đến 511 tô màu 9 Các số từ 512 đến 1023 tô màu 10 Các số từ 1024 đến 2017 tô màu 11. Dễ thấy cách tô màu trên thỏa mãn không có hai số nào cùng màu chia hết cho nhau. Vậy cần ít nhất 11 màu. Câu 22. Từ các chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự nhiên mà trong mỗi số nầy các chữ số không lặp lại. Hướng dẫn giải Đếm các số tự nhiên có 1 chữ số, 2 chữ số, ,7 chữ số rồi tìm tổng. Câu 23. Cho m,n 3là hai số nguyên dương. Trong bảng kích thước m n có dán k ngôi sao (mỗi ô có nhiều nhất là một ngôi sao). Ta thực hiện một công việc là nếu có một hình 2 3 hoặc 3 2 mà có 5 ngôi sao thì ta sẽ dán thêm một ngôi sao vào ô còn lại. Tìm giá trị nhỏ nhất của k sao cho ban đầu trong bảng có k ngôi sao thì sau hữu hạn bước thực hiện việc dán thêm sao như trên thì mọi ô trong bảng đều có ngôi sao. Hướng dẫn giải Ta chứng minh giá trị nhỏ nhất của k là m+n. Sau mỗi một lần thực hiện thuật toán thì ít nhất một hình 2 2với 4 ngôi sao được hình thành. Nếu ban đầu không có hình 2 2 nào với 4 ngôi sao thì sau bước thực hiện sẽ có ít nhất hai hình 2 2 với đầy đủ 4 ngôi sao được hình thành. Do đó sau mn-k bước thực hiện sẽ có ít nhất mn-k+1 hình 2 2 với 4 ngôi sao được hình thành hoặc ít nhất có 1 hình 2 2 với 4 ngôi sao đã có ban đầu và mn-k hình 2 2 có đủ 4 sao được hình thành. Mặt khác, tồn tại đúng (m-1)(n-1) hình 2 2 ở trong bảng, do đó m 1 n 1 mn k 1 Từ đó k m n . Hình vẽ sau đây chỉ ra một ví dụ k= m+n * * * * * * * * * * Câu 24. Trên bàn cờ 10 x 10 người ta viết các số từ 1 đến 100. Mỗi hàng chọn ra số lớn thứ ba. Chứng minh rằng tồn tại một hàng có tổng các số trong hàng đó nhỏ hơn tổng các số lớn thứ ba được chọn. Hướng dẫn giải
11. Sắp xếp thứ tự của 10 số lớn thứ ba của các hàng là a1 a2 a10. Ta thấy tối đa là 20 số có thể lớn hơn a1 (là các số lớn thứ nhất và thứ hai ở mỗi hàng). Vì vậy a1 80. Tương tự có tối đa 28 số có thể lớn hơn a2 . Vì vậy a2 72. Từ đó a1 a2 a10 80 72 a10 7 a10 6 a10 8a10 180. Trong khi đó, tổng các số ở hàng chứa a10 không lớn hơn 100 99 a10 a10 1 a10 7 8a10 171. Do 8a10 171 8a10 180 nên hàng chứa a10 là hàng thỏa mãn yêu cầu. Câu 25. Một ngân hàng câu hỏi Toán có 30 câu hỏi khác nhau gồm: 5 câu hỏi khó, 10 câu hỏi trung bình và 15 câu hỏi dễ. Từ ngân hàng này lập một đề thi gồm 5 câu hỏi khác nhau. Tính xác suất để sao cho trong mỗi đề được chọn nhất thiết phải có đủ cả 3 loại câu hỏi (khó, trung bình, dễ) và số câu hỏi dễ không ít hơn 2? Hướng dẫn giải Số đề thi thỏa mãn yêu cầu bài toán là: 56875. Tổng số đề thi có thể có là: 142506. 625 Xác suất cần tìm là: P . 1566 Câu 26. Cho 100 số tự nhiên không lớn hơn 100 có tổng bằng 200. Chứng minh rằng từ các số đó có thể chọn được ít nhất một bộ các số có tổng bằng 100. Hướng dẫn giải Câu 27. Một túi đựng 11 viên bi cùng kích thước nhưng khác nhau về màu sắc gồm: 4 viên bi xanh, 7 viên bi đỏ. Lấy ngẫu nhiên 2 viên. tính xác suất để: a. Lấy được 2 viên bi cùng màu. b. Lấy được 2 viên bi khác màu. Hướng dẫn giải Mỗi cách lấy ngẫu nhiên 2 viên bi từ 11 viên bi là một tổ hợp chập 2 của 11 viên bi. Do đó : N( 2  ) = C11 2 Gọi A là biến cố lấy được 2 viên bi xanh, B là biến cố lấy được 2 viên bi đỏ thì N(A) = C4 và 2 N(B) = C7 . 2 2 C4 6 C7 21 Do đó : P(A) = 2 , P(B) = 2 C11 55 C11 55 Biến cố lấy được 2 viên bi cùng màu là C = A  B , vì A, B là 2 biến cố xung khắc nên: P(C) 27 = P(A  B) P(A) P(B) 55 b) Biến cố lấy được 2 viên bi khác màu là C . 27 28 Từ đó ta có: P(C) 1 P(C) 1 55 55 Câu 28. Có bao nhiêu cách phân tích 69 thành tích của 3 số nguyên dương, biêt các cách phân tích mà các nhân tử chỉ khác nhau về thứ tự thì chỉ được tính 1 lần? Hướng dẫn giải Có bao nhiêu cách phân tích 69 thành tích của 3 số nguyên dương, biêt các cách phân tích mà các nhân tử chỉ khác nhau về thứ tự thì chỉ được tính 1 lần?
12. 푖 , 푖 ∈ 9 Xét phân tích 6 = (2 1.3 1)(2 2.3 2)(2 3.3 3) với 1 + 2 + 3 = 9 1 + 2 + 3 = 9 Với mỗi 1 ∈ , 0 ≤ 1 ≤ 9, có 10 ― 1 cách chọn số 2, để 1 + 2 ≤ 9 từ đó chọn a3 = 9 ― a1 ― a2. (1 điểm) Vậy số cách chọn các bộ ( 1, 2, 3) là 10+9+ +1 = 55 cách số cách chọn các bộ ( 1, 2, 3) và ( 1, 2, 3) là 55.55 cách. Bây giờ, ta sẽ tính số các cách phân tích bị trùng nhau. +) TH1: 3 thừa số bằng nhau: 69 = (23.33)(23.33)(23.33) (1 điểm) +) TH2: 2 thừa số bằng nhau: 69 = (2 .3 )(2 .3 )(29―2 .39―2 ) và (a ; b) # (3 ; 3). Khi đó a ∈ {0; 1; 2; 3; 4} ; b ∈ {0; 1; 2; 3; 4 } và (a ; b) # (3 ; 3) → số cặp (a; b) là 5.5 – 1 =24, và 24 cặp này cho ta 24 cách phân tích thỏa mãn yêu cầu. Tuy nhiên, mỗi cặp sẽ cho 3 lần đếm trong quá trình đếm mà ta vừa nêu ở trên. (1 điểm) +) TH3: nếu cả 3 thừa số khác nhau, thì mỗi phân tích bị đếm trùng 3!=6 lần. Vậy số cách phân tích là: 1 + 24 + (55 × 55 ― 24 × 3 ― 1):6 = 517 cách (1 điểm) Người làm đề: Nguyễn Mạnh Cường Sđt: 0169.534.8888. Trong đề không có câu 2 - về dãy số, vì tôi không nghiên cứu được câu nào mới và phù hợp Câu 29. Hội khỏe Phù Đổng năm 2014 có tổ chức thi đấu 4 môn thể thao chạy 100m, nhẩy xa, nhẩy cao, bắn cung và quy định điều kiện cho mỗi đội tham gia như sau: Mỗi vận động viên của một đội chỉ thi đấu duy nhất một môn thể thao. Mỗi đội có thể lựa chọn số vận động viên cho mỗi môn tùy ý (nhưng tổng số vận động viên đúng bằng 20). Tại lễ khai mạc, mỗi đội xếp thành một hàng dọc, các vận động viên chạy 100m cầm cờ đỏ đứng đầu, tiếp theo đến vận động viên nhảy xa cầm cờ vàng rồi đến vận động viên nhảy cao cầm cờ xanh và cuối cùng là vận động viên bắn cung cầm cờ tím. Giả sử số đội tham dự là đủ lớn, hỏi có thể có tối đa bao nhiêu loại hàng dọc (phân biệt theo độ dài mỗi màu của hàng). Hướng dẫn giải Bài này có thể giải theo phương pháp song ánh để tính số phần tử của tập hợp kết hợp với kỹ thuật dùng dãy nhị phân. 0 a,b,c,d 20 Ta thấy mỗi hàng sẽ tương ứng với một bộ 4 số (a, b, c, d) với để chỉ số a b c d 20 lượng vận động viên thi đấu mỗi môn chạy 100m, nhẩy xa, nhẩy cao, bắn cung tương ứng. Với 23  mỗi bộ 4 số như thế ta đặt tương ứng với dãy nhị phân 1 101 101 101 1. Dễ thấy tương a b c d ứng đó là một song ánh và có 3 dãy nhị phân khác nhau do đó có tối đa 3 1771 loại C 23 C 23 hàng dọc khác nhau.
13. Câu 30. Cho p là số nguyên tố lẻ. Tìm số tập con X của tập {1;2; ;2p}biết rằng X chứa đúng p phần tử và tổng tất cả các phẩn tử của X chia hết cho p. Hướng dẫn giải p Đặt A {c  {1;2; ;2 p}: x p} A C2 p Và Aj {x  A: S(x)  j(mod p)}với j 0,1,2, , p 1 Vì A A0  A1   Ap 1 và Ai  Aj  i j nên: A A0 A1 Ap 1 Xét đa thức: P(x) x p 1 x p 2 x 1, đa thức này có p 1 nghiệm phức { , 2 , , p 1} và p 1 Và x p 1 có p nghiệm phức phân biệt: , ,2 , , p 1, p 1, nên ta có: p x p 1 (x k ) k 1 Suy ra: 2 p p p (x k ) (x k ).(x p k ) k 1 k 1 k 1 p p p 2 k k k p 2 (x )(x ) (x ) (x 1) k 1 k 1 k 1 So sánh hẹ số x p của 2 vế đẳng thức: p (x k ) (x p 1)2 k 1 ta có: ( 1) p  S (x) 2 x A S (x) k Do p lẻ và nếu x Ak ta có: p 1 k  Ak . 2 0 k 0 p 1 k Do vậy x là nghiệm của đa thức: Q(x)  Ak x A0 2 k 1 Vì x là 1 nghiệm bất kì của đa thức: P(x) x p 1 x p 2 x 1 nên A1 A2 Ap 1 A0 2 A A A A 2 A 2 A 2 1 2 p 1 0 0 p p C p 2 A 2 p 2 là số tập con thỏa mãn bài toán. 0 p Câu 31. Một quân cờ di chuyển trên bàn cờ 2016´ 2016 theo một trong ba cách: đi lên một ô, sang bên phải một ô, đi xuống về bên trái một ô. Hỏi quân cờ có thể đi qua tất cả các ô, mỗi ô đúng một lần và quay lại ô kề bên phải ô xuất phát được không?
14. Hướng dẫn giải Sau mỗi bước, tổng thứ tự của hàng và cột chứa quân cờ hoặc giảm đi 2 hoặc tăng lên 1. Như vậy, khi xét theo modulo 3 thì tổng này tăng 1 mỗi bước. Do có 20162 - 1 bước, nếu kết thúc ở ô kề bên phải ô xuất phát thì tổng này tăng 1 đơn vị. Do đó, 20162 - 2 chia hết cho Vậy quân cờ không thể đi qua tất cả các ô, mỗi ô đúng một lần và quay lại ô kề bên phải ô xuất phát. n k 2 n 1 Chứng minh hệ thức : k(Cn ) nC2n 1 k 1 Hướng dẫn giải Ta sẽ giải bài toán sau bằng hai cách “Có n nhà vật lí và n nhà toán học tham gia một Hội nghị khoa học. Hỏi có bao nhiêu cách chọn ra một nhóm làm việc gồm n người, trong đó có 1 nhà vật lí làm nhóm trưởng”. Cách 1: Chọn nhóm trưởng vật lí, sau đó chọn n-1 thành viên còn lại từ 2n -1 người còn lại. +) Chọn nhóm trưởng là một nhà vật lí có n cách. n 1 +) Ứng với mỗi cách chọn nhóm trưởng có C2n 1 cách chọn n -1 thành viên trong 2n -1 thành viên còn lại. n 1 Áp dụng quy tắc nhân có tất cả nC2n 1 cách chọn một nhóm n người thỏa mãn bài toán. (1) Cách 2: Chọn k nhà vật lý, chọn nhóm trưởng là nhà vật lý sau đó chọn n-k nhà toán học với k = 1, 2, , n. Với mỗi giá trị k cố định : k +) Chọn k nhà vật lí trong n nhà vật lí có Cn cách +) Ứng với mỗi cách chọn k nhà vật lí ở trên có k cách chọn một nhóm trưởng là nhà vật lí n k k +) Ứng với mỗi cách chọn k nhà vật lí và một nhóm trưởng vật lí có Cn Cn cách chọn n k nhà toán học trong n nhà toán học. k 2 Áp dụng quy tắc nhân có tất cả k Cn cách. n k 2 Cho k chạy từ 1 đến n ta được tất cả k(Cn ) cách chọn nhóm n người thỏa mãn bài toán k 1 (2). n k 2 n 1 Từ (1) và (2) suy ra k(Cn ) nC2n 1 (đpcm) k 1 Câu 32. Các số nguyên dương 1,2,3, ,2014 được sắp xếp trên một hàng theo một thứ tự nào đó. Ta thực hiện quy tắc đổi chỗ các số như sau: nếu số đầu tiên là k thì ta đổi k số đầu tiên theo thứ tự ngược lại. Chứng minh rằng sau một số hữu hạn lần thực hiện quy tắc trên thì số 1 sẽ xuất hiện ở vị trí đầu tiên Hướng dẫn giải Giả sử k,1 k 2014 là số lớn nhất xuất hiện ở vị trí đầu tiên trong tất cả các quá trình đổi chỗ. Giả sử số k xuất hiện ở lần thứ h. Khi đó ở lần thực hiện sau lần thứ h thì số k sẽ giữ nguyên vị trí. Trong các quá trình đổi chỗ sau đó ta gọi k1 là số lớn nhất xuất hiện ở vị trí đầu tiên. Giả sử số k1 xuất hiện ở lần thứ h1 . Khi đó sau lần thứ h1 thì số k1 sẽ giữ nguyên vị trí, cứ tiếp tục như vậy thì sau một số hữu hạn bước phải dừng lại. Khi không thực hiện việc thực hiện quy tắc đổi chỗ của bài toán tức là số ở vị trí đầu tiên sẽ là số 1. Bài toán được chứng minh.