Đề tài 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

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 PHẦN 1. LÍ DO CHỌN ĐỀ TÀ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. Đó là lí do mà chúng tôi chọn đề tài: “ Một số dạng toán cực trị trong tổ hợp hợp, rời rạc và định hướng cách giải”. PHẦN 2.THỰC TRẠNG TRƯỚC KHI THỰC HIỆN ĐỀ TÀI 1. Thuận lợi: Học sinh đã được tiếp cận các bài toán về cực trị trong tổ hợp và rời rạc cũng như nắm được một số lời giải các bài toán đó. 2. Khó khăn: Học sinh chưa được tiếp cận một cách hệ thống các bài toán liên quan đến cực trị trong tổ hợp và rời rạc. Đồng thơi học sinh chưa có được định hướng để giải các bài toán đó. PHẦN 3. NỘI DUNG ĐỀ TÀI Trong phần 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à đề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 và A không thỏa tính chất T, từ đó suy ra được . Tiếp theo ta chứng minh mọi tập mà đều có tính chất T, từ đó ta tìm được . Để chứng minh mọi tập mà đề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ó: Xét tập Dễ thấy hai phần tử bất kì thuộc thì không chia hết cho nhau. Từ đó ta suy ra được . Ta chứng minh thỏa đề bài. Xét là một tập con bất kì của và . Xét ba cặp , 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 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 hoặc 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 . 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 để từ đó ta khẳng định được và dự đoán . Để tìm tập , 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 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 nhỏ nhất có tính chất: Trong mỗi tập con có phần tử của A đều tồn tại hai số phân biệt sao cho là số nguyên tố (VMO 2004). Lời giải. Giả sử là số nguyên dương sao cho trong mỗi tập con có phân tử của tập A đều tồn tại hai số phân biệt sao cho là số nguyên tố Ta xét tập T gồm các số chẵn thuộc tập A. Khi đó và với mọi ta có là hợp số, do đó suy ra . Xét các cặp số sau: 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à , khi đó theo nguyên lí Dirichlet 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 sao cho là số nguyên tố. Vậy . Chú ý: 1) Vì giả thiết là số nguyên tố nên không thể là số chẵn hay phải khác tính chẵn, lẻ. Dựa vào đó ta xây dựng được tập . 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: Ta liệt kê tất cả các số sao cho ( ) 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 nhỏ nhất thảo mãn tính chất: Trong mỗi cách chọn đỉ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à . 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 ( bỏ đi các đỉnh và ). Ta có và X không chứa 4 đỉnh liên tiếp của đa giác. Từ đó suy ra . Ta chứng minh . Gọi là tập hợp các điểm thuộc đỉnh của đa giác và . Ta xét đỉnh còn lại. Các đỉnh này sẽ chia đường tròn ngoại tiếp đa giác thành cung, do đó sẽ có một cung chứa ít nhất đỉ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 . Chú ý: 1) Để chứng minh ta có thể làm theo cách sau Đặt . Nếu có thì bài toán được chứng minh Giả sử , vì nên và Vì nên ta suy ra được . Do đó . 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 giác . Từ đó chúng ta xây dựng tập X không thỏa yêu cầu bài toán. Khi xây dựng tập X ta chú ý, cần xây dựng X sao cho trong X không chứa 4 đỉnh liên tiếp và X có số phần tử lớn nhất. Ví dụ 4. Trong một cuộc hội thảo cứ người thì có đúng một người quen chung. Tìm số người quen lớn nhất của một người. Lời giải. Từ giả thiết bài toán, ta suy ra được: Mỗi người có ít nhất một người quen. Giả sử có () người đôi một quen nhau. Khi đó sẽ có người thứ là quen với người , suy ra đôi một quen nhau. Bằng cách xây dựng như vậy ta có được ít nhất người đôi một quen nhau. Giả sử có người và n quen với ít nhất 1 trong người , ta xét các trường hợp sau: TH 1: Số người quen của n không nhỏ hơn 2. Giả sử n quen với trong . Khi đó nhóm gồm 10 người có 2 người quen chung là , suy ra vô lý. TH 2: n quen đúng 1 người trong 11 người . Giả sử không quen . Khi đó có một người quen chung là và Suy ra p có không ít hơn 2 người quen trong . Ta đưa về trường hợp trên và dẫn đến điều vô lí. Vậy số người quen nhiều nhất của một người là . Bài toán 2: Tìm số phần tử lớn nhất (nhỏ nhất ) của tập A gồm các phần tử có tính chất T. Để giải bài toán này, chúng ta thường thực hiện theo cách sau Đặt , bằng các lập luận ta chứng minh (). Sau đó ta xây dựng một tập thỏa tính chất T và . Chú ý: Nếu trong một bài toán liên quan đến một phần tử thuộc giao , ta có thể đi đếm bộ bằng hai cách. Từ đó ta thiết lập được các bất đẳng thức. Ví dụ 5. Cho A là tập hợp gồm 8 phần tử. Tìm số lớn nhất các tập con gồm 3 phần tử của A sao cho giao của hai tập bất kì trong các tập con này không phải là tập gồm hai phần tử. Lời giải. Gọi là số tập con của A thỏa : Giả sử có phần tử thuộc vào 4 tập trong các tập (chẳng hạn thuộc 4 tập ). Khi đó: Mặt khác với thì nên Suy ra Do đó: vô lí. Như vậy mỗi phần tử thuộc tập A thì sẽ thuộc nhiều nhất ba tập trong số các tập . Khi đó, suy ra . Xét và các tập Là các tập con gồm ba phần tử của A và . Vậy số tập con lớn nhất là 8. Ví dụ 6. Trong một cuộc thi có 11 thí sinh tham gia giải 9 bài toán. Hai thí sinh bất kì giải chung với nhau không quá 1 bài. Tìm lớn nhất để mọi bài toán có ít nhất k thí sinh giải được. Lời giải. Gọi là thí sinh thứ i và tập các bài toán là Theo đề bài ta có: . Đặt là số thí sinh giải được bài . Ta đi đếm bộ , trong đó . Ta có số bộ này chính bằng: Mặt khác: số bộ này lại bằng . Do đó ta có: Suy ra Với . Giả sử tồn tại , suy ra vô lí. Suy ra Do đó, tồn tại sao cho Giả sử và Nếu tồn tại để Nên tồn tại một phần tử của thuộc ít nhất tập . Suy ra tồn tại một phần tử thuộc nhiều hơn 5 tập , vô lí. Suy ra vô lí. Do đó . Với ta chỉ ra như sau: Quy ước : số 1 là thí sinh giải được bài đó số 0 là thí sinh không giải được bài đó. 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 Ví dụ 7. Trong một kì thi, 8 giám khảo đánh giá từng thí sinh chỉ bằng hai từ đúng hoặc sai. Biết rằng với bất kì hai thí sinh nào cũng nhận được kết quả như sau: có hai giám khảo cùng cho đúng; có hai giám khảo với người thứ nhất cho đúng và người thứ hai cho sai; có hai giam khảo với người thứ nhất cho sai, người thứ hai cho đúng; cuối cùng có hai giám khảo cùng cho sai. Hỏi số thí sinh lớn nhất có thể bằng bao nhiêu? Lời giải. Gọi n là số thí sinh. Ta xét hình chữ nhật gồm 8 hàng và n cột sao cho ô vuông ở hàng thứ I và cột thứ j cho số 0 (số 1) nếu vị giám khảo thứ đánh giá thí sinh thứ j sai (đúng). Từ giả thiết đề bài ta suy ra bất cứ hai cột nào của bảng cũng có tính chất: 8 hàng của hai cột này chứa các cặp số va mỗi cặp số xuất hiện hai lần. Ta chứng minh, không tồn tại bảng gồm 8 cột có tính chất trên. Giả sử tồn tại một bảng như thế. Do trong một cột bất kí, ta đổi số 0 thành số 1 và ngược lại thì tính chất trên vẫn được bảo toàn. Vì vậy ta có thể giả sử hàng đầu tiên gồm các số 0. Gọi là số các số 0 nằm ở hàng thứ . Ta có tổng các số 0 là , hơn nữa số lần xuất hiện củacặp là . Mặt khác số này cũng bằng Vì nên ta có . Từ đó suy ra: Do vậy: vô lí. Nên ta suy ra số thí sinh nhiều nhất chỉ có thể là 7. Bảng sau chứng tỏ có thể có 7 thí sinh. 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 Ví dụ 8. Cho bảng ô vuông kích thước (bảng gồm 2000 hàng và 2001 cột). Hãy tìm số nguyên dương lớn nhất sao cho ta có thể tô màu ô vuông con của bảng thỏa điều kiện: hai ô vuông con nào được tô màu cũng không có đỉnh chung (VMO 2001). Lời giải. Kí hiệu là ô vuông nằm ở hàng thứ và cột thứ . Kí hiệu là số ô vuông được tô màu ở cách tô màu T. Xét một cách tô màu T thỏa yêu cầu bài toán Ta thấy nếu ô được tô màu thì các ô và các ô kề với nó trong cũng một hàng không được tô màu. Ta xét phép biến đổi sau đối với Xóa tất cả các ô mà lẻ và tô màu các ô . Khi thực hiện phép biến đổi trên ta thu được cách tô màu thỏa mãn đề bài và: Tất cả các ô nằm trên hàng thứ () đều không được tô màu. Từ điều kiện đề bài, suy ra trong một hàng có không quá 1001 ô được tô màu. Do đó . Vì vậy với mọi cách tô màu T thỏa yêu cầu bài toán. Ta xét cách tô màu sau: Tô các ô với . Ta thấy cách tô này thỏa yêu cầu bài toán và số ô được tô màu là . Vậy . Ví dụ 9. Trên một đường tròn cho 2011 điểm phân biệt. Giả sử trong số các điểm này có đúng k điểm được tô màu đen. Một cách tô màu được gọi là “tốt” nếu tồn tại ít nhất một cặp điểm màu đen sao cho phần trong của một trong hai cung đó tạo bởi hai điểm chứa đúng điểm của E. Tìm k nhỏ nhất sao cho mọi cách tô màu k của điểm của E đều “tốt”. Lời giải. Đặt . Ta sẽ xét theo Một cách tô tốt khi và chỉ khi tồn tại sao cho (*) Xét một tập . Ta sẽ chứng minh tồn tại thỏa (*) Thật vậy: với mỗi thì tồn tại sao cho : Mặt khác, mỗi được tính hai lần. Suy ra vô lí Suy ra là số tốt, do đó . Do nên Chọn Suy ra : (1) vô lí. Tương tự, từ (2) ta suy ra vô lí. Vậy . Chú ý: Để đánh giá () chúng ta có thể thiết lập các đẳng thức hoặc bất đẳng thức. Để thiết lập các đẳng thức chúng ta cần chú ý đến các bất biến. Ví dụ 10. Cho một bảng kích thước được điền các số tự nhiên từ đến theo quy tắc sau: Hàng thứ nhất ta điền các số từ 1 đến 2012 từ trái qua phải, ở hàng thứ hai ta đánh các số từ 2013 đến 4024 tuwg phải qua trái, các hàng tiếp theo được đánh theo kiểu zích zắc tương tự như trên. Hãy tìm các phủ kín bẳng trên bởi quân cơ Domino sao cho tổng của tích các số trên mỗi quân cờ Domino lớn nhất. Lời giải. Đặt . Gọi là hai số được ghi trên quân cờ Domino thứ với và với . Ta cần tìm giá trị nhỏ nhất của . Vì nên ta có: Mặt khác là các số tự nhiên khác nhau thuộc tập A nên và Suy ra . Đẳng thức xảy ra khi và chỉ khi là hai số tự nhiên liên tiếp. Vậy để S lớn nhất ta phủ các quân cơ Domino sao cho mỗi quân cờ chứa hai số tự nhiên liên tiếp. Ví dụ 11. Cho số nguyên dương n. Có n học sinh nam và n học sinh nữ xếp thành một hàng ngang, theo thứ tự tùy ý. Mỗi học sinh (trong số 2n học sinh vừa nêu) được cho một số kẹo bằng đúng số cách chọn ra hai học sinh khác giới với X và đứng ở hai phía của X. Chứng minh rằng tổng số kẹo mà tất cả 2n học sinh nhận được không vượt quá (VMO 2012). Lời giải. Gọi và là vị trí của n nam và n nữ trên hàng. Xét nam tại vị trí , ta thấy bên trái anh ta có vị trí, trong đó có vị trí là nam, vậy nên bên trái anh ta có nữ. Tương tự, bên phải anh ta có nữ. Vậy nam tại được cho kẹo. Tương tự, nữ tại vị trí được cho kẹo. Như vậy tổng số kẹo được cho bằng Chú ý là nên ta có Ngoài ra Thay vào biểu thức tính S, ta tìm được . Từ đó, ta đưa bài toán ban đầu về việc chứng minh bất đẳng thức: Ta có: Áp dụng công thức khai triển tổng Abel, ta có . Vậy bài toán được chứng minh. Ví dụ 12. Gọi hình chữ nhật (hoặc ) bị cắt bỏ một ô vuông ở góc được gọi là hình chữ nhật khuyết đơn (Hình 1). Hình chữ nhật ( hoặc ) bị cắt bỏ hai hình vuông nằm ở hai góc đối diện là hình chữ nhật khuyết kép (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 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 . Gọi là tổng số hình vuông và hình chữ nhật khuyết kép trong mỗi cách ghép nói trên. Tìm giá trị lớn nhất của (Vietnam TST 1993). Lời giải. Gọi là số hình chữ nhật khuyết đơn. Ta có đẳng thức về diện tích (1) Điền số 0 vào các ô với , ta thấy có số 0 được điền. Dựa vào hình (hình 3) ta thấy: Hình vuông và hình chữ nhật khuyết kép chứa đúng một số 0 Hình chữ nhật khuyết đơn chứa số 0 với hoặc . Suy ra (2) Từ (1) và (2) ta suy ra được: Suy ra . Ta xét cách ghép sau (hình 4) thỏa . (Hình 3) (Hình 4) Ví dụ 13. Gọi hình chữ nhật (hoặc ) là hình chữ nhật đơn và hình chữ nhật (hoặc ) bỏ đi hai ô vuông đơn vị ở hai góc đối diện là hình chữ nhật kép. Người ta ghép khít các hình chữ nhật đơn và các hình chữ nhật kép lại với nhau được một bảng hình chữ nhật . Tìm số nhỏ nhất các hình chữ nhật đơn có thể dùng để ghép (Vietnam TST 2010). Lời giải. Ta xét một hình chữ nhật thỏa yêu cầu bài toán. Gọi lần lượt là số hình chữ nhật đơn , và là số hình chữ nhật kép dùng trong cách phủ đó. Các ô ở hàng lẻ ta tô màu trắng, các ô ở hàng chẵn ta tô mau đen. NX 1: Dựa vào đẳng thức diện tích, ta có: (1) NX 2: Trên toàn bảng mỗi hình chữ nhật kép hoặc đều có các ô màu đen bằng các ô màu trắng. Hình chữ nhật đơn được ghép dọc nên số ô màu đen cũng bằng số ô màu trắng. Suy ra số hình chữ nhật ở các hàng được tô màu đen bằng số hình chữ nhật ở các hàng được tô màu trắng. Hơn nữa có tất cả hàng nên ta suy ra chẵn, cộng với đẳng thức (1) ta suy ra được chẵn. Hay nói cách khác ta có chẵn (2). Bây giờ ở tất cả các ô hàng thứ của hình chữ nhật ta điền các số () và là hiệu của tổng các số ghi trên ô màu trắng và tổng các số ghi trên ô màu đen của các hình chữ nhật đang xét. Ta có: Suy ra (trong đó là tổng tính trên tất cả các hình chữ nhật kép được dùng, tương tự cho các kí hiệu còn lại) Mặt khác tổng các số ghi trên hình chữ nhật là một số chẵn thuộc đoạn , mà là số chẵn nên ta có đánh giá sau . Ta có Do đó: (3). Tiếp theo ta xét hình chữ nhật , lấp luận về các hình chữ nhật được dùng tương tự như trên ta cũng xây dựng được bất đẳng thức (4). Từ (3) và (4) ta suy ra: (5) Theo (1) thì kết hợp với (5) ta có: Mà là số chẵn nên ta suy ra được: . Ta chứng minh tồn tại cách ghép chỉ cần dùng hình chữ nhật đơn. Hình dưới đây mô tả cách ghép một hình chữ nhật 10x16, trong đó: các hình chữ nhật khuyết được tô bằng 5 màu khác nhau (đỏ, hồng, xanh lam, xanh lá cây, xanh đậm) để dễ dàng phân biệt; trên hình các khối được tô màu xanh lá mạ là các hình chữ nhật đơn chắc chắn phải dùng, các khối màu vàng thì tùy trường hợp, có thể là hình chữ nhật đơn mà cũng có thể là hình chữ nhật khuyết. Hình chữ nhật có thể được tạo thành từ hình trên bằng quy tắc sau: - Thêm các dìng bằng cách chèn vào giữa mỗi khối ở trên các hình có dạng: Mỗi lần ghép như thế thì ta có thêm được hai hàng mới, do 2010 chia hết cho 2 nên khi thực hiện việc này liên tiếp một cách thích hợp thì khối này sẽ tăng về chiều dài, tạo thành các khối mới có kích thước và ở mỗi khối như vậy, ta chỉ dùng đúng 2 hình chữ nhật màu xanh lá mạ. - Thêm cột bằng cách lặp lại các khối 1, 2 , 3, 4 ở trên hình (chú ý tính tuần hoàn giữa các khối: (1) tương ứng với (3), (2) tương ứng với (4)). Như thế thì ta cần phải có tất cả 502 khối dành cho 2008 cột. Đồng thời, ở khối đầu tiên và khối cuối cùng, ta cần dùng thêm một hình chữ nhật đơn màu vàng, các khối ở giữa thì dùng các hình chữ nhật khuyết màu vàng. Tức là: ở hai khối đầu tiên và cuối cùng, ta cần dùng 3 hình chữ nhật đơn, các khối ở giữa chỉ cần dùng 2 hình chữ nhật đơn thôi. Khi đó, tổng số hình chữ nhật đơn cần dùng là: 500.2 + 2.3 =1006 Xoay hình chữ nhật 2010× 2008 lại, ta được hình chữ nhật 2008× 2010 cần phải ghép, hình chữ nhật đó có đúng 1006 hình chữ nhật đơn thỏa mìn đề bài. Do đó, cách ghép trên thỏa yêu cầu bài toán. Vậy giá trị nhỏ nhất các hình chữ nhật đơn cần dùng là 1006. Ví dụ 14. Trên một bàn cờ đặt vào k hình sao cho không thể đặt thêm một hình nào nữa (các hình rời nhau). Tìm số lớn nhất các ô tự do còn lại. Lời giải. Đặt và là số ô tự do còn lại của bàn cờ. Ta chứng minh ô. Gọi là số ô tự do nằm trong bảng là số ô tự do nằm ở trên biên (không tính ở góc) là số ô tự do nằm ở góc là số ô tự do của bảng. Ta có: . Gọi là số hình nằm trên bảng, là số hình nằm dính biên Suy ra Ta đếm số cặp “ số ô tự do – biến của ô đó dính với 1 hình chữ nhật ” Số cặp này bằng Mặt khác: số cặp này không vượt quá nên ta có: (1) Do hai ô tự do nằm trên biên liên tiếp thì bị tách bởi 1 hình chữ nhật nên (2). Lấy (1)+(2) ta được: Suy ra Do nên ta suy ra được Với . Ta xét cách ghép sau đây sẽ xảy ra dấu “=”. Ví dụ 15. Cho 2006 điểm phân biệt trong không gian, không có bốn điểm nào thẳng hàng. Số k gọi là số tốt nếu ta có thể điền lên mỗi đoạn thẳng nối hai điểm trong 2006 điểm đã cho một số tự nhiên không vượt quá k sao cho với mọi tam giác có ba đỉnh trong 2006 điểm đa cho thì có hai cạnh được điền hai số bằng nhau và cạnh còn lại thì được điền số lớn hơn. Tìm số tốt có giá trị nhỏ nhất (TST Việt Nam 2006). Lời giải. Ta sẽ chứng minh số tốt nhỏ nhất là 10 . Trước hết ta định nghĩa một số khái niệm như sau: Một cách điền các số tự nhiên không vượt quá k lên các đoạn thẳng nối n điểm trong không gian, không có bốn điểm nào đồng phẳng, là một cách điền tốt nếu với mọi tam giác có ba đỉnh trong n đỉnh đã cho thì có hai cạnh được điền hai số bằng nhau và cạnh còn lại được điền số lớn hơn, và khi đó ta gọi k là số n-tốt. Ký hiệu số n-tốt có giá trị nhỏ nhất là . Ta chứng minh . Trước hết, ta chứng minh (1). Với ta có nên suy ra Để chứng minh (1) ta chứng minh không phải là số n-tốt và là số n – tốt. Giả sử là số n – tốt, khi đó sẽ tồn tại cách điền các số tự nhiên không vượt quá lên các cạnh của n điểm là cách điền tốt. Ta thấy không có tam giác nào có ba đỉnh trong các điểm đã cho có hai cạnh bằng nhau được đánh số , suy ra hai cạnh được điền thì không có đầu mút chung. Do đó ta có thể kí hiệu n điểm đã cho là , trong đó các cạnh được đánh số là và các điểm còn lại là . Ta xét các điểm ( Do nên có ít nhất điểm được chọn, ta gọi m là số điểm được chọn) và các đoạn thảng nối các điểm đó. Do không có cạnh nào được đánh số nên : Vô lí do . Vậy điều giả sử ở trên là sai, suy ra . Tiếp theo ta chứng minh là số n - tốt Xét n điểm . Ta xét cách điền số như sau: Ta điền số 0 lên các cạnh mà Với các điểm ta có thể điền các số từ 0 đến lên các đoạn nối nó sao cho là một cách điền tốt với các điểm đó nên cũng có thể điền các số từ 1 đến sao cho là một cách điền tốt với các điểm đó (2) Tương tự ta cũng có thể điền các số từ 1 đến lên các cạnh nối các điểm sao cho đó là một cách điền tốt với các điểm đó (3) Ta chứng minh cách điền trên là cách điền tốt đối với n điểm đã nêu. Xét tam giác . Nếu , khi đó theo (2) và (3) ta có tam giác có hai cạnh được điền hai số bằng nhau và cạnh còn lại được điền số lớn hơn Nếu trong ba số có hai số cùng tính chẵn lẻ và khác tính chẵn lẻ với số còn lại, không mất tính tổng quát, ta giả sử Khi đó, theo cách điền trên thì các cạnh được điền số 0, cạnh còn lại điền số lớn hơn 0. Suy ra là số n – tốt Vậy ta có: Từ đó suy ra : Ta tính . Ta có số 0 không phải là 4-tốt và số 1 là 4 - tốt với cách điền sau Suy ra . Vậy . Bài tập Bài 1. Giả sử là tập con của tập thỏa mãn: tích 3 phần tử bất kỳ thuộc không là số chính phương. Tìm số phần tử lớn nhất của . Bài 2. Cho tập hợp P gồm n điểm phân biệt trên mặt phẳng (),trong đó không có 3 điểm nào thẳng hàng. Mỗi cặp điểm thuộc P được nối bởi một đoạn thẳng tô màu đỏ hoặc tô màu xanh.Tìm số nhỏ nhất các đoạn thẳng tô màu đỏ sao cho bất kì tam giác nào với 3 đỉnh thuộc P đều có ít nhất một cạnh màu đỏ. Bài 3. Trong không gian cho 2006 điểm mà trong đó không có 4 điểm nào đồng phẳng. Nối tất cả các cặp điểm đã cho bởi các đoạn thẳng. Số tự nhiên được gọi là tốt nếu ta có thể gán cho mỗi đoạn thẳng một số tự nhiên sao cho tam giác tạo bởi 3 trong số các điểm đã cho đều có hai cạnh bằng nhau và cạnh còn lại được gán một số lớn hơn hai số đó. Tìm số tốt nhỏ nhất. Bài 4. Trong một giải bóng đá có 20 đội tham gia, thi đấu vòng tròn một lượt (kết thúc giải mỗi đội đá với mỗi đội còn lại đúng một trận). Tìm số k lớn nhất sao cho sau mỗi k vòng đấu (mỗi đội đấu k trận) luôn tìm được 3 đội đôi một chưa đá với nhau. Bài 5. Cho một bảng ô vuông 5x5. Gọi A là tập hợp các đỉnh của các hình vuông đơn vị trừ các đỉnh của bảng. Hỏi ta có thể chọn được từ A nhiều nhất bao nhiều điểm để trong số các điểm đã được chọn không có ba điểm nào lập thành một tam giác cân. Bài 6. Trong mặt phẳng, cho tập hợp A gồm điểm phân biệt được đánh số từ 1 đến sao cho ba điểm bất kì nào trong chúng cũng không thẳng hàng. Một tứ giác (lồi hoặc lõm) được gọi là "đẹp" nếu các đỉnh của nó thuộc A và được đánh số bằng 4 số thỏa mãn một trong hai điều kiện sau: i) Đó là 4 số tự nhiên cách nhau 2010 đơn vị. ii) Đó là 4 số tự nhiên liên tiếp và nếu trong đó có chứa số chia hết cho 2010 thì số đó phải là lớn nhất. Nối tất cả các điểm thuộc tập hợp A lại với nhau sao cho điểm nào thuộc A cũng thuộc đúng một tứ giác. Tìm số lớn nhất tứ giác "đẹp" được tạo thành. Bài 7. Cho một đa giác lồi 67 đỉnh các đỉnh được nối với nhau bởi các đoạn thẳng. Chọn n đoạn bất kỳ và mỗi đoạn được tô bởi một màu trong 10 màu cho trước. Tìm số n nhỏ nhất sao cho với bất kỳ cách tô nào cũng luôn tìm được một đỉnh mà có ít nhất 7 cạnh xuất phát từ đó cùng màu. Bài 8. Gọi G là tập hợp các điểm có tọa độ trên mặt phẳng tọa độ với . Một tập con S của G được gọi là tập "hình bình hành tự do" nếu không có 4 điểm nào trong S tạo thành hình bình hành (trừ trường hợp chúng thẳng hàng). Xác định cỡ lớn nhất của S. Bài 9. Cho giác lồi (). Chia đa giác này thành các tam giác rời nhau có các đỉnh là đỉnh của đa giác, rồi tô các tam giác này bằng 2 màu đỏ và trắng sao cho hai tam giác cùng chung cạnh thì được tô hai màu khác nhau. Trong tất cả các cách chia tìm số tam giác nhỏ nhất được tô màu đỏ. Bài 10. Giả sử M là tập con của tập gồm tất cả các cặp số tự nhiên không vượt quá số tự nhiên cho trước.Trong đó nếu cặp thuộc M thì không có cặp nào thuộc M. Hãy xác định số cặp lớn nhất có thể có của tập M. Bài 11. Cho tập . Tìm số nguyên dương nhỏ nhất sao cho tồn tại tập thỏa các điều kiện sau: i) và ii) Không tồn tại tập sao cho tồn tại ba phần tử (a,b,c không nhất thiết phân biệt) sao cho . Bài 12. Trong một đại hội có 51 đại biểu. Đại biểu được chia thành n nhóm sao cho mỗi đại biểu thuộc vào đúng một nhóm. Mỗi đại biểu ghét đúng 3 đại biểu khác. Biết rằng nếu A ghét B thì không nhất thiết B ghét A. Tìm số n nhỏ nhất sao cho ta luôn có thể chia n nhóm sao cho không có đại biểu nào ghét đại biểu khác trong nhóm của ông hoặc bà đó. Bài 13. Trên bàn cờ vua kích thước 8x8 được chia thành 64 ô vuông đơn vị, người ta bỏ đi một ô vuông đơn vị nào đó ở vị trí hàng thứ m và cột thứ n . Gọi S(m;n) là số hình chữ nhật được tạo bởi một hay nhiều ô vuông đơn vị của bàn cờ sao cho không có ô nào trùng với vị trí của ô bị xóa bỏ ban đầu. Tìm giá trị nhỏ nhất và giá trị lớn nhất của S(m;n). Bài 14. Cho tập . Hãy tìm số nguyên dương nhỏ nhất có tính chất: Với mọi tập con của mà thì trong A ta luôn tìm được ba phần tử sao cho trong đó là 3 phần tử thuộc tập (CMO 2010) Bài 15.(Vietnam TST 2012) Trên một cánh đồng hình chữ nhật kích thước ô vuông gồm hàng và cột người ta đặt một số máy bơm nước vào các ô vuông. Biết rằng mỗi máy bơm nước có thể tưới nước cho các ô vuông có chung cạnh với nó và các ô vuông cùng cột với nó và cách nó đúng một ô vuông . Tìm số nhỏ nhất các máy bơm nước sao cho các máy bơm nước có thể tưới hết cả cánh đồng trong 2 trường hợp: a) b) PHẦN IV. KẾT QUẢ Khi thực hiện giảng dạy cho các em học sinh trong đội tuyển học sinh giỏi, các em đã giảm bớt sự e sợ đối với dạng toán này và