Tài liệu Bồi dưỡng học sinh giỏi môn Toán Lớp 12 - Chuyên đề 20: Tổ hợp và rời rạc

Nội dung text: Tài liệu Bồi dưỡng học sinh giỏi môn Toán Lớp 12 - Chuyên đề 20: Tổ hợp và rời rạc

1. Gọi X là tập gồm tất cả các số thoả mãn yêu cầu đề bài. A là tập gồm tất cả các số có 15 chữ số được lập nên bởi các chữ số 1, 2, 3, 4, 5 mà mỗi chữ số đều có mặt đúng 3 lần trong số. 5 Khi đó: X A \  Ai Với Ai là tập gồm tất cả các số thuộc A mà chữ số i i 1 chiếm đúng 3 vị trí liên tiếp i 1,2, 3, 4, 5 k 15 2k ! 15! Xét 1 k 5 ta chứng minh được  Ai 5-k và A 5 i 1 3 3 k n k k-1 Áp dụng công thức:  Ai  1   Ai i 1 k 1 1 i1 i2 ix in i 1 15! 13! 11! 9! 7! 5! X C1 C 2 C3 C 4 C5 35 5 34 5 33 5 32 5 3! 5 30 Bài toán 20. 7: Cho các số nguyên dương k và n với k n . Hỏi tất cả có bao nhiêu chỉnh hợp chập k a1, a2 , ak của n số nguyên dương đầu tiên, mà mỗi chỉnh hợp a1,a2 , ,ak thoả mãn ít nhất một trong hai điều kiện sau: 1) Tồn tại s, t 1; 2; ;ksao cho s at 2) Tồn tại s 1; 2; ;k sao cho as s không chia hết cho 2. Hướng dẫn giải Gọi A là tập hợp tất cả chỉnh hợp chập k của n số nguyên dương đầu tiên và A1 là tập hợp tất cả chỉnh hợp thoả mãn yêu cầu của bài ra. Nếu kí hiệu A2 { chỉnh hợp (a1, ,ak ) A / ai ai 1, i 1 ,2, ,k 1 và ai , i mod 2, i 1,2, ,k} thì rõ ràng A2  A và A1 A \ A2 . Suy ra: A1 A A2 Bây giờ ta xét A2 . Với mỗi (ai , ,ak ) A2 ta đều có ai i a j j với mọi i i 1, ,k, ai i 2 và ai i 1, ,n k với mọi i 1,2, ,k. k n! k Ta chứng minh: A2 C n k từ đó ta có: A1 C n k n k ! 2 2 Bài toán 20. 8: Trong mặt phẳng cho 100 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng.Chứng minh rằng trong số các tam giác được tạo thành từ 100 điểm đó, có không quá 70% các tam giác nhọn. Trang 5
2. Vì tất cả Ek 0 , nên rõ ràng là trò chơi xổ số này không có lợi cho người chơi dù viết mấy số. Xác suất sao cho có hơn 10 người thắng trong số những người viết 3 số bằng 0.24 Bài toán 20. 10: Hai đấu thủ A và B thi đấu trong một giải cờ vua. Người thắng một ván được một điểm và không có ván hoà. Xác suất thắng một ván của đấu thủ A là và của  là p. Ai hơn đối thủ hai điểm thì thắng giải. Tính xác suất thắng giải của mỗi đấu thủ. Hướng dẫn giải Giả sử  . Kí hiệu Pn A là xác suất thắng giải của A sau n ván; Ai và Bi là các biến số tương ứng A và B thắng ván đầu tiên. Khi đó: Pn A P A1 Pn-1 A / A1 P B1 Pn-1 A / B1 Pn-1 A / A1  Pn-1 A / B1 (*) Trong đó Pn-1 A / A1 là xác suất A thắng giải sau n – 1 ván còn lại, khi A đã thắng ván đầu tiên; Pn-1 A / B1 là xác suất A thắng giải sau n – 1 ván còn lại, khi B đã thắng ván đầu tiên. Xét n 2 . Để A thắng giải sau n – 1 ván còn lại, khi A đã thắng ván đầu, thì B phải thắng ván thứ hai, nghĩa là: Pn-1(A / A1) P(B1)Pn-2 (A)  Pn-2 (A) Tương tự: Pn-1(A / B1) P(A1)Pn-2 (A) Pn-2 (A) Từ đó và (*) ta có Pn (A) 2 Pn-2 (A) , và suy ra 2 n-1 2 P4 (A) 2  , , P2n (A) 2  2 Khi n 2 ta có P2 A . Vì không có ván hoà nên  1, do đó xác suất thắng giải của A là: 2 2 2 P(A) P (A) 2 1 2  2   2k 2 2 k 1 1 2   Bài toán 20. 11: Tìm tất cả các số nguyên dương n có tính chất sau: Có thể chia tập hợp 6 số n, n 1, n 2, n 3, n 4, n 5 thành hai tập hợp, sao cho tích tất cả các số của tập hợp này bằng tích tất cả các số của tập hợp kia. Hựớng dẫn giải Ta hãy để ý rằng trong 5 số nguyên liên tiếp phải có một số chia hết cho 5. Trang 7
3. Trường hợp 2: k 4t, t N . Khi đó, tập X sẽ có 4t 1phần tử. Do đó, nếu X được chia thành hai tập con rời nhau A, B thì một trong hai tập con đó, không mất tổng quát giả sử là A, phải có không ít hơn 2t + 1 phần tử. Như vậy, tập B sẽ có không quá 2t phần tử. Suy ra, nếu kí hiệu a, b tương ứng là tổng của tất cả các phần tử của A, B thì: a 1990 (1900 1) (1900 2t) 1990 2t 1 t 2t 1 b (1990 2t 1) (1990 4t) 1990 X 2t t(6t 1) Với giả thiết a b ta có: 1990 x2t t(6t 1) 1990(2t 1) t(2t 1) 4t 2 1990 nên t 23 Với t 23ta có X {1990, 1990 1, , 1990 92} AUB, Với: A {1990 1, 1990 2, , 1990 46}. B {1990 ; 1990 47, 1990 48, , 1990 92} Hiển nhiên A, B rời nhau, và bằng tính toán trực tiếp dễ thấy a b . Như vậy với t 23( k 92) tập X có tính chất T. Với t 3 ta có: X X1UX 2 với X1 1990,1990 1, ,1990 92 và X 2 {1990 93, 1990 94, ,1990 4t} Theo phần trên, tập X1 có tính chất t. Hơn nữa, do tập X2 có 4 t 23 , phần tử nên, vận dụng những lập luận đã trình bày khi xét trường hợp 1, ta sẽ được tập X 2 có tính chất T. Từ đó suy ra tập X cũng có tính chất T. Vậy, tóm lại, tất cả các số nguyên dương k cần tìm là tất cả các số có dạng k 4t 3, t N và k 4t, t N ,t 23 Bài toán 20. 13: Cho tập hợp số M 1, 2, ,n.Hãy tìm số m nhỏ nhất sao cho mỗi tập con chứa m phần tử của tập M đều tồn tại ít nhất hai số a, b thoả số này là bội của số kia Hướng dẫn giải n n  n Ta có C 1; 2; n có n phần tử và không có phần tử nào là bội 2 2  2 của ít nhất 1 phần tử khác thuộc C. n 1 n 1 Suy ra: m 1 phần tử. Ta chứng minh: m 1 2 2 Trang 9
4. T 0 R 0,0, ,0,0 0 cho nên T(0) là đa thức bậc n của x, suy ra hệ số của bậc n cao nhất x trong khai triển (*) là Rn 0, 0, ,0 0 b) Với một bộ a1,a2 , ,ak-1 thoả a1 0,1, ,n,a1 a2 ak-1 0 ta có R a1,a2 , ,ak-1, X triệt tiêu tại n+1 điểm X 0, 1, 2 n . Vì bậc của R a1,a2 , ,ak-1, X không vượt quá n, cho nên R a1,a2 , ,ak-1, x là đa thức đồng nhất 0, do đó tất cả hệ số của nó trong khai triển (*) bằng 0 và đặc biệt là R a1,a2 , ,ak-1 0 Như vậy, Rn x1, x2 , , xk-1 là đa thức có bậc không nhỏ hơn (k – 1)n theo giả thiết quy nạp, cho nên R x1, x2 , , xk-1, x là đa thức có bậc không nhỏ hơn kn. Do đó deg P deg R x1, x2 , , xk-1, x kn . Bổ đề đựợc chứng minh. Bây giờ giả sử N mặt phẳng ai x bi y ci z di 0 chứa tất cả các điểm của S nhưng không chứa điểm (0,0, ,0). Khi đó xét N P x, y, z (ai x bi y ci z d j ) i 1 Đa thức này có bậc là N và P(x, y,z) thoả mãn các giả thiết của bổ đề, nên ta có N deg P 3n là điều phải chứng minh. Bài toán 20. 15: Xét hoán vị S0 , S1 , , Sn cua các số 0, 1, 2, ,n, ta tác động một phép biến đổi lên hoán vị này nếu tìm được i, j sao cho si 0 và s j si-1 1. Hoán vị mới tạo thành nhận được bằng cách đổi chỗ hai phần tử Si và Sj. Hỏi với số n nào thì xuất phát từ hoán vị 1, n, n 1, n 2, , 3, 2, 0 ta có thể nhận được hoán vị 1,2, ,n,0 bằng cách lập lại nhiều lần phép biến đổi đó? Hướng dẫn giải Thử trực tiếp, ta thấy rằng có thể thực hiện yêu cầu của bài toán trong trường hợp n 1, n 2, 3, 7, 15 , nhưng không thực hiện được khi n 4, 5, 6 ,8 ,9 , 10, 11, 12, 13,1 4 . Từ đó, ta dự đoán rằng các số dạng n 2m 1và số n 2 sẽ thoả mãn điều kiện bài toán. Ta để ý nếu n 2m , thì sau m-1lần biến đỗi ta sẽ có 1 n 0 n 2 n 1 n 4 n 3 4 5 2 3 và không thể làm tiếp được. Vậy với n chẵn, n 2 ta không thực hiện được . Trang 11
5. n k Để ý: pn (k) Cn Pn-k (0), pn (k) n! k 0 n n k Từ đó suy ra:  pn (k)  k.Cn pn-k (0) k 0 i 1 n n-1 n-1 k-1 k nCn-1 pn-k (0) Cn-1 pn-k-1(0) n pn-1 k n n 1 ! n! k 0 k 0 k 0 Bài toán 20. 17: Chứng minh rằng tập hợp 1, 2, 3, ,1989 có thể được viết thành hợp của các tập rời nhau A1, A2 , A117 sao cho mọi Ai , i 1, 2, ,117 , đều có chứa 17 phần tử và tổng giá trị của các phần tử những Aị đều bằng nhau. Hướng dẫn giải Trước hết, ta xây dựng 117 tập hợp gồm 3 số sao cho tổng của 3 số đó trong mỗi tập đều bằng 0 và chúng rời nhau từng đôi một như sau: Từ tập 1, 2, 3, , 1989, ta tạo thành tập M 994, 993, ,993, 994, tập hợp này có được bằng cách lấy từng số hạng của tập hợp đã cho trừ đi 995. Khi đó, ta tạo 116 tập hợp gồm 3 số nói trên là: N1 {993, 496, 497}, N2 { 993, 496, 497}, N2k 1 {993 4k, 2k 496, 2k 497}, N2k 2 { 993 4k, 2k 496, 2k 497}, N115 {665, 382, 383}, N116 { 665, 382, 383} Ngoài ra, ta đặt N117 { 1 ,0, 1} Tất cả 117 tập hợp trên đều rời nhau từng đôi một, Thật vậy, trong mỗi tập, do các phần tử thứ hai đều chẵn nên các phần tử thứ hai của các tập hợp N1, , N116 không thể trùng với các phần tử thứ nhất hoặc thứ ba của những tập hợp này, tất cả các phần tử thứ nhất của những tập hợp này có giá trị tuyệt đối lớn hơn tất cả phần tử thứ ba, thành thử các tập hợp Ni rời nhau từng đôi một. Ngoài ra, nếu số x nào đó là phần tử của một trong các tập hợp Ni thì số (-x) cũng là phần tử của một trong các tập hợp Ni . Để ý rằng 14.117 phần tử của tập hợp M, không thuộc về một trong các tập hợp Ni , được chia thành 7.117 cặp số với dấu đối Trang 13
6. B C . Quá trình kết thúc khi thu được một tập hợp c sao cho c B C c B 1 c(A) . Ta chứng minh c A  C c A . Thật vậy, xét một nhóm bạn bè Q tuỳ ý trong A  C . Do mỗi phần tử của c là bạn bè của mọi phần tử M A cho nên Q  M A là một nhóm bạn bè trong G và do đó: c G 2m Q  M A Q 2m A A Q . Vậy B C và A  C là phân hoạch của G thành hai tập hợp có cùng cỡ (đpcm). Bài toán 20. 19: Trong kỳ thi Olympic có 17 học sinh thi Toán được mang số ký danh trong khoảng từ 1 đến 1000. Chứng tỏ rằng có thể chọn ra 9 học sinh thi Toán có tổng các số ký danh được mang chia hết cho 9. Hướng dẫn giải Xét 5 số tự nhiên tuỳ ý, khi chia cho 3 có thể xảy ra: Có 3 số dư giống nhau Tổng 3 số tương ứng chia hết cho 3. Trái lại, sẽ có 3 số dư đôi một khác nhau Tổng 3 số tương ứng chia hết cho 3. Vậy trong 5 số tự nhiên bất kì, tồn tại 3 số có tổng chia hết cho 3. Xét 17 số tự nhiên tuỳ ý: Chia chúng thành 3 tập, có lần lượt 5, 5, 7 phần tử. Trong mỗi tập, chọn được 3 số có tổng lần lượt là: 3a1, 3a2 , 3a3 a1,a2 , a3 N còn lại: 17 9 8 số, trong 8 số này, chọn tiếp 3 số có tổng là 3a 4 , còn lại 5 số, chọn tiếp 3 số có tổng là 3a5 . Trong 5 số a1,a2 ,a3 ,a4 ,a5 có 3 số ai1,ai2 ,ai3 có tổng chia hết cho 3. 9 học sinh tương ứng có tổng các số kí danh là: 3ai1 3ai2 3ai3 3 ai1 ai2 ai3 9 Bài toán 20. 20: Cho 75 điểm trong hình lập phương có cạnh 1. Chứng minh rằng tồn tại 7 một tam giác có 3 đỉnh trong số các điểm đó có diện tích không quá 12 Hướng dẫn giải Trước hết ta chứng minh bổ đề sau: Bổ đề: Trong hình lập phương cạnh a có 3 điểm, khi đó diện tích tam giác có 3 a 2 3 đỉnh tại các điểm đó không lớn hơn 2 Trang 15
7. Như vậy: cần có 1991 729 1262 học sinh rời khỏi vị trí có 1262 : 2 631 nhóm 3 người, do đó cần có 631 . 3 1893 học sinh đứng trước học sinh B đếm số 1 đầu tiên trong 729 người còn lại. Vậy nếu chọn số 1 đầu tiên trong số 1991 người thì học sinh B đứng ở vị trí thứ 1894 sẽ là người đếm sổ 1 đầu tiên trong 729 người, do đó sẽ còn lại đến cuối cùng và được thưởng. Bài toán 20. 22: Tại đỉnh A0 của đa giác A0 A1 A2 An n 3 người ta đặt n viên bi. Thực hiện việc chuyển chỗ các viên bi theo cách sau: mỗi lần lấy một viên bi ở A, rồi đặt vào một đỉnh kề Ai và đồng thời lấy một viên bi ở Ai rồi đặt nó vào một đỉnh kề Ai với i, j e 0, 1, 2, ,n (có thể i = j). Hãy tìm tất cả giá trị của n sao một số hữu hạn lần thực hiện việc chuyển bi nói trên một cách thích hợp thì ở mỗi đỉnh A1, A2 , , An đều có một viên bi. Hướng dẫn giải Ta thấy n 2k (k là số tự nhiên > 2) thoả mãn bài ra. Vậy ta xét n 2k 1 với k tự nhiên 0 . Ta tô các đỉnh A0 , A2 , , A2k 1 với hai màu xanh, đỏ sao cho đỉnh A0 được tô màu đỏ; với mỗi i 0,1,2, , 2k 1đỉnh Ai có màu khác với màu của đỉnh kề với nó. Ta nhận thấy rằng: trong mỗi lần chuyển bi, mỗi bi đều được chuyển từ đỉnh có màu này sang đỉnh có màu kia. Vì thế, sau mỗi lần chuyển bi, tổng số bi có tại tất cả các đỉnh được tô màu xanh không thay đổi tính chẵn, lẻ. Suy ra có thể xếp được vào mỗi đỉnh A1 A2 , , A2k 1 một bi chỉ khi k 1 0 mod 2 hay n 3 mod 4 . Ngược lại, với n 4m 3, m N , thực hiện việc chuyển bi theo cách sau đây chẳng hạn: Lần lượt, với mỗi k 1, 2, ,2m 1 ở bước thứ 1 ta làm như sau: Lấy 2 bi ở A0 , chuyển chúng qua các đỉnh A1, A2 , , tới đỉnh A2k thì dừng lại. Sau bước thứ 2m 1, tại đỉnh A0 sẽ có 1 bi, tại mỗi đỉnh A2 , A4 , , A4m 1 đều có 2 bi, còn tại các đỉnh A1, A3 , , A4m 3 đều không có bi. Sau đó lần lượt với mỗi k 1, 2, , 4m 1 ở bước thứ k ta làm như sau: Lấy 1 bi ở A4k chuyển sang A4k 1 , đồng thời lấy 1 bi ở A4k 2 chuyển sang A4k+3 (quy ước coi A0 là A4m 4 )- Sau bước thứ m + 1, tại mỗi điểm A1, A3 , , A4m 3 sẽ có 1 bi. Vậy tất cả giá trị n 3 phải tìm là n 1 mod 4 . Trang 17
8. Bài toán 20. 23: Từ bảng Hãy chọn n số sao cho không có hai số nào đứng trong cùng một dòng và không có 2 số nào nằm trong cùng một cột của bảng. Tính tổng n sổ đã chọn. Hướng dẫn giải Kí hiệu aij là số ở hàng thứ i, cọt thứ j và để ý đến cấu tạo của bảng thì ta có: aij i 1 n j Muốn có n số thoả mãn đầu bài, ta chỉ việc lấy n số sau: a ,a , ,a trong đó α là số thứ tự chỉ cột và α α nếu i j. 1 1 2 2 n n i i j Như vậy nếu hoán vị các αi cho nhau, ta được tất cả n! cách chọn Muốn có cách chọn khác ta chỉ việc hoán vị αi và α j cho nhau mà phép hoán vị không làm thay đổi tổng của hai số đã cho, nên mọi cách chọn đều có chung một tổng. Gọi tổng của n chữ số đó là S ta có: S (1 1)n 1 2 1 n 2 n 1 n n S 0n n 2n n 1 n 1 2 n n n 1 Mà 1 2 n 1 2 n 2 n n 1 n n2 1 Nên S 1 2 n 1 n 2 2 Bài toán 20. 24: Tồn tại hay không một cách xếp 100 số nguyên: 51, 52, , 149, 150 vào trong một lưới vuông gồm 10 hàng 10 cột (mỗi ô vuông một số) sao cho nếu a và b là hai số đứng kề nhau trên một hàng hoặc trên một cột thì ít nhất một trong hai phương trình x2 ax b 0, x2 bx a 0 có nghiệm nguyên? Hướng dẫn giải Đặt S 51; 52 : ; 150. Giả sử a, p S; p nguyên tố. Khi đó: Nếu phương trình x2 a x p 0 có nghiệm nguyên, thì theo định lý Vi-ét, cả hai nghiệm x1,x2 của nó đều nguyên và dương; hơn nữa, do p là số nguyên tố, Trang 19
9. chứa ít nhất k hòn đá, do giả thiết k là số bé nhất các hòn đá trong một hàng hay cột bất kì. Với 1999 - k ô trống của cột này, tương ứng với một ô trống, để thoả mãn điều kiện đã nêu, hàng chứa ô trống phải chứa ít nhất 1999 - k hòn đá. Vậy tổng số các hòn đá ít nhất phải là: 2 2 2 2 1999 1999 k 1999 k 2 k 1998000,5 2 2 Tóm lại, số cần tìm là 1998001. Bài toán 20. 26: Một khối bằng gạch có dạng hình của một tam cấp gồm ba bậc có bề rộng là 2 được làm từ 12 khối hình lập phương đơn vị. Hãy xác định số nguyên n sao cho ta có thể dựng một khối lập phương cạnh n từ các khối bằng gạch (dạng tam cấp) ấy. Hưởng dẫn giải Thể tích trọn viên gạch (dạng tam cấp) bằng 12, nên điều kiện ắt có là cạnh của hình lập phương phải là bội của 6. Hai viên gạch có thể gắn với nhau dễ dàng để tạo thành một hình hộp chữ nhật kích thước 2 x 3 x 4 , và hình hộp chữ nhật này có thể xếp thành hàng để tạo thành một hình lập phương cạnh 1 hay thành một hình lập phương bất kì có cạnh là bội của 12. Đảo lại, ta sẽ chứng minh rằng: Một hình lập phương cạnh n = 6 chỉ có thể tạo thành theo điều kiện bài toán nếu  chẵn. Thật vậy, giả sử một hình lập phương như thế được tạo xong, thế thì ta đã sử dụng m = n3 /12 = 183 viên gạch (dạng tam cấp). Ta chuyển hình lập phương này vào trong góc phần tám x, y, z 0 của hệ trục toạ độ trong không gian với một đỉnh của hình lập phương nằm tại gốc O 0, 0, 0 .Tô màu mỗi cạnh của hình lập phương đơn vị i, i 1 x  j,i 1 x k, k 1 bằng một trong tám màu, tuỳ theo tính chẵn lẻ của bộ ba i, j, k . Trong mỗi viên gạch, tất cả tám màu đều có sáu trong tám mày ấy xuất hiện chỉ trong một hình lập phương đơn vị, và mỗi một trong hai màu còn lại có mặt trong ba hình lập phương đơn vị. Ta chọn một trong tám màu và gọi p là số viên gạch mà trong đó màu này xuất hiện ba lần. Trong hình lập phương có m viên gạch, màu này xuất hiện cả thảy Trang 21
10. Mỗi vòng tròn trên biểu đồ biểu diễn một học sinh x và con số trong vòng tròn biểu diễn f(x). số nằm trên các cung tròn thì biểu diễn số lần 2 học sinh kề nhau vỗ vào tay nhau. Chọn n = 499, ta có được ví dụ thoả mãn bài toán. Bài toán 20. 28: Cho n 1là một số nguyên. Một con đường từ 0,0 tới n,n trong mặt phẳng xOy được định nghĩa là một chuỗi các di chuyển liên tiếp của đơn vị sang phải (di chuyển này được kí hiệu bởi E) hay lên trên (di chuyển này được kí hiệu bởi N), mọi di chuyển được thực hiện trong nửa mặt phẳng x y . Một bước nhảy trên con đường là sự kết hợp của hai di chuyển liên tiếp có dạng EN. Chứng minh rằng số các con đường từ 0,0 đến n,n mà chứa đúng s bước nhảy n s 1 là bằng 1 C s-1C s-1 s n-1 n Hướng dẫn giải Một con đường với s bước nhảy từ 0,0 đến n,n được gọi là một con đường kiểu 1 n, s . Cho f n, s là số con đường kiểu n, s và đặt g n, s C s-1C s-1 s n-1 n Ta sẽ chứng minh bằng quy nạp theo n rằng (n, s) g(n, s) với s 1, 2, , n . Dễ dàng thấy rằng: f (1 , 1) 1 g( 1, 1 ), f ( 2 , 1 ) 1 g( 2 , 1 ), f ( 2 , 2 ) 1 g( 2 , 2 ). Cho n 2 và giả sử rằng (m, s) g(m, s) với 1 s m n . Rõ ràng là f (n 1, 1) g(n 1, 1) . Ta sẽ chứng minh rằng f (n 1, s 1) g(n 1, s 1) với1 s n Ta nói một con đường kiểu n, s và một con đường kiểu n 1, s 1 là liên đới với nhau nếu con đường sau thu được từ con đường trước bằng cách hoặc nhét thêm vào con đường thứ nhất một cặp EN giữa hai di chuyển liên tiếp có dạng (E, E), (N, N) hay (N, E), hoặc thêm vào một cặp EN ở cuối con đường. Ta cũng nói rằng con đường kiểu n, s + 1 và con đường kiểu n 1, s 1 là liên đới nếu con đường dài hơn có được từ con đường ngắn hơn bằng cách thêm một cặp EN vào giữa (E, N). Trang 23
11. khác nhau i, j (không phải X) thi đấu ở vòng i j (mod 2N 1) . Cho i và X đấu nhau ở vòng 2i mod 2N 1 . Dễ dàng kiểm tra rằng cách sắp xếp như vậy thoả mãn yêu cầu. Bây giờ ta xét trường hợp n = 7 . Gọi S là tập hợp lớn nhất gồm các cầu thủ mà không có hai người nào trong đó đấu với nhau, gọi S' là tập hợp các đấu thủ còn lại. Chọn A trong S' là một người đã chơi với vài đấu thủ trong S. Giả sử S =m , ta có S ' 18 m . Ta sẽ chứng minh rằng A đã chơi nhiều nhất là với m 2 phần tử của S. Giả sử điều ngược lại xảy ra. Mỗi đấu thủ đã chơi 7 trận, do tất cả các phần tử của s đều có chơi với các phần tử của S' nên đã có 7m trận diễn ra giữa các phần tử của S và các phần tử của S'. Nếu mọi phần tử của S' đã chơi với m 1hay nhiều hơn các phần tử của S thì có ít nhất 18 m m 1 trận diễn ra giữa các phần tử của S và các phần tử của S', suy ra 18 m m 1 7m , m2 12m 18 0, do đó m 10 . Rõ ràng không thể có m 10 thì do A chỉ chơi có 7 trận nên anh ta đã chơi ít hơn m - 2 phần tử của S'. Vì vậy, ta có thề tìm được B và C thuộc S sao cho A không chơi với B hay C. Vì A không thuộc S và S lớn nhất như đã nói trên nên phải có D thuộc S là người đã chơi với A. Như thế A, B, C, D là 4 người cần tìm mà trong số họ chỉ chơi có một trận (A với D). Bài toán 20. 30: một cuộc họp có 12k người, mỗi người trao đổi lời chào với đúng 3k + 6 người khác. Với hai người bất kì nào đó, số người trao đổi lời chào với cả hai người này là giống nhau. Hỏi có bao nhiêu người tham dự cuộc họp? Hướng dẫn giải Với hai người bất kì, ta gọi n là số cố định những người khác có trao đỗi lời chào với cả hai. Xét một người đặc biệt a. Gọi B là tập hợp những người có trao đồi lời chào với a, và C là tập hợp những người không trao đổi lời chào với a. Thế thì có 3k + 6 người trong B và 9k 7 người trong C. Với một người b bất kì trong B, thì người có trao đổi lời chào với a và b phải thuộc B. Như thế b đã trao đổi lời chào với n người trong B, và như thế với 3k 5 n người trong C. Trang 25
12. Thật vậy nếu H nằm ngoài đoạn thẳng đó và A2,3 gần H hơn A1,3 thì rõ ràng khoảng cách từ A2,3 tới A1 còn nhỏ hơn A1,2 H . Bây giờ giả sử rằng qua A1,2 còn có đường thẳng a 4 . Khi đó a 4 phải cắt a, tại một điểm A3,4 , điểm này phải nằm trên một trong hai tia có gốc H của đường thẳng a3 . Giả sử nó nằm trên tia chứa điểm A2,3 thì rõ ràng khoảng cách từ A2,3 tới a 2 nhỏ hơn A1,2 H . Vô lý!. Bài toán 20. 32: Cho một đa giác đều 2007 đỉnh. Tìm số nguyên dương k nhỏ nhất thoả mãn tính chất: Trong mỗi cách chọn k đỉnh của đa giác luôn tồn tại 4 đỉnh tạo thành một tứ giác lồi mà 3 trong số 4 cạnh của nó là 3 cạnh của đa giác đã cho. Hướng dẫn giải Gọi các đỉnh của đa giác đều đã cho là A 1 A 2 , , A2007 Chú ý rằng tứ giác (tạo nên từ 4 trong số các đỉnh của đa giác) có 3 cạnh là 3 cạnh của đa giác khi và chỉ khi 4 đỉnh của tứ giác đó là 4 đỉnh liên tiếp của đa giác. Gọi A là tập các đỉnh: [A1, A2 , A3 , A5 , A6 , A7 , , A2003 , A2006 ] (bỏ đi các đỉnh A4i ,i 1, 501 và A2007 ). Hiển nhiên A 1505 và trong A không chứa 4 đỉnh liên tiếp nào của đa giác. Dễ thấy, mọi tập con của A đều không chứa 4 đỉnh liên tiếp của đa giác. Vậy k 1506. Ta sẽ chứng minh mọi cách chọn 1506 đỉnh tuỳ ý của đa giác thì sẽ tồn tại 4 đỉnh liên tiếp của đa giác trong 1506 đỉnh đó. Thật vậy, giả sử T là một tập gồm 1506 đỉnh tuỳ ý của đa giác. Phân hoạch tập các đỉnh của đa giác thành các tập hợp. B1 A1, A2 , A3 , A4; B2 A5 , A6 , A7 , A8; B501 A2001, A2002 , A2003 , A2004; B502 A2005 , A2006 , A2007 Giả sử T không chứa 4 đỉnh liên tiếp của đa giác. Lúc đó với mỗi i 1, , 501, tập Bi không thuộc T, tức là mỗi tập Bi đó sẽ có ít nhất một đỉnh không thuộc T. Khi đó T 3 x 502 1506 . Do T 1506 nên B502  T và mỗi tập Bi i=1,501 ó đúng 3 phần tử thuộc T. Ta có A2005 , A2006 , A2007 T suy ra Ai T A2 , A3 , A4 T A5 T A6 , A7 , A T A2002 , A2003 , A2004 T Trang 27