Luận văn Áp dụng phương pháp phân hoạch để giải toán trung học phổ thông

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG  BÙI NGUYÊN SƠN ÁP DỤNG PHƢƠNG PHÁP PHÂN HOẠCH ĐỂ GIẢI TOÁN TRUNG HỌC PHỔ THÔNG Chuyên ngành: Phƣơng pháp Toán sơ cấp Mã số: 60.46.01.13 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng – Năm 2016 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Ngƣời hƣớng dẫn khoa học: TS. TRỊNH ĐÀO CHIẾN Phản biện 1: TS. Trương Công Quỳnh. Phản biện 2: TS. Hoàng Quang Tuyến. Luận văn đã được bảo vệ tại Hội đồng chấm Luận văn tốt nghiệp thạc sĩ Khoa học chuyên ngành Phương pháp Toán sơ cấp tại Đại học Đà Nẵng vào ngày 13 tháng 08 năm 2016. Tìm hiểu luận văn tại: Trung tâm Thông tin-Học liệu, Đại học Đà Nẵng Thư viện trường Đại học Sư phạm, Đại học Đà nẵng 1 MỞ ĐẦU 1. Lý do chọn đề tài Lý thuyết mở đầu về Phân hoạch tập hợp tỏ ra khá đơn giản, nhưng những áp dụng của nó rất phong phú. Nhiều bài toán khó trong các đề thi chọn học sinh giỏi các cấp và Olympic Toán quốc tế đôi khi được giải quyết khá nhanh gọn và độc đáo nhờ vào việc áp dụng phương pháp phân hoạch tập hợp. Mà phương pháp ấy đôi khi cũng “bất quy tắc”. Các tập hợp khác rỗng 1 2, , ... , kA A A được gọi là một phân hoạch của tập hợp A nếu:   1 2 ... ; , , 1, 2, ..., , . k i j A A A A A A i j k i j           Mỗi tập con iA được gọi là một thành phần của phân hoạch. Trong lý thuyết về phân hoạch tập hợp, việc phân hoạch trên những tập rời rạc, đặc biệt trên tập số nguyên đóng một vai trò quan trọng. Nhiều kết quả cổ điển xuất sắc đã ra đời từ lý thuyết này. Những kết quả ấy còn độc đáo ở chỗ việc chứng minh chúng nhiều khi chủ yếu chỉ sử dụng một số tính chất cơ bản của Số học cùng với những suy luận logic, mà không phải áp dụng những công cụ mạnh chẳng hạn của Giải tích và Đại số. Có thể xem các bài toán về phân hoạch tập hợp như là một bộ phận của Toán Rời rạc, chủ yếu được nghiên cứu ở bậc Đại học và 2 Sau đại học, chưa được giới thiệu một cách bài bản trong chương trình Toán phổ thông, đặc biệt ở hệ Chuyên Toán. Một cách hình thức, có thể chia những bài toán này theo 2 dạng: - Dạng toán yêu cầu nêu phân hoạch của tập hợp. Đó là các bài toán dạng “hiện”, mà phân hoạch tập hợp là yêu cầu trong đề bài. Chẳng hạn bài toán sau đây: “Giả sử c là số hữu tỉ dương và khác 1 . Chứng minh rằng có thể phân hoạch tập các số nguyên dương thành hai tập khác nhau A và B sao cho x c y  , với mọi x, y cùng thuộc A hoặc cùng thuộc B ”. - Dạng toán giải bằng phương pháp phân hoạch tập hợp. Đó là các bài toán dạng “ẩn”, mà ta phải áp dụng phương pháp phân hoạch tập hợp một cách khéo léo mới giải được. Chẳng hạn bài toán sau đây: “ Cho p và q là hai số lẻ và nguyên tố cùng nhau. Chứng minh: 1 1 2 2 1 1 1 1 2 2 p q i j iq jp p q p q                             ”. Cho đến nay, ngoài một số tài liệu tham khảo chủ yếu từ nguồn internet, lý thuyết và các phương pháp phân hoạch tập hợp hầu như còn rất ít tài liệu đề cập một cách hệ thống. Luận văn góp phần giới thiệu một cách cơ bản về phương pháp phân hoạch tập hợp, với mục đích sẽ là một tài liệu tham khảo hữu 3 ích cho học sinh, sinh viên, giáo viên phổ thông, đặc biệt đối với hệ Chuyên Toán. 2. Mục tiêu nghiên cứu Luận văn đề cập đến lý thuyết và một số áp dụng của phương pháp phân hoạch tập hợp trong việc giải một số bài toán khó ở phổ thông, đặc biệt đối với bài toán Số học. Luận văn có thể là một tài liệu tham khảo hữu ích cho học sinh, sinh viên, giáo viên phổ thông, đặc biệt đối với hệ Chuyên Toán. Do đó, việc nghiên cứu của luận văn là cần thiết, có ý nghĩa khoa học, mang tính thực tiễn và phù hợp với chuyên ngành Phương pháp Toán sơ cấp. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu Phương pháp phân hoạch trên tập hợp nào đó nói chung và trên tập số nguyên dương nói riêng. 3.2. Phạm vi nghiên cứu Thuộc chuyên ngành Phương pháp toán sơ cấp. Luận văn không quá đi sâu vào lý thuyết phân hoạch mà sơ cấp hóa nó, áp dụng phương pháp phân hoạch để giải một số bài toán khó của toán phổ thông. 4 4. Phương pháp nghiên cứu Từ các tài liệu sưu tầm được, luận văn sẽ đề cập ngắn gọn về phân hoạch tập hợp và áp dụng phương pháp phân hoạch để tìm tòi lời giải, cùng với việc đề xuất một số bài toán tương tự, phù hợp với toán phổ thông, đặc biệt đối với hệ Chuyên Toán. 5. Ý nghĩa khoa học và thực tiễn của đề tài Với mục đích nêu trên, việc nghiên cứu của luận văn là có ý nghĩa khoa học, mang tính thực tiễn và phù hợp với chuyên ngành Phương pháp Toán sơ cấp. Có thể sử dụng luận văn như là tài liệu tham khảo cho giáo viên, học sinh và bạn đọc quan tâm đến vấn đề này. 6. Cấu trúc luận văn Với mục đích nêu trên, nội dung của luận văn gồm các phần sau đây: Lời mở đầu. Giới thiệu cơ sở khoa học và tính thực tiễn của đề tài, mục đích của đề tài, nội dung của đề tài và một số vấn đề khác theo quy định. Chương 1. Kiến thức cơ sở Chương này đề cập đến một số kiến thức cơ bản về phân hoạch tập hợp và một số lý thuyết quan trọng liên quan đến phân hoạch và được dùng nhiều trong chứng minh ở các chương sau như số Stirling 5 loại I, số Stirling loại II, Bài toán chia kẹo Euler, thuật toán “ba lô”, thuật toán “tham ăn” Chương 2. Phân hoạch nguyên Là phân hoạch trên tập số nguyên, với một tập hợp xác định gồm các số nguyên nào đó, các bài toán cần phân hoạch tập hợp này thành một số tập hợp con rời nhau sao cho chúng thỏa mãn một tính chất nào đó là những dạng toán quen thuộc và quan trọng. Chẳng hạn, cần phân hoạch một tập hợp các số nguyên xác định thành hai tập hợp con rời nhau sao cho tổng các số trong hai tập hợp con đó bằng nhau. Đây là những dạng toán thường là rất khó. Chương này đề cập đến việc phân hoạch trên tập số nguyên, giải quyết một số bài toán khó ở cả dạng “ẩn” và “hiện”. Chương 3. Phân hoạch tập hợp Chương này đề cập đến phương pháp phân hoạch và số cách phân hoạch trên tập hợp nào đó nói chung thỏa mãn một vài tính chất cụ thể. Đó có thể là bài toán nêu rõ yêu cầu phân hoạch ( dạng “ hiện”) chẳng hạn bài toán: “Tìm số các phân hoạch tập hợp  1, 2,..., n thành 3 tập con 1 2 3, , A A A (các tập này có thể rỗng) sao cho các điều kiện sau thỏa mãn. 1) Sau khi sắp xếp các phần tử của 1 2 3, , A A A theo thứ tự tăng dần, thì 2 phần tử liên tiếp luôn có tính chẵn, lẻ khác nhau. 6 2) Nếu cả ba tập 1 2 3, , A A A đều không rỗng, thì có đúng một tập có số nhỏ nhất là số chẵn.” Cũng có thể là bài toán không nêu rõ điều kiện nhưng để giải quyết ta buộc phải phân hoạch theo điều kiện nào đó (dạng “ẩn”), ví dụ: “Khai triển     10 2 101 ...f x x x x     ta được đa thức   2 1000 1 2 100...f x a a x a x a x     . Tính 0 1 2 10...S a a a a     .”. 7 CHƯƠNG 1 KIẾN THỨC CƠ SỞ Chương này đề cập đến một số kiến thức cơ bản về phân hoạch tập hợp và một số lý thuyết quan trọng liên quan đến phân hoạch và được dùng nhiều trong chứng minh ở các chương sau. 1.1. SỐ STIRLING LOẠI I VÀ LOẠI II 1.1.1. Chu trình của hoán vị Trong các bài toán về phân hoạch tập hợp, ta không thể nào không nhắc đến số Stirling. Đây là cơ sở để xây dựng các bài toán đếm một cách khá vững chắc, đồng thời kết hợp với các công cụ đại số và giải tích khác sẽ giúp xây dựng được nhiều lý thuyết khác. Chu trình trong một hoán vị 1 2 3, , ,..., na a a a của các số 1, 2, 3,..., n , là một tập con của các số này mà chúng đổi vị trí cho nhau tạo thành một vòng. Ta xét hoán vị sau 123456789 142357698 f  , trong hoán vị này,      2 4, 4 3, 3 2f f f   nên có thể nói  2; 3; 4 tạo thành một chu trình. Các số không đổi qua phép hoán vị được coi là một chu trình riêng biệt và do đó, trong hoán vị trên có tất cả 5 chu trình:  1 ,  4; 2; 3 ,  5 ,  7; 6 ,  9; 8 . 1.1.2. Số Stirling loại I Số hoán vị của n phần tử mà có đúng k chu trình, đặt là  ,s n k . Công thức truy hồi 8      1, , 1 . ,s n k s n k n s n k    . 1.1.3. Số Stirling loại II Số cách chia n phần tử thành k tập con, đặt là  ,S n k . Công thức truy hồi      1, , 1 ,S n k S n k kS n k    1.2. BÀI TOÁN CHIA KẸO EULER Bên cạnh các bài toán về số Stirling thì bài toán chia kẹo Euler liên quan đến số tổ hợp lặp là dạng khá phổ biến và quen thuộc. Dạng 1: Số cách chia n viên kẹo cho k em bé mà em nào cũng có kẹo là 1 1 k nC   . Dạng 2: Số cách chia n viên kẹo cho k em bé mà có thể có em không có kẹo là 1 1 k n kC    . 1.3 DÃY SỐ FIBONACCI Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1. Các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci là:       0, 0; : : 1, 1; 1 2 , 1. n khi n F F n khi n F n F n khi n            9 CHƯƠNG 2 PHÂN HOẠCH NGUYÊN Chương này đề cập đến việc phân hoạch trên tập số nguyên đồng thời giải quyết một số bài toán khó ở cả dạng “ẩn” và “hiện”. 2.1. PHÂN HOẠCH NGUYÊN DẠNG “ HIỆN” 2.1.1. Phân hoạch tập các số tự nhiên thành 2 tập hợp có tổng các phần tử bằng nhau Bổ đề 2.1. Từ n số nguyên cho trước, luôn chọn được một vài số để tổng của chúng chia hết cho n . Định lí 2.1. (P. Erdos, A. Ginzburg, A. Ziv) Từ 2 1n  số nguyên dương cho trước, luôn chọn được n số sao cho tổng của chúng chia hết cho n . Bổ đề 2.2. Nếu trong 1n  số nguyên dương cho trước không tồn tại một nhóm số có tổng chia hết cho n thì 1n  số đó có cùng số dư khi chia cho n . Bài toán 2.1. Tồn tại hay không giá trị K nhỏ nhất để với mọi số nguyên dương k K , tập hợp A luôn có thể phân hoạch thành 2 tập con có tổng các phần tử mỗi tập bằng N? 10 Định lý 2.2. Mọi tập gồm 1N  số nguyên dương không lớn hơn N và có tổng bằng 2N , luôn phân hoạch được thành 2 tập con, mỗi tập có tổng các phần tử bằng N . Bổ đề 2.3. Với 2N n và A là tập hợp 2 1n  số nguyên dương không lớn hơn N và có tổng bằng 2N . Khi đó, A có thể phân hoạch được thành 2 tập con, mỗi tập có tổng các phần tử bằng N . Bổ đề 2.4. Cho A là tập k số nguyên dương không vượt quá N và A biểu diễn được đến N . Khi đó A là tập hoàn chỉnh. Bổ đề 2.5. Nếu A và B là hai tập hoàn chỉnh thì C A B  là tập hoàn chỉnh. Bổ đề 2.6. Cho A là tập các số nguyên dương và 1 A . Khi đó, tồn tại duy nhất một tập con hoàn chỉnh của A có số phần tử lớn nhất. Gọi tập hoàn chỉnh này là H và h là tổng các phần tử của H. Nếu tất cả các phần tử của A không vượt quá h thì H=A. Nếu a A và a H thì 2a h  . Bổ đề 2.7. Nếu tập  2 ,A N k với 2 2 N k        thì A có ít nhất ba phần tử có giá trị nhỏ hơn 4. 11 Định lý 2.3. Cho  2 ,A N k với 2N  và 2 2 N k        . Gọi H là tập con hoàn chỉnh có số phần tử lớn nhất của A. Nếu H biểu diễn được đến 3 thì A phân hoạch được thành 2 tập có tổng các phần tử bằng N. Định lý 2.4. Cho  2 ,A N k với 2, 2 2 N N k         và  1 2 3( , , ) (1; 1; 1), (1; 1; 2),(1; 1; 3), (1; 2; 2), (1; 2; 3)a a a  . Khi đó, tập hợp A có thể phân hoạch được thành hai tập con có tổng các phần tử bằng N. Bổ đề 2.8. Cho tập  2 ,A N k với  2 ,A N k mà 12, 2, 2 2 N N k a          . Khi đó, 2 số bất kỳ thuộc A có tổng không vượt quá N. 12 Định lý 2.5. Cho tập  2 ,A N k với 2 2 N k        , N chẵn và 1 2 2a a  . Khi đó ta có thể phân hoạch tập A thành 2 tập có tổng bằng N. Định lý 2.6. Cho tập  2 ,A N k với 2 2 N k        , k chẵn và 2 2a  . Khi đó có thể phân hoạch A thành 2 tập con có tổng các phần tử bằng N. Hệ quả 2.1. Cho tập  2 ,A N k với 6 2, 1 N m m   và 4 3k m  . Tập  2 ,A N k có thể phân hoạch được thành 2 tập con có tổng các phần tử bằng nhau. Hệ quả 2.2. Cho tập  2 ,A N k với 6 4; 4 4N m k m    . Tập  2 ,A N k có thể phân hoạch được thành 2 tập con có tổng các phần tử bằng nhau. Hệ quả 2.3. Cho tập  2 ,A N k với 6 ; 3 2N m k m   . Tập  2 ,A N k có thể phân hoạch được thành 2 tập con có tổng các phần tử bằng nhau. Định lý 2.7. Cho một tập A có k phần tử là số nguyên dương không lớn hơn N và tổng của các số này bằng 2N. Khi đó, tồn tại giá 13 trị K nhỏ nhất để với mọi k K , tập A luôn phân hoạch được thành 2 tập con có tổng các phần tử mỗi tập bằng N, trong đó:  K= N+1 khi N lẻ  K= 2 khi N=2  K= 4m+3 khi N= 6m+2  K= 4m+4 khi N= 6m+4  K= 3m+2 khi N = 6m. Bài toán 2.2. Chứng minh rằng trong 35 số nguyên dương không vượt quá 50 và có tổng bằng 100 thì có thể chọn ra một nhóm số có tổng bằng 50. Hệ quả 2.4. Trong năm số nguyên bất kỳ, luôn tìm được vài số để tổng của chúng chia hết cho 5. 2.1.2. Phân hoạch dạng tổng 2.1.3 Định lý Beatty Định lí 2.8. Nếu a, b là 2 số vô tỉ dương thỏa mãn 1 1 1 a b   và xét các tập hợp    , 1, 2, 3... , , 1, 2, 3,...A ma m B nb n          thì *, A B A B    . 14 2.1.4. Các bài toán chọn lọc khác Bài toán 2.1. Chứng minh rằng nếu gọi  , f r n là số phân hoạch của n thành dạng 0 1 2 ... sb b b b    với 0 1i s   và 1i ib rb  , r là một số nguyên dương nào đó thì tồn tại số nguyên dương n mà  , f r n khác số phân hoạch của n thành các phần từ một tập hợp các số nguyên bất kỳ, trừ khi 1r  . Bài toán 2.2. Gọi f(n), g(n) lần lượt là số phân hoạch của n thành số chẵn phần và số lẻ phần. Chứng minh rằng      1 m f n g n   nếu   1 3 1 2 n m m  và bằng    f n g n nếu ngược lại. (số có dạng   1 3 1 2 n m m  được gọi là pentagonal number). Bài toán 2.3. Gọi n là số nguyên dương sao cho 1, 2, 3,..., 3n có thể chia thành 3 tập hợp là      1 2 1 2 1 2, ,..., , , ,..., , , ,..., n n na a a b b b c c c sao cho , 1, .i i ia b c i n    Chứng minh rằng nếu n thỏa thì 3 1, 4 , 4 1n n n  cũng thỏa. Bài toán 2.4. a) Hỏi có tồn tại cách phân hoạch tập hợp các số nguyên dương thành các tập con có 2 phần tử 1 2 3, , ,..., nA A A A sao 15 cho với mọi số nguyên dương n tổng các phần tử của nA là 1391 n ? b) Hỏi có tồn tại cách phân hoạch tập hợp số nguyên dương thành các tập con có 2 phần tử 1 2 3, , ,..., nA A A A sao cho với mọi số nguyên dương n tổng các phần tử của nA là 21391 n ? Bài toán 2.5. Chứng minh rằng có thể phân hoạch tập hợp các số tự nhiên thành 100 tập khác rỗng sao cho với bất kỳ 3 số tự nhiên a, b, c thỏa mãn 99a b c  thì 2 trong số chúng thuộc cùng một tập hợp. Bài toán 2.6. Giả sử c là số hữu tỷ dương và khác 1. Chứng minh rằng có thể phân hoạch tập các số nguyên dương thành 2 tập khác nhau A, B sao cho x c y  với mọi x, y cùng nằm trong A hoặc cùng nằm trong B. Bài toán 2.7. Có bao nhiêu cách chia 15 đồ vật đôi một khác nhau cho 5 người, sao cho trong số đó có đúng 2 người không nhận được đồ vật nào? 2.2. PHÂN HOẠCH NGUYÊN DẠNG “ ẨN ” Bài toán 2.8. Cho bảng ô vuông  ija với 1, , 1, i n j n  và điền các số từ 1 đến 2n theo thứ tự từ trái sang phải, từ trên xuống dưới. Người ta viết ghép các hàng của bảng này theo thứ tự từ trái 16 sang phải được một dãy X. Tiếp tục ghép các cột của bảng này thành dạng hàng ngang cũng từ trái sang phải được dãy Y. Một phép biến đổi cho phép đổi chỗ 2 số cho nhau. Hỏi ít nhất cần bao nhiêu phép biến đổi để đưa X về Y? Bài toán 2.9. Cho A là tập tất cả các hoán vị  1 2 2003, ,..., a a a a của 2003 số nguyên dương đầu tiên và một hoán vị thỏa mãn điều kiện: Không có tập con S nào của A mà  |ka k S S  . Với mỗi  1 2 2003, ,..., a a a a A  ta kí hiệu     2003 2 1 k k d a a k    . 1. Tìm giá trị nhỏ nhất của d(a), gọi giá trị nhỏ nhất đó là 0d . 2. Tìm tất cả các hoán vị a A thỏa mãn   0d a d . Bài toán 2.10. Gọi  S n là số cách phân hoạch có tính thứ tự của n thành các số 1, 3, 4. Chứng minh rằng  2S n là số chính phương. Bài toán 2.11. Từ việc so sánh phân hoạch của n thành các số 1, 2 chứng minh rằng 17 1 0 , , 2 x x y n x y n x y n C F       . Bài toán 2.12. Cho số nguyên dương k. Dãy số  , 1, 2, 3,...nx n  được xác định như sau: (i) 1 1x  . (ii) Với mỗi số nguyên dương 1n  thì 1nx  là số nguyên dương bé nhất không thuộc tập  1 2 3 1 2 3; ; ;...; ; ; 2 ; 3 ;...; n nx x x x x k x k x k x nk    . Chứng minh rằng tồn tại số thực a sao cho nx na    với mọi *n . Bài toán 2.13. Xét dãy các số 3, 6, 7, 9, 10, 11, 12,... là có thể biểu diễn thành tổng của ít nhất hai số nguyên dương liên tiếp. Gọi  f n là số hạng thứ n của dãy. Chứng minh rằng     2 2log logf n n n n     . Bài toán 2.14. Chứng minh rằng tập các số tự nhiên có thể được tô bởi 2 màu mà 2 điều kiện sau đây được thỏa mãn: i) Với mỗi số nguyên tố p và mỗi số tự nhiên n thì các số 1, n np p  và 2np  không được tô cùng màu. i)) Không tồn tại một cấp số nhân vô hạn của các số tự nhiên có cùng màu. 18 CHƯƠNG 3 PHÂN HOẠCH TẬP HỢP Chương này đề cập đến phương pháp phân hoạch và số cách phân hoạch trên tập hợp nào đó nói chung thỏa mãn một vài tính chất cụ thể. 3.1. PHÂN HOẠCH TẬP HỢP DẠNG “ HIỆN ” 3.1.1. Các dạng của phân hoạch tập hợp Trong toán học, người ta tổng hợp các bài toán về phân hoạch tập hợp hay có thể hình dung là phân chia đồ vật và phân thành 12 dạng với tên gọi nổi tiếng “ Twelvefold Way”. Dưới đây, ta xét bài toán chung là: Xác định tất cả số cách cho n quả bóng vào k hộp. Các kiểu phân hoạch được đặc trưng bằng 1 ánh xạ đi từ tập các quả bóng đến các hộp được liệt kê đầy đủ dưới đây, chú ý rằng:  Ánh xạ bất kỳ: việc phân chia là tùy ý, không có ràng buộc gì (có thể 1 hộp có nhiều bóng mà cũng có thể có hộp không có quả nào, nhưng tất nhiên là 1 quả bóng thì chỉ có thể chia vào 1 hộp).  Đơn ánh: mỗi hộp chỉ chứa nhiều nhất 1 quả bóng. Toàn ánh: mỗi hộp chứa ít nhất 1 quả bóng. Ở đây không xét song ánh vì khi đó mỗi hộp chỉ chứa đúng 1 quả bóng và bài toán không còn nhiều ý nghĩa. Quy ước 0 abC  với b a . 19 Trường hợp 1: Các quả bóng đôi một khác nhau và các hộp đôi một khác nhau.  Ánh xạ bất kỳ: mỗi quả bóng đều có thể xếp vào một hộp tùy ý. Kết quả là nk .  Đơn ánh: Nếu n k thì không có cách xếp thỏa mãn vì theo Nguyên lý Dirichlet, sẽ có 1 hộp chứa nhiều hơn 1 quả bóng, kết quả là 0. Nếu n k , ta thấy quả bóng đầu tiên có thể đặt vào k hộp, quả thứ 2 có thể đặt vào 1k  hộp còn lại và cứ thế. Kết quả là     1 2 ...k k k k n   .  Toàn ánh: Vấn đề tương tự như việc phân hoạch tập hợp có n phần tử thành k tập con khác rỗng, tuy nhiên chú ý rằng cần quan tâm đến thứ tự của tập con tương ứng. Kết quả là  ! , k S n k với  , S n k là số Stirling loại II. Trường hợp 2: Các quả bóng giống nhau và các hộp đôi một khác nhau.  Ánh xạ bất kỳ: Do các quả bóng giống nhau nên ta chỉ xét có bao nhiêu quả được đưa vào mỗi hộp, tương ứng với bài toán chia kẹo Euler trong trường hợp không nhất thiết em nào cũng có kẹo. Kết quả là 1 1 k n kC    . 20  Đơn ánh: Tương tự trên, nếu n k thì kết quả là 0. Nếu n k thì ta tính số cách chọn n hộp trong k hộp. Kết quả là n kC .  Toàn ánh: Số trường hợp tương ứng chính là bài toán chia kẹo Euler trong trường hợp em nào cũng phải có kẹo. Kết quả là 1 1 k nC   . Trường hợp 3: Các quả bóng đôi một khác nhau và các hộp đều giống nhau.  Ánh xạ bất kỳ: Do các quả bóng là khác nhau nên ta dánh số chúng từ 1 dến n , dẫn đến bài toán phân hoạch tập hợp  1, 2, 3,..., n thành không quá k tập con. Kết quả là      , 1 , 2 ... , S n S n S n k   .  Đơn ánh: Tương tự trên, nếu n k thì kết quả là 0. Nếu n k thì rõ ràng chỉ có 1 cách xếp. Kết quả là 1.  Toàn ánh: Hộp nào cũng phải có bóng nên nó đúng với bài toán tính số Stirling loại II. Kết quả là  , S n k . Trường hợp 4: Các quả bóng đều giống nhau và các hộp đều giống nhau.  Ánh xạ bất kỳ: Tương ứng với bài toán phan hoạch số n thành không quá k thành phần. Kết quả là      1 2 ... kp n p n p n   . 21  Đơn ánh: Tương tự trên, nếu n k thì kết quả là 0. Nếu n k thì rõ ràng chỉ có 1 cách xếp. Kết quả là 1.  Toàn ánh: Tương ứng với bài toán phân hoạch số n thành đúng k thành phần. Kết quả là  kp n . 3.1.2. Các bài toán chọn lọc Bài toán 3.1. Tìm số các phân hoạch tập hợp  1, 2,..., n thành 3 tập con 1 2 3, , A A A (các tập này có thể rỗng ) sao cho các điều kiện sau thỏa mãn: 1) Sau khi sắp xếp các phần tử của 1 2 3, , A A A theo thứ tự tăng dần, thì 2 phần tử liên tiếp luôn có tính chẵn, lẻ khác nhau. 2) Nếu cả ba tập 1 2 3, , A A A đều không rỗng, thì có đúng một tập có số nhỏ nhất là số chẵn. Bài toán 3.2. Cho tập M gồm n số dương 1 2, ,..., na a a . Xét tất cả các tập hợp con iT khác rỗng của M. Gọi is là tổng các số thuộc tập con iT nói trên. Chứng minh rằng có thể chia tập hợp tất cả các số is được thành lập như vậy thành n tập hợp con khác rỗng không giao nhau sao cho tỉ số của hai số bất kỳ thuộc cùng một tập hợp con vừa được phân chia không vượt quá 2. 3.2. PHÂN HOẠCH TẬP HỢP DẠNG “ẨN” Bài toán 3.3. Xác định số nghiệm của các phương trình sau a) 1 2 3 20... 2013x x x x     với , 1, ix i i n  . 22 b) 1 2 3 51... 2013x x x x     với , 1, ix i n là các số lẻ. c) 1 2 3 201... 2013x x x x     với 1 22, 3x x  . Bài toán 3.4. Trong mặt phẳng, cho tam giác ABC. Một điểm P nằm trong tam giác gọi là điểm tốt nếu ta có thể tìm được đúng 27 tia chung gốc P cắt các cạnh của tam giác ABC và chia tam giác thành 27 tam giác con có diện tích bằng nhau. Xác định tất cả các điểm tốt của tam giác ABC. Bài toán 3.5. Ở một ngôi làng nọ, mỗi người hoặc luôn nói thật hoặc luôn nói dối. Xét 5 người trong làng xếp thành 1 hàng và 1 người khách đến thăm làng hỏi mỗi người trong họ rằng có bao nhiêu người nói thật trong hàng. Mỗi người sẽ cho khách một số từ 0 đến 5. Hỏi có bao nhiêu multiset các câu trả lời mà người khách có thể nhận được? (multiset là tập mà mỗi phần tử có thể xuất hiện nhiều hơn 1 lần). Bài toán 3.6. Cho A là tập hợp 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 tập hợp A đều tồn tại hai số phân biệt a và b sao cho 2 2a b là một số nguyên tố. Bài toán 3.7. Cho p và q là hai số nguyên tố lẻ. Chứng minh 1 1 2 2 1 1 1 1 2 2 p q i j iq jp p q p q                             . 23 Bài toán 3.8. Đối với mỗi số tự nhiên n , hãy tìm số tự nhiên k lớn nhất thỏa mãn điều kiện: trong tập gồm n phần tử, có thể chọn ra được k tập con khác nhau mà hai tập bất kỳ trong các tập con này đều có giao khác rỗng. Bài toán 3.9. Khai triển     10 2 101 ...f x x x x     ta được đa thức   2 1000 1 2 100...f x a a x a x a x     . Tính 0 1 2 10...S a a a a     . Bổ đề 3.1. Cho hai số tự nhiên n, k. Xét tập hợp:  , 0 1 0 1 0 1( , ,..., ) | , ,..., , ...n k n n nH x x x x x x x x x k      . Thế thì , n n k n kH C  Bài toán 3.10. Cho số nguyên 2n  . Gọi S là tập hợp gồm n phần tử và (1 )iA i m  là các tập con khác nhau và gồm ít nhất hai phần tử của S sao cho từ các quan hệ , , i j i k j kA A A A A A      ta suy ra được i j kA A A   . Chứng minh rằng 12 1nm   . 24 KẾT LUẬN Dưới sự hướng dẫn tận tình của thầy giáo TS. Trịnh Đào Chiến, dựa trên các tài liệu của thầy cung cấp, tôi đã hoàn thành đề tài của mình. Luận văn “Áp dụng phương pháp phân hoạch để giải toán trung học phổ thông” đã đạt được các kết quả sau: 1. Trình bày một số khái niệm về phân hoạch tập hợp. Nêu ra một số tính chất, kết quả liên quan đến việc áp dụng phương pháp phân hoạch vào giải các bài toán. 2. Trình bày việc áp dụng phương pháp phân hoạch để phân hoạch tập hợp số nguyên và giải một số dạng toán tổng hợp cả dạng ẩn và hiện trên tập này. 3. Trình bày áp dụng phương pháp phân hoạch để tìm ra cách phân hoạch và số cách phân hoạch một tập hợp nào đó nói chung để giải một số dạng số học, bài toán tính tổng tổ hợp, bài toán đếm tổ hợp và một số bài toán tổng hợp khác. Kết quả của luận văn có ý nghĩa khoa học, mang tính thực tiễn và phù hợp với chuyên ngành Phương pháp Toán sơ cấp. Có thể sử dụng luận văn như là tài liệu tham khảo cho giáo viên, học sinh và bạn đọc quan tâm đến vấn đề này. Mặc dù bản thân đã cố gắng rất nhiều trong quá trình làm luận văn, tuy nhiên do thời gian và năng lực còn hạn chế nên trong luận văn này không tránh khỏi những thiếu sót . Rất mong quý thầy cô và các bạn đọc góp ý để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn.