Bài tập Toán Lớp 11 - Cực trị tổ hợp (Có hướng dẫn)

Nội dung text: Bài tập Toán Lớp 11 - Cực trị tổ hợp (Có hướng dẫn)

1. CỰC TRỊ TỔ HỢP MỘT SỐ DẠNG TOÁN CỰC TRỊ TỔ HỢP, RỜI RẠC VÀ ĐỊNH HƯỚNG CÁCH GIẢI Bài toán cực trị trong tổ hợp và rời rạc thường xuất hiện trong các kì thi học sinh giỏi và đây thường là bài khó dùng để phân loại học sinh. Các bài toán này thường không có một thuật giải cụ thể. Lời giải có được chủ yếu dựa vào năng lực tư duy sáng tạo của học sinh. Nhằm giúp học sinh có được cơ sở để giải các bài toán về cực trị trong tổ hợp và rời rạc, chúng tôi hệ thống một số bài toán và một số định hướng cách giải quyết các bài toán về cực trị trong tổ hợp và rời rạc. Trong bài viết này, chúng tôi đưa ra một số bài toán thường gặp và định hướng giải các bài toán đó. Bài toán 1. Tìm số nguyên dương k nhỏ nhất (lớn nhất) sao cho mọi tập A mà A= k đều có tính chất T nào đó. Với bài toán này, chúng ta thường xét một tập A có tính chất đặc biệt nào đó sao cho A= m và A không thỏa tính chất T, từ đó suy ra được kmin ³m+1. Tiếp theo ta chứng minh mọi tập A mà A=m+1 đều có tính chất T, từ đó ta tìm được kmin =m+1. Để chứng minh mọi tập A mà A=m+1 đều có tính chất T thì ta có thể sử dụng nguyên lí Dirichlet hoặc xây dựng Ví dụ 1. Gọi A là tập tất cả các số tự nhiên lẻ không chia hết cho 5 và nhỏ hơn 30. Tìm số k nhỏ nhất sao cho mỗi tập con của A gồm k phần tử đều tồn tại hai số chia hết cho nhau? Lời giải. Ta có: A={1,3,7,9,11,13,17,19,21,23,27,29}, A=12 1
2. CỰC TRỊ TỔ HỢP Xét tập A0 = {9,11,13,17,19,21,23,29} Dễ thấy hai phần tử bất kì thuộc A0 thì không chia hết cho nhau. Từ đó ta suy ra được k³ 9. Ta chứng minh k= 9 thỏa đề bài. Xét S là một tập con bất kì của A và S= 9. Xét ba cặp {21,7},{27,9},{1,11}, ta thấy mỗi cặp là bội của nhau. Nếu trong 3 cặp trên có ít nhất một cặp thuộc S thì bài toán được giải quyết Giả sử trong ba cặp trên không có cặp nào cùng thuộc S, do S= 9 nên S phải chữa một số trong mỗi cặp và chứa 6 số còn lại. Từ đó suy ra trong S phải có cặp {3;9} hoặc {3;27} và mỗi cặp này là bội của nhau. Hay nói cách khác trong S luôn tồn tại hai số chia hết cho nhau. Vậy kmin = 9. Nhận xét: Mẫu chốt trong bài toán trên là chúng ta phát hiện ra tập A0 để từ đó ta khẳng định được k³ 9 và dự đoán kmin = 9. Để tìm tập A0 , ta liệt kê hết các số trong A mà không có hai số nào là bội của nhau. Với bài toán này, việc tìm ra tập A0 khá đơn giản. Ví dụ 2. Cho tập A gồm 16 số nguyên dương đầu tiên. Hãy tìm số nguyên dương k nhỏ nhất có tính chất: Trong mỗi tập con có k phần tử của A đều tồn tại hai số phân biệt a,b sao cho a2+ b2 là số nguyên tố (VMO 2004). Lời giải. Giả sử k là số nguyên dương sao cho trong mỗi tập con có k phân tử của tập A đều tồn tại hai số phân biệt a,b sao cho a2+ b2 là số nguyên tố 2
3. CỰC TRỊ TỔ HỢP Ta xét tập T gồm các số chẵn thuộc tập A. Khi đó T= 8 và với mọi a,bTÎ ta có a2+ b2 là hợp số, do đó suy ra k³ 9. Xét các cặp số sau: A={1;4}È{3;2}È{5;16} È{6;15}È{7;12}È{8;13} È{9;10}È{11;14} Ta thấy tổng bình phương của mỗi cặp trên là một số nguyên tố. Xét T là một tập con của A và T= 9, khi đó theo nguyên lí Dirichlet T sẽ chứa ít nhất một cặp nói trên, hay nói cách khác trong T luôn tồn tại hai số phân biệt a,b sao cho a2+ b2 là số nguyên tố. Vậy kmin = 9. Chú ý: 1) Vì giả thiết a2+ b2 là số nguyên tố nên a2+ b2 không thể là số chẵn hay a,b phải khác tính chẵn, lẻ. Dựa vào đó ta xây dựng được tập T . 2) Để tìm được sự phân hoạch tập A thành hợp của 8 cặp rời nhau như trên ta làm như sau: 22 · Ta liệt kê tất cả các số a1ÎA,a2ÎA, ,a16 ÎA sao cho i+ ai ( i= 1,16 ) là số nguyên tố . Từ đó ta có được sự phân hoạch trên, sự phân hoạch trên không phải là duy nhất. Ví dụ 3. Cho một đa giác đều 2007 đỉnh . Tìm số nguyên dương k nhỏ nhất thảo 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 tứ giác là cạnh của đa giác đã cho (VMO 2007). Lời giải. Gọi các đỉnh của đa giác là A1,A2, ,A2007 . 3
4. CỰC TRỊ TỔ HỢP Ta thấy tứ giác có 4 đỉnh thuộc các đỉnh của đa giác có 3 cạnh trong 4 cạnh là 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. Xét tập hợp X={A1,A2,A3,A4, ,A2005,A2006}( bỏ đi các đỉnh A4i và A2007 ). Ta có X= 1505 và X không chứa 4 đỉnh liên tiếp của đa giác. Từ đó suy ra k³ 1506 . Ta chứng minh kmin = 1506 . Gọi T là tập hợp các điểm thuộc đỉnh của đa giác và T= 1506 . Ta xét 2007-1506=501 đỉnh còn lại. Các đỉnh này sẽ chia đường tròn ngoại tiếp é2007 ù đa giác thành 501 cung, do đó sẽ có một cung chứa ít nhất êú+14= ë501 û đỉnh liên tiếp của đa giác. Dĩ nhiên 4 đỉnh này thuộc T và là 4 đỉnh liên tiếp của đa giác đã cho. Vậy kmin = 1506 . Chú ý: 1) Để chứng minh kmin = 1506 ta có thể làm theo cách sau Đặt T1={A1,A2,A3,A4}, T2={A5,A6,A7,A8} . T501={A2001,A2002,A2003,A2004},T502={A2005,A2006,A2007} Nếu có Ti ÌT,i=1,501 thì bài toán được chứng minh Giả sử Ti ËT,i=1,501, vì T= 1006 nên TÇTi =3, "i=1,501 và T502 Ì T Vì A2005,A2006,A2007 ÎT nên A1ÏTÞA2,A3,A4ÎTÞA5ÏT ta suy ra được A2001ÏTÞA2002,A2003,A2004 ÎT. Do đó A2002,A2003,A2004,A2005 ÎT. Bài toán được chứng minh. 2) Mẫu chốt bài toán trên là chúng ta đưa ra được nhận xét: Đa giác thỏa yêu cầu bài toán khi và chỉ khi 4 đỉnh của tứ giác là 4 đỉnh liên tiếp của đa 4
5. CỰC TRỊ TỔ HỢP MỘT SỐ DẠNG TOÁN CỰC TRỊ TỔ HỢP, RỜI RẠC VÀ ĐỊNH HƯỚNG CÁCH GIẢI Bài toán cực trị trong tổ hợp và rời rạc thường xuất hiện trong các kì thi học sinh giỏi và đây thường là bài khó dùng để phân loại học sinh. Các bài toán này thường không có một thuật giải cụ thể. Lời giải có được chủ yếu dựa vào năng lực tư duy sáng tạo của học sinh. Nhằm giúp học sinh có được cơ sở để giải các bài toán về cực trị trong tổ hợp và rời rạc, chúng tôi hệ thống một số bài toán và một số định hướng cách giải quyết các bài toán về cực trị trong tổ hợp và rời rạc. Trong bài viết này, chúng tôi đưa ra một số bài toán thường gặp và định hướng giải các bài toán đó. Bài toán 1. Tìm số nguyên dương k nhỏ nhất (lớn nhất) sao cho mọi tập A mà A= k đều có tính chất T nào đó. Với bài toán này, chúng ta thường xét một tập A có tính chất đặc biệt nào đó sao cho A= m và A không thỏa tính chất T, từ đó suy ra được kmin ³m+1. Tiếp theo ta chứng minh mọi tập A mà A=m+1 đều có tính chất T, từ đó ta tìm được kmin =m+1. Để chứng minh mọi tập A mà A=m+1 đều có tính chất T thì ta có thể sử dụng nguyên lí Dirichlet hoặc xây dựng Ví dụ 1. Gọi A là tập tất cả các số tự nhiên lẻ không chia hết cho 5 và nhỏ hơn 30. Tìm số k nhỏ nhất sao cho mỗi tập con của A gồm k phần tử đều tồn tại hai số chia hết cho nhau? Lời giải. Ta có: A={1,3,7,9,11,13,17,19,21,23,27,29}, A=12 1