Tài liệu ôn thi học sinh giỏi Toán Lớp 11 - Chuyên đề: Toán rời rạc (Phần 3) - 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 đề: Toán rời rạc (Phần 3) - Ngô Tùng Hiếu

1. Bài 1. Cho số nguyên n 2 . Chứng minh rằng trong mọi họ gồm ít nhất 2n 1 1 tập hợp con không rỗng phân biệt của tập 1,2, ,n đều tìm được ba tập hợp mà một trong chúng là hợp của hai tập còn lại. Hướng dẫn giải Giải bằng quy nạp Với n=2 ,ta có {1;2}={1}U{2}. Với n>=2, giả sử có 2n+1 tập con không rỗng của tập {1,2, ,n+1} Nếu ít nhất trong 2n-1+1 tập hợp trong chúng không chứa n+1, theo giả thiết quy nạp ta có đpcm. Nếu ít nhất 2n-1+2 tập hợp chứa n+1 thì bỏ n+1 ra khỏi các tập hợp này và ta áp dụng giả thiết quy nạp Nếu có đúng 2n-1 tập con không chứa n+1 thì có đúng 2n-1 tập con chứa n+1 (có nhiều hơn 1 phần tử) và tập {n+1} Loại bỏ n+1 trong những tập con này ta được 2n tập con khác rỗng của tập {1,2, ,n}, và do đó trong chúng phải có hai tập trùng nhau, gọi đó là A. Do vậy AU{n+1}=B  1,2, ,n 1(đpcm) Bài 2. Cho X là một tập hợp 2015 số nguyên dương. Gọi p1, p2 , , pn là các ước nguyên tố của các số trong X. Chứng minh rằng nếu 2015 2n thì tồn tại hai số trong X mà tích của chúng là một số chính phương. Hướng dẫn giải Mỗi số M trong X mã hóa bởi một dãy nhị phân (x1, x2 , , xn ) trong đó xi 0 nếu số mũ của pi trong phân tích tiêu chuẩn của M là chẵn; xi 1 nếu số mũ của pi trong phân tích tiêu chuẩn của M là lẻ. Áp dụng nguyên lí Dirichlet, ta xác định 2015 thỏ là 2015 số trong X. Các chuồng là 2n dãy nhị phân có độ dài n. Khi đó có hai số có tương ứng cùng dãy nhị phân. Tích hai số này là một số chính phương. Bài 3. Cho tập S gồm tất cả các số nguyên trên trong đoạn [1;2014] . Gọi T là tập hợp gồm tất cả các tập con không rỗng của S. Với mỗi tập hợp X T , ký hiệu m(X ) là trung bình cộng của tất cả các số thuộc m(X ) X . Đặt m  (ở đây tổng được lấy theo tất cả các tập hợp X T ). Hãy tính giá trị của m. |T | Hướng dẫn giải Cách 1: Với mỗi x [1,2, , 2014], đặt mk  m(X) ở đây tổng được lấy theo tất cả các tập hợp X T mà | X | k . k 1 Xét số a bất kỳ thuộc S, suy ra a có mặt trong C2013 tập X T mà | X | k . k 1 k 1 Suy ra kmk (1 2 2014)C2013 1007.2015.C2013 . 2014 2014 k 1 2014 2014 C2013 2015 k 2015 k 2015 2014 Do đó  m(X)  mk 1007.2015  C2014  C2014 (2 1) . k 1 k 1 k 2 k 1 2 k 1 2 2015 Mà |T | (22015 1) m . 2 Cách 2. Xây dựng song ánh từ T vào T như sau X T f (X ) {2015- x / x X} m(X ) m( f (X )) 2015 Suy ra 2 m(X) m(X) m(f(X)) | T |.2015 m(X) 2015 Suy ra m  . | T | 2
2. Bài 4.Ở các vị trí khác nhau của một đường đua ô tô vòng tròn cùng một thời gian có 25 ô tô xuất phát theo cùng một hướng. Theo thể lệ cuộc đua, các ô tô có thể vượt lẫn nhau, nhưng cấm không được vượt đồng thời hai xe một lúc. Các ô tô đến đích là các điểm mà chúng xuất phát ban đầu cùng một lúc. Chứng minh rằng trong suốt cuộc đua có một số chẵn lần vượt nhau của các ô tô. Hướng dẫn giải Ở Ta sơn 1 trong 25 ô tô thành màu vàng, còn các oto khác đánh số từ 1 đến 24 theo thứ tự mà chúng ở thời điểm ban đầu sau ô tô màu vàng ( theo chiều chuyển động của các ô tô). Ở tâm của đường đua ta đặt một bảng để ghi số thứ tự của các ô tô sắp xếp sau ô tô vàng sau mỗi lần các ô tô vượt nhau, tức là ta được một hoán vị của {1,2, ,24}. Trường hợp 1: Mỗi lần 2 ô tô trong các ô tô từ 1 đến 24 vượt nhau thì trên bảng có 2 số liền nhau đổi chỗ cho nhau. Trường hợp 2: Nếu trước khi có lần vượt của một ô tô nào với ô tô vàng, các số trên bảng lập thành một hoán vị a1, a2, ,a24 thì sau lần vượt đó sẽ có hoán vị a2,a3, ,a24,a1. Từ hoán vị trên có thể chuyển xuống hoán vị dưới bằng 23 phép chuyển vị, tức là phép đổi chỗ 2 số liền nhau. Trường hợp 3: Nếu ô tô vàng vượt một ô tô nào đó thì từ hoán vị a1,a2, ,a24 ta có hoán vị a24,a1,a2, a23. Lần di chuyển này cũng có thể thay bằng 23 phép chuyển vị như trường hợp 2. Như vậy mỗi lần các ô tô vượt nhau đều dẫn đến việc thực hiện một số lẻ lần phép chuyển vị. Ta sẽ chứng minh nếu số lần vượt nhau là số lẻ thì khi về đích các ô tô không được sắp xếp như cũ. Thật vậy gs a1,a2 ,a24 là một cách sắp xếp tùy ý của các số1,2, 24. Ta sẽ nói rằng các số ai,aj lập thành một nghịch thế nếu i aj. Khi đổi vị trí 2 số đứng liền nhau, tức là thực hiện một phép chuyển vị thì sẽ tăng hay giảm số nghịch thế đi 1. Do đó nếu các oto vượt nhau một số lẻ lần thì từ cách sắp xếp thứ tự của các oto ban đầu, đến cuối cùng ta đã thực hiện một số lẻ các phép chuyển vị, tức là số nghich thế của lần sắp xếp cuối cùng là số lẻ, nghĩa là các ô tô không thể sắp xếp như cũ. Mâu thuẫn. Vậy các ô tô vượt nhau một số chẵn lần. Bài 5. Với n là số nguyên dương, một tập con của tập 1,2,3, ,n được gọi là tốt nếu sau khi ta sắp xếp thứ tự tăng các phần tử của nó thì thu được các số lẻ, chẵn, lẻ, theo thứ tự. Ví dụ các tập con tốt là 1,4,5,6, 3,4,7, tập  . Tập 2,3,4,7không là tập con tốt do nó bắt đầu bởi số chẵn. Tính số tập con tốt của tập 1,2,3, ,n . Hướng dẫn giải Gọi fn là số tập con tốt của 1,2,3, ,n . Ta lập hệ thức truy hồi của fn . + Nếu tập con tốt của 1,2,3, ,n không lấy n thì fn fn 1 . + Nếu tập con tốt của 1,2,3, ,n lấy n thì fn fn 2 . Vậy ta có fn fn 1 fn 2 . Hơn nữa f1 2, f2 3 1 5 Phương trình đặc trưng x2 x 1 0 x 2 n n 1 5 1 5 Suy ra f A B n 2 2
3. 1 5 1 5 2 2 5 1 A B 2 2 2 A 5 5 Thay 2 giá trị đầu ta được 2 2 1 5 1 5 A B 3 2 B 2 2 5 5 Suy ra n n n 1 n 1 2 2 5 1 1 5 2 1 5 2 5 1 1 5 1 1 5 f . n 5 5 2 5 5 2 5 2 5 2 Bài 6. Với mỗi hoán vị p a1,a2 , ,a9 của các chữ số 1, 2, , 9, kí hiệu s p là tổng của ba số có 3 chữ số a1a2a3 , a4a5a6 , a7a8a9 . Trong các s p có hàng đơn vị bằng 0, gọi m là giá trị nhỏ nhất của nó và n là số các hoán vị p thỏa mãn s p m . Tính m n . Hướng dẫn giải Để s p đạt giá trị nhỏ nhất thì 3 chữ số hàng trăm là 1, 2, 3, s p có chữ số tận cùng bằng 0 thì các chữ số hàng đơn vị có tổng là bội của 10. Và từ các chữ số 4, 5, 6, 7, 8, 9 không có ba số nào có tổng bằng 10 và vì 7 8 9 24 30 nên 3 chữ số hàng đơn vị phải có tổng bằng 20, ta thấy 5 6 9 4 7 9 5 7 8 20 , có ba bộ số có thể xếp vào 3 chữ số ở hàng đơn vị, tương ứng các chữ số còn lại sẽ là hàng chục. Do đó giá trị nhỏ nhất của s p là m 1 2 3 100 19 10 20 810 . Như vậy có 3 trường hợp, trong mỗi trường hợp có 6 cách chọn 3 chữ số hàng trăm, 6 cách chọn 3 chữ số hàng chục và 6 cách chọn 3 chữ số hàng đơn vị. Vậy số các hoán vị p thỏa mãn yêu cầu bài toán là n 3 6 6 6 648. Vậy m n 162 . Bài 7. Giả sử n là một số nguyên dương ( n 2014 ) và A {a1,a2 , ,an} là một tập con của tập {1,2, ,2014}, thỏa mãn: nếu ai +a j 2014 , 1 i j n thì ai +a j cũng là một phần tử của tập A . a +a + +a 2015 Chứng minh rằng: 1 2 n . n 2 Hướng dẫn giải Không mất tính tổng quát giả sử rằng a1 a2 an . n Ta sẽ chứng minh a a 2005 k (1). k n 1 k 2 n Thật vậy, giả sử k : a a 2004 . 2 k n 1 k Khi đó a1 an 1 k , a2 an 1 k , ,ak 1 an 1 k và ak an 1 k đều không vượt quá 2004. Như vậy theo giả thiết k số kể trên đều là phần tử của tập A . Nhưng chú ý rằng những số trên đều lớn hơn an 1 k . Điều này dẫn đến một điều mâu thuẫn vì trong tập A chỉ có đúng k 1 số lớn hơn an 1 k , đó là an 2 k , ,an . Vậy điều giả sử là sai. Bất đẳng thức (1) được chứng minh. Áp dụng BĐT (1): 2(a1 +a2 + +an ) (a1 +an ) (a2 +an 1) (an a1) n.2015 đpcm. Bài 8.
4. 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 hai phần tử thuộc S m(m 6) m(m 3) C(m) (hai phần tử này không nhất thiết phân biệt). Chứng minh: 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) +) (2 điểm) Chứng minh: 2 | S | (| S | 3) m(m 3) | A | | S | | S S | | S | | S | C 2 |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. Bài 9. Đ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 15 16 17 18 19 20 21 22 23 24 20 21 22 23 24 25 26 27 28 29 25 26 27 28 1 Bảng 1 Bảng 2 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 (*)
5. 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) 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ị. +) 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 ai liên tiếp qua n số kề với nó và chuyển ai 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 tắc của đề bài. Bài 10. Ban đầu ta có bộ số a,b,c,d trong đó a,b,c,d là các số nguyên đôi một khác nhau. Thực hiện thuật toán sau: nếu có bộ số M x, y, z,t với x, y, z,t nguyên thì được phép thay thế bởi bộ số x y y z z t t x T M , , , . Chứng minh rằng việc thực hiện thuật toán trên sẽ dừng lại sau hữu 2 2 2 2 hạn bước. Hướng dẫn giải Giả sử ngược lại, ta nhận được bộ số với các thành phần là số nguyên. Gọi Sn max xn yn , yn zn , zn tn , tn xn , xn zn , yn tn  trong đó xn , yn , zn ,tn là bộ số nhận được sau bước thứ n . Ta có: Sn 1 Sn ,n 1. * Do Sn ¢ ,n 1 nên tồn tại m ¥ sao cho Sm 0 . Khi đó ta có: xm ym zm tm 0 . Đặt xm ym zm tm k . x y y z z t t x Ta có: m 1 m 1 m 1 m 1 m 1 m 1 m 1 m 1 k . 2 2 2 2 Suy ra: xm 1 zm 1, ym 1 tm 1 .
6. Đặt xm 1 zm 1 u, ym 1 tm 1 v . x y z t y z t x Ta có: m 2 m 2 m 2 m 2 u; m 2 m 2 m 2 m 2 v . 2 2 2 2 x y z t Suy ra: u v m 2 m 2 m 2 m 2 . Thế thì x y z t . 2 m 1 m 1 m 1 m 1 Tiếp tục quá trình lập luận như trên dẫn đến a b c d . Vậy ta hoàn tất chứng minh. Bài 11. 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í dụ a và b, a b a b bởi và . Hỏi có thể nhận được bộ số 28;4;2014 sau khi thực hiện hữu hạn phép biến đổi từ 2 2 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. Bài 12. Cho các số nguyên dương m,n; một bảng hình vuông kích thước n n được gọi là bảng “ m hoàn thiện” nếu tất cả các ô của nó được điền bởi các số nguyên không âm (không nhất thiết phân biệt) sao cho tổng các số trên mỗi hàng và mỗi cột đều bằng m. Hỏi có tất cả bao nhiêu cách lập bảng “2015-hoàn thiện” kích thước 3x3 sao cho số nhỏ nhất trong các số ở các ô trên đường chéo chính nằm ở vị trí tâm của bảng? (Ô ở đường chéo chính của bảng là ô ở vị trí giao của dòng có số thứ tự tính từ trên xuống và cột có số thứ tự tính từ trái sang bằng nhau; ô ở tâm bảng 3x3 là ô ở dòng thứ 2 và cột thứ 2). Hướng dẫn giải Ta giải bài toán trong trường hợp lập bảng “ m hoàn thiện” kích thước 3x3. Gọi x, y, z,t lần lượt là các số điền được ở đường chéo chính và ô ở vị trí dòng 1 cột 2 , khi đó các số còn lại ở các ô được xác định duy nhất như hình bên dưới x t m x t m z x y t y x t z y t z m y t z Vì các số được điền là không âm và y là số nhỏ nhất trong các số ở đường chéo chính nên các điều kiện sau phải thỏa
7. x, y, z,t 0; x t m; x t z; z y t m; x y t m z; y min x, y, z Các điều kiện trên có thể rút gọn lại thành 0 y min x, y, z; x t m; z y t * Khi đó 0 y 2y t z x y t z x t m . Ta thấy rằng bộ bốn số không âm y;2y t z; x y t z; x t sắp theo thứ tự tăng dần xác định duy nhất bộ các số x, y, z,t thỏa mãn * và tương ứng với một cách lập bảng “ m hoàn thiện”. Do vậy, số m 4 cách lập được là . 4 2019 Áp dụng với m 2015được kết quả là . 4 Bài 13. Cho 51 điểm bất kì phân biệt nằm trong hình vuông ABCD có cạnh bằng 5, trong đó không có không có 3 điểm nào thẳng hàng. Vẽ các đường tròn có bán kính bằng 2 và có tâm lần lượt là 51 điểm trên. Chứng minh rằng tồn tại 3 điểm trong số 51 điểm nói trên sao cho chúng đều thuộc phần giao của 3 hình tròn có tâm cũng chính là 3 điểm đó. Hướng dẫn giải * Chia hình vuông ABCD thành 25 hình vuông đơn vị ( có cạnh bằng 1) Theo nguyên lý Dirichlet, có ít nhất 1 hình vuông đơn vị chứa không ít hơn 3 điểm. * Mặt khác, khoảng cách giữa hai điểm bất kì trong một hình vuông đơn vị không vượt quá 2 . * Gọi I1, I2, I3 là 3 điểm nằm trong hình vuông đợ vị nào đó. Vẽ 3 đường tròn có tâm lần lượt là I1, I2, I3 và có bán kính bằng 2 thì 3 điểm I1, I2, I3 đều thuộc giao của cả 3 hình tròn này ( Đpcm). Bài 14. Cho 2013 điểm trên đường thẳng, tô các điểm bằng một trong 3 màu màu xanh, đỏ, vàng (mỗi viên bi chỉ tô một màu). Có bao nhiêu cách tô khác nhau sao cho không có 3 điểm liên tiếp nào cùng màu. Hướng dẫn giải Gọi là số cách tô màu thỏa mãn cho n () điểm (bài toán của ta là n 2013 ). Ta sẽ tính theo , xét hai bi cuối cùng của có hai trường hợp xảy ra: +Nếu hai bi cuối cùng màu thế thì bi thứ n 1khác màu 2 bi cuối. +Nếu hai bi cuối khác màu thì bi thứ n 1tô bất kì. Từ đó sinh ra hai số đặc trưng là số cách tô n bi mà hai bi cuối cùng màu, là số cách tô màu n bi mà hai bi cuối khác màu và cả hai cùng thỏa mãn 3 bi liên tiếp khác màu. Ta có: Sn 1 2M n 2Pn , Pn 1 2Sn ;M n 1 Pn . Thế thì Sn 1 2Pn 1 6Sn 4Sn 2 6Sn 1 . Vậy ta có hệ thức truy hồi: Sn 1 6Sn 1 4Sn 2 0 . Bây giờ ta 2 tính S3 , S4 thấy ngay S3 27 3 24 , S4 4! 3 12 49 . Phương trình đặc trưng X 6X 4 0 có n n nghiệm là: x1 3 13, x2 3 13 . Công thức xác định Sn ax1 bx2 với a,b thỏa mãn: 24 13 23 a a(3 13)3 b(3 13)3 24 2 13(3 13)3 a(3 13)4 b(3 13)4 49 24 13 23 b 3 2 13(3 13) Sau đó cho n 2013 ta được kết quả bài toán. Bài 15. Đối với mỗi giá trị của n ¥ , tìm số k lớn nhất thỏa mãn trong tập hợp gồm n phần tử có thể chọn ra k tập con khác nhau sao cho hai tập con bất kỳ đều có giao khác rỗng.
8. Hướng dẫn giải Số tập con của X là 2n . Giả sử chọn được 2n 1 1 tập con của X có giao khác rỗng. Ta chia các tập con của X thành 2n 1 cặp được tạo bởi một tập con của X và phần bù của tập con đó trong X. Có 2n 1 cặp, chọn ra 2n 1 1tập từ 2n 1 cặp nên theo nguyên lý Dirichlet phải có ít nhất 2 tập thuộc cùng một cặp, và do đó giao của nó bằng rỗng. Điều này chứng tỏ không thể chọn được lớn hơn hoặc bằng 2n 1 1 tập sao cho giao của hai tập bất kỳ trong chúng khác rỗng. n 1 n n 1 n 1 Số tập con của X không chứa phần tử ai là 2 . Số tập con của X chứa ai là 2 2 2 . Do đó có n 1 n 1 2 tập con của X có giao là phần tử ai nên số k lớn nhất cần tìm là 2 . Bài 16. Trên bảng có 2013 số tự nhiên : 1;2; ;2013. Thực hiện phép toán: mỗi lần xóa đi 2 số (giả sử 2 số xóa đi là a và b) và viết lên bảng một số là a.b - a - b + 2. Sau 2012 lần thực hiện phép toán như vậy thì trên bảng chỉ còn 1 số. Hỏi đó là số nào? Hướng dẫn giải Gọi a1;a2 ; ;a2013 là 2013 số tự nhiên đã cho trên bảng. Xét tích P (a1 1)(a2 1) (a2013 1) . Mỗi lần xóa đi 2 số a,b ( a,b a1;a2 ; ;a2013 ) và viết thay bằng số a.b -a - b +2 thì trong tích P xóa đi 2 thừa số (a-1); (b-1) và viết thêm thừa số a.b - a - b +1. Vì : a.b a b 1 (a 1)(b 1) nên tích P không đổi sau mỗi lần thực hiện phép toán. Ta có P = 0 ( vì 1 a1;a2 ; ;a2013) nên số cuối cùng còn lại trên bảng là số 1. Bài 17. Cho p và q là các số nguyên dương khác 1. Tìm số nguyên dương m bé nhất sao cho trong mỗi m số nguyên phân biệt thuộc đoạn [ q; p], tồn tại 3 số khác nhau có tổng bằng 0 . Hướng dẫn giải Ta sẽ chứng minh giá trị nhỏ nhất của m là max( p,q) , ở đây 3 nếu p , q là số chẵn và p q , c 2 trong các trường hợp còn lại. Rõ ràng giá trị nhỏ nhất của m là tồn tại, ký hiệu nó bởi m0 . Không mất tính tổng quát ta có thể giả sử p q . Đoạn [ p;q] chứa q 1 số không âm và không có ba số nào có tổng bằng 0 , suy ra trong mỗi trường hợp m0 q 2 . Khi p , q là số chẵn và p q thì tập { q; q 1;; q / 2;q / 2;;q} gồm q 2 số và không có ba số nào có tổng bằng 0 . Do đó m0 q . Bây giờ ta đi chứng minh m0 q . Xét ba trường hợp Trường hợp 1: p và q là hai số lẻ bằng nhau. Bằng quy nạp theo q ta chứng minh được Bổ đề. Nếu X  [ q;q]‚ {0} và X không chứa ba phần tử có tổng bằng 0 thì | X | q 1. Thật vậy, khẳng định hiển nhiên đúng với q 1. Giả sử nó đúng với các số lẻ bé hơn q . Xét tập X  [ q;q]‚ {0} sao cho X không chứa ba phần tử có tổng bằng 0 . Đặt Y X { q; (q 1);q 1;q}. Nếu |Y | 2 thì | X | (q 1) 2 q 1theo giả thiết quy nạp. Bây giờ ta xem là |Y | 3 . Chắc chắn Y chứa hai phần tử cùng dấu, giả sử hai phần tử đó âm, do đó q Y  X . q 1 Suy ra với mỗi i 1,2,, , nhiều nhất một phần tử trong {i,q i} sẽ thuộc X , suy ra X chứa nhiều 2 q 1 nhất phần tử dương, dấu bằng có thể xảy ra chỉ khi q X . 2
9. q 1 Nếu q X thì bởi tính đối xứng, X chứa nhiều nhất phần tử âm, do đó | X | q 1. 2 Bài 18. Cho tập hợp X 1;2;3; ;2016. Tìm số k nguyên dương nhỏ nhất sao cho với mọi tập con gồm k phần tử của tập hợp X đều chứa ít nhất 5 số nguyên liên tiếp. Hướng dẫn giải Xét tập hợp A X / 5k,1 k 403 A 2016 403 1613 Với k không lớn hơn 1613, thì chọn bất kỳ tập hợp B là tập con gồm k phần tử của A, cũng là tập con của X và B không thể chứa 5 số nguyên liên tiếp. Nếu k = 1614. Xét C là một tập con của X gồm 1614 phần tử A 5i 4;5i 3;5i 2;5i 1;5i ,i 1;403, A 2016 i  404  Nếu mỗi tập hợp trên chứa tối đa 4 phần tử thuộc C thì số phần tử của C không quá 4x403+1= 1613 ( vô lý). Vậy trong các tập hợp gồm 5 phần tử trên phải có 1 tập là con của C nên C chứa 5 số nguyên lien tiếp. Vậy số k nhỏ nhất cần tìm bằng 1614. Bài 19. Cho trước k số khác không a1; a2; ; ak thoả mãn với mọi số tự nhiên n lẻ ta có n n n a1 a2 ak 0 . Chứng minh rằng k chẵn và giả sử k = 2m thì các số a 1; a2; ; ak có thể phân chia thành m cặp sao cho tổng của 2 số trong mỗi cặp bằng 0. Hướng dẫn giải Do k hữu hạn nên trong k số a1; a2; ; ak ta chọn được số có giá trị tuyệt đối lớn nhất. Giả sử số đó là a1. n n a a Theo giả thiết, với mọi n lẻ ta có: 1 2 k 0 1 a1 a1 ai Do a1 có giá trị tuyệt đối lớn nhất nên 1,i 2,3 k a1 a Ta chứng minh, tồn tại i để i 1 a1 a Giả sử không có số nào trong các số i bằng -1. a1 a a Không mất tính tổng quát, giả sử i = 2, 3, , t thì i 1 và với i = t + 1, , k thì i 1. a1 a1 n n a a Khi đó, từ (1) S t 1 k t S t với mọi n lẻ a1 a1 a Do i 1 với i = t + 1, , k a1 n a t chọn n lẻ đủ lớn để i với i = t + 1, , k a1 k t n n a a S t 1 k t (mâu thuẫn) a1 a1 a Do đó, trong các số i có ít nhất 1 số bằng -1. a1
10. a2 Giả sử 1 a1 + a2 = 0. a1 Còn lại k – 2 số: a3; a4; ; ak. Nếu k chẵn lặp lại lập luận trên đpcm Nếu k lẻ thì phải có 1 số trong các số đã cho mà mọi luỹ thừa lẻ của nó đều bằng 0 số đó bằng 0 (mâu thuẫn) Vậy ta có điều phải chứng minh. Bài 20. Hãy chỉ ra tất cả các cách tô tất cả các số tự nhiên bởi ba màu xanh, đỏ, vàng sao cho trong mỗi cách tô, các điều kiện sau được đồng thời thỏa mãn: 1) Mỗi số tự nhiên được tô một màu và mỗi màu được dùng để tô vô số số tự nhiên; 2) Số 2 không được tô màu xanh; 3) Nếu số a được tô màu xanh thì số a +1 được tô màu đỏ hoặc màu vàng. 4) Nếu số a được tô màu đỏ và số b được tô màu vàng thì số a +b được tô màu xanh. Hướng dẫn giải Trong phần trình bày dưới đây, khi nói tới số ta hiểu đó là số tự nhiên. * Xét một cách tô màu thỏa mãn các điều kiện của đề bài. Trước hết, từ 3) và 4), bằng phản chứng dễ dàng suy ra hai số liên tiếp không được tô cùng một màu. Từ 4) và 1), cũng bằng phản chứng, dễ dàng chứng minh được 0 được tô màu xanh. Từ đó suy ra 1 được tô màu đỏ hoặc màu vàng. Không mất tổng quát, giả sử 1 được tô màu đỏ. Khi đó, vì 2 không được tô màu xanh (theo 2)) nên 2 phải được tô màu vàng. Suy ra 3 được tô màu xanh (do 3=1+2). (*) Tiếp theo, gọi a là số nhỏ thứ hai được tô màu đỏ (1 là số nhỏ nhất có tính chất vừa nêu). Ta sẽ chứng minh a là số chẵn. Thật vậy, giả sử ngược lại a = 2b + 1, với b là số lớn hơn 1. Khi đó, tất cả các số từ 3 đến 2b - 1 (kể cả 2b - 1) không được tô màu đỏ và 2b được tô màu xanh. Suy ra 2b - 1 được tô màu vàng. Dẫn tới 2b - 2 được tô màu xanh, và do đó 2b - 3 được tô màu vàng. Tiếp tục quá trình suy luận đó, ta được 4 phải được tô màu xanh, và do đó 3 sẽ không được tô màu xanh (do 3)), mâu thuẫn với (*). Mâu thuẫn nhận được cho ta điều muốn chứng minh. Đặt q = a – 1. Hiển nhiên, mỗi số n được biểu diễn duy nhất dưới dạng n = kq + r, với 0 r q . Bằng quy nạp theo k, dễ dàng chứng minh được rằng: - Tất cả các số n = kq + r, mà r = 0 hoặc r là số lẻ khác 1, đều được tô màu xanh; - Tất cả các số n = kq + 1 đều được tô màu đỏ; - Tất cả các số n = kq + r, mà r là số chẵn khác 0, đều được tô màu vàng. *Ngược lại, tô tất cả các số tự nhiên theo cách sau: - Tô màu xanh tất cả các số n = kq + r, 0 r q , mà r = 0 hoặc r là số lẻ khác 1; - Tô màu đỏ (hoặc vàng) tất cả các số n = kq + 1; - Tô màu vàng (hoặc đỏ) tất cả các số n = kq + r, 0 < r < q mà r là số chẵn khác 0; Trong đó, q là một số lẻ bất kì lớn hơn 1. Dễ dàng kiểm tra được rằng cách tô màu nêu trên thỏa mãn tất cả các điều kiện của đề bài. *Vậy, tóm lại, tất cả các cách tô màu thỏa mãn điều kiện của bài ra là tất cả các cách tô màu vừa được mô tả ở trên. Bài 21. Cho n là một số nguyên dương. Hãy xác định số các bộ ba (A, B,C) (không kể thứ tự) các tập hợp con của tập 1;2;3; ,n thỏa mãn tính chất : A B  , B C  , C  A  và A B C  . Hướng dẫn giải
11. . Bổ đề : Số các cách chọn hai tập hợp con khác rỗng, rời nhau của một tập hợp k 0 phần tử là : k k 1 Nk 3 2 1. Thật vậy, Giả sử S là tập hợp có k phần tử và ta cần đếm số các cặp (A, B) các tập hợp con của S khác i rỗng và rời nhau. Có Ck cách chọn A, mà A i 1. Sau đó ta chỉ cần chọn một tập hợp con tùy ý khác rỗng của S \ A . Số cách chọn B là : 2k i 1. Do đó : k 1 k k i i i k i i i k k k 1 Nk  2 .Ck Ck  2 .Ck Ck (2 1) 3 2 1 i 1 i 0 . Tất cả các bộ ba thỏa mãn yêu cầu bài toán được xây dựng như sau : k Đầu tiên ta chọn tập con B có k 2 phần tử . Số cách chọn là Cn . Mỗi tập con B như thế, ta chọn hai tập hợp con rời nhau khác rỗng của B có dạng A B và B C . Theo bổ đề trên, ta có Nk cách chọn . Sau đó ta tiếp tục chọn hai tập con khác rỗng rời nhau của B* 1;2;3; ;n \ B mà có dạng là A \ (B  A) và C \ (B C) . Có 4n k cách chọn hai tập hợp con từ B* , trong đó chú ý rằng trong đó có 2 2n k cặp mà ít nhất một tập là rỗng và có một trường hợp mà cả hai là rỗng. Thành thử, có: n k n k n k n k 4 2 2 1 Nn k 4 3 cách để dựng ra A và C. n k k k 1 n k n k Cuối cùng, tổng số các bộ ba thỏa mãn yêu cầu bài toán là : T  Cn (3 2 1)(4 3 ) k 0 Từ đây suy ra số các bộ ba (A, B,C) là : T 7n 3 6n 3 5n 4n . Bài 22. Cho 2015 điểm trên đường thẳng, tô các điểm bằng một trong 3 màu xanh, đỏ, vàng (mỗi điểm chỉ tô một màu). Có bao nhiêu cách tô khác nhau sao cho không có 3 điểm liên tiếp nào cùng màu. Hướng dẫn giải Gọi là số cách tô màu thỏa mãn cho n () điểm (bài toán của ta là n 2015 ). Ta sẽ tính theo , xét hai điểm cuối cùng của có hai trường hợp xảy ra: +Nếu hai điểm cuối cùng màu thế thì điểm thứ n 1khác màu 2 điểm cuối. +Nếu hai điểm cuối khác màu thì điểm thứ n 1 tô bất kì. Từ đó sinh ra hai số đặc trưng là số cách tô n điểm mà hai điểm cuối cùng màu, là số cách tô màu n điểm mà hai điểm cuối khác màu và cả hai cùng thỏa mãn 3 điểm liên tiếp khác màu. Ta có: S 2M 3P , P 2S ;M P n 1 n n n 1 n n 1 n . Thế thì Sn 1 2Pn 1 6Sn 1 4Sn 2 6Sn 1 . Vậy ta có hệ thức truy hồi: Sn 1 6Sn 1 4Sn 2 0 . Bây giờ ta 2 tính S3 , S4 thấy ngay S3 27 3 24 , S4 4! 3 12 49 . Phương trình đặc trưng X 6X 4 0 có nghiệm là: x1 3 13, x2 3 13 . n n Công thức xác định Sn ax1 bx2 với a,b thỏa mãn: 24 13 23 a a(3 13)3 b(3 13)3 24 2 13(3 13)3 a(3 13)4 b(3 13)4 49 24 13 23 b 3 2 13(3 13) Sau đó cho n 2015 ta được kết quả bài toán. Bài 23. Cho tập hợp 푆 = {1,2, ,2016}.
12. a) Hỏi có bao nhiêu tập con 3 phần tử của 푆 mà chúng là độ dài 3 cạnh của một tam giác có cạnh lớn nhất có độ dài bằng 1000? b) Chọn ngẫu nhiên 3 phần tử của 푆, tính xác suất để 3 số được chọn là độ dài 3 cạnh của một tam giác có cạnh lớn nhất có độ dài là một số chẵn. Hướng dẫn giải a) Đặt 1000 = 2 và gọi là tập chứa các tập con thỏa mãn đề bài, theo BĐT tam giác và không mất tính tổng quát, ta có = {{ , ,2 } ⊂ 푆| 2 }. Rõ ràng = {{ , } ⊂ 푆| 2 }. Từ điều kiện của và ta có + > 2 và + > 2 . Ta xét hai trường hợp, đó là trường hợp 2 }. Khi đó, số cách chọn 3 phần tử thỏa mãn yêu cầu đề bài là 1008 | 2 | . =1 2 Theo câu a), ta có | 2 | = ( ― 1) . Suy ra 1008 1008 1007 1007 ⋅ 1008 ⋅ (2 ⋅ 1007 + 1) | | = ( ― 1)2 = 2 = . 2 6 =1 =1 =0 3 Và do số cách chọn 3 phần tử bất kì thuộc 푆 là C2016, suy ra xác suất cần tính là 1007 ⋅ 1008 ⋅ (2 ⋅ 1007 + 1) 1 3 = = 0,25. 6C2016 4 Bài 24. 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 ? 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
13. 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.