Ứng dụng phương pháp ánh xạ trong giải toán tổ hợp

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH ĐĂK LĂK TRƯỜNG TRUNG HỌC PHỔ THỒNG CHUYÊN NGUYỄN DU ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP NGƯỜI THỰC HIỆN : LÊ NGỌC ĐỨC LỚP : 10CT NIÊN KHÓA : 2017-2020 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP MỤC LỤC Mục lục …………………………………………………………………………………………………..1 Lời cảm ơn ……………………………………………………………………………………………….2 Giới thiệu và tổng quan về vấn đề nghiên cứu …………………………………………………………...4 Một số chữ viết tắt và các kí hiệu toán học trong tài liệu …………………………..…………………….5 Cơ sở lí thuyết ……………………………………………………………………………………………. Ánh xạ ……………………………………………………………………………………...……………6 Ứng dụng của ánh xạ trong các bài toán tổ hợp …………………………………………………………7 Lời kết ……………………………………………………………………………………………...……28 Tài liệu tham khảo …………………………………………………………………………………...….29 Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 2 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP LỜI CẢM ƠN Trong quá trình học tập, nghiên cứu và thực hiện dự án, chúng tôi đã nhận được nhiều sự giúp đỡ. Giờ đây khi nội dung dự án đã được hoàn thành, chúng tôi xin bày tỏ lòng biết ơn chân thành đến: Quý Thầy, Cô của trường THPT chuyên Nguyễn Du tỉnh Đắk Lắk đã tận tình giảng dạy, hướng dẫn, giúp đỡ chúng tôi học tập và hỗ trợ chúng tôi trong việc thực hiện đề tài nghiên cứu. Đặc biệt là thầy Nguyễn Văn Quang, giáo viên hướng dẫn khoa học, đã tận tình hướng dẫn chúng tôi trong suốt quá trình nghiên cứu và hoàn thành dự án. Chúng tôi cũng xin bày tỏ lòng biết ơn đến các thầy, tuy không giảng dạy trực tiếp nhưng đã chia sẻ những bài toán tổ hợp hay với cách giải bằng phương pháp ánh xạ rất độc đáo để chúng tôi tham khảo. Xin gửi tặng các bạn cùng lớp, những người đã dành cho chúng tôi những tình cảm, lời động viên, sự giúp đỡ trong cuộc sống và trong quá trình học tập vừa qua. Lần đầu tiên chúng tôi tập làm nghiên cứu, nội dung có lẽ chưa được đầy đủ và còn nhiều thiếu sót, mong nhận được những góp ý bổ ích từ quý Thầy, Cô cùng các độc giả. Xin trân trọng cảm ơn! Buôn Ma Thuột, ngày 16 tháng 10 năm 2017 Tác giả Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 3 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP A. LỜI GIỚI THIỆU VÀ TỔNG QUAN Cùng với chương trình phát triển trọng điểm toán học giai đoạn 2010 – 2020 , toán học Việt Nam đã có nhiều phát triển và tiến bộ.Đi cùng với đó,phong trào chuyên toán phổ thông những năm gần đây đã có nhiều dấu hiệu khởi sắc với kết quả các kì thi HSG toán quốc gia và quốc tế của chúng ta ngày càng được nâng cao. Hằng năm các trường hè,trường đông được Viện toán học tổ chức ngày càng phát triển về quy mô và chất lượng. Cùng với những sự phát triển đó thì nhu cầu tài liệu càng được nhiều học sinh quan tâm. Đặc biệt là những tài liệu mang tính thời sự và chuyên môn sâu về các phân môn. Lịch sử và quá trình giảng dạy cho ta thấy điểm yếu của học sinh Việt Nam đó chính là toán tổ hợp và rời rạc. Trong các kìthi HSG toán phổ thông, số học sinh giải quyết trọn vẹn bài toán tổ hợp là rất ít, thậm chí không có học sinh nào. Trên thực tế như vậy, việc biên soạn một cuốn sách chuyên khảo sâu về tổ hợp và rời rạc là việc rất cần thiết.Và đó cũng là lý do chúng tôi biên soạn tài liệu này.Tài liệu này cung cấp những khái niệm về ánh xạ và ứng dụng của nó trong toán học. Trong toán học, tổ hợp là một dạng toán rất khó nhưng lại rất thu hút vì những lài giải hay, độc đáo và có ý nghĩa quan trọng trong các nghành học công nghệ thông tin. Trong các kì thi học sinh giỏi, tổ hợp luôn là bài toán khó nhất nên hầu hết học sinh đều ngại học chủ đề này, vì mỗi kì chỉ có vài ba bạn giải được. Do đó có rất nhiều nghiên cứu về chủ đề này, từ đó có rất nhiều phương pháp để tiếp cận. Ánh xạ là một trong các công cụ đầu tiên, đơn giản nhưng hiệu quả trong bài toán đếm. Thông qua ánh xạ ta đưa một bài toán đếm phức tạp về một bài toán đếm đơn giản hơn ; tuy nhiên việc xây dựng ánh xạ phù hợp mới là việc khó khăn đòi hỏi phải và chạm nhiều và phải có kinh nghiệm. Bài nghiên cứu này nhằm mục đích ban đầu là tự học, tổng hợp các bài toán để có thêm nhiều kinh nghiệm; sau đó là một tài liệu tham khảo cho các bạn bước đầu học tổ hợp. Tuy nhiên, dù đã cố gắng nhiều nhưng chắc chắn vẫn còn nhiều thiếu sót . Mong các bạn đọc góp ý để bài nghiên cứu hoàn thiện tốt hơn. Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 4 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP MỘT SỐ CHỮ VIẾT TẮT VÀ CÁC KÍ HIỆU TOÁN HỌC TRONG TÀI LIỆU I/Một số chữ viết tắt: IMO International Mathematical Olympiad Olympic Toán học Quốc tế VMO Vietnam Mathematical Olympiad Olympic Toán học Việt Nam APMO Asian Pacific Math Olympiad Olympic toán Châu Á – Thái Bình Dương II/Một số kí hiệu toán học A là số phần tử của tập hợp A Cmn là tổ hợp chập n của tập hợp gồm m phần tử Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 5 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP B. CƠ SỞ LÝ THUYẾT I/ÁNH XẠ 1/KHÁI NIỆM Một ánh xạ f đi từ tập X đến Y là một quy tắc đặt tương ứng mỗi phần tử x của X với một (và chỉ một) phần tử của Y Phần tử này được gọi là ảnh của x qua ánh xạ f và được kí hiệu là f(x). (i) Tập X được gọi là tập xác định của f. Tập hợp Y được gọi là tập giá trị của f. (ii) Ánh xạ f đi từ X đến Y được kí kiệu là f: X → Y x ↦y=f(x) (iii) Khi X và Y là các tập số thực , ánh xạ f được gọi là một hàm số xác định trên X (iv) Cho a thuộc X, b thuộc Y. Nếu f(a)=y thì ta nói y là ảnh của a và a là nghịch ảnh của y qua ánh xạ f (v) Tập hợp Y = {y=Y : mọi x thuộc X, y=f(x)} gọi là tập ảnh của f. 2/Đơn ánh, toàn ánh, song ánh 2.1. Định nghĩa đơn ánh: Ánh xạ f:X được gọi là đơn ánh nếu với a ∈ X,b ∈ Y mà a≠b thì f(a)≠f(b), tức là hai phần tử phân biệt sẽ có hai ảnh phân biệt. Từ định nghĩa ta suy ta ánh xạ f là đơn ánh khi và chỉ khi với a ∈ X, b ∈ Y mà f(a)=f(b), ta phải có a=b. 2.2. Định nghĩa toàn ánh Ánh xạ f: X ↦ Y được gọi là toàn ánh nếu với mỗi phần tử y ∈ Y đều tồn tại một phần tử x ∈ X sao cho y=f(x). Như vậy f là toàn ánh nếu và chỉ nếu Y=f(X). 2.3. Định nghĩa song ánh Ánh xạ f : X ↦ Y được gọi là song ánh nếu nó vừa là đơn ánh vừa là toàn ánh. Như vậy ánh xạ f : X↦Y là song ánh nếu và chỉ nếu với mỗi y  Y , tồn tại và duy nhất một phần tử x  X để y = f(x) 3. Ánh xạ ngược của một song ánh 3.1.Định nghĩa Ánh xạ ngược của f, được kí hiệu bởi ,là ánh xạ từ Y đến X gán cho mỗi phần tử y Y phần tử duy nhất x X sao cho y = f(x) . Như vậy 3.2. Chú ý. Nếu f không phải là song ánh thì ta không thể định nghĩa được ánh xạ ngược của f. Do đó chỉ nói đến ánh xạ ngược khi f là song ánh. 4. Ánh xạ hợp 4.1. Định nghĩa. Nếu g : A↦ B và f : B ↦ C và g(A)  B thì ánh xạ hợp được xác định bởi . Kí hiệu Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 6 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP Nguyên lý ánh xạ. Cho A và B là các tập hữu hạn khác rỗng và f : A B là một ánh xạ. Khi đó: a) Nếu f là đơn ánh thì | A| |B | b) Nếu f là toàn ánh thì |A | |B | c) Nếu f là song ánh thì |A | |B | Phương pháp ánh xạ dựa vào ý tưởng rất đơn giản: - Nếu tồn tại một song ánh từ tập hữu hạn A vào tập hữu hạn B thì |A| = |B|. Do đó, muốn chứng minh hai tập hợp có cùng số phần tử, chỉ cần xây dựng một song ánh giữa chúng. Hơn nữa, ta có thể đếm được số phần tử của một tập hợp A bằng cách xây dựng song ánh từ A vào một tập hợp B mà ta đã biết cách đếm hoặc dễ đếm hơn. - Nếu tồn tại một đơn ánh (tương ứng toàn ánh) từ A vào B thì |A| |B| (tương ứng |A| |B |). Do đó, đơn ánh và toàn ánh chủ yếu được sử dụng để chứng minh các bài toán liên quan đến bất đẳng thức tổ hợp. Chuyển bài toán cần chứng minh về việc so sánh số phần tử của hai tập hợp, trong đó có một tập hợp đã biết cách đếm hoặc dễ đếm. Tương tự nguyên lý Dirichle, về mặt ý tưởng thì hết sức đơn giản tuy nhiên thực thế thì không phải đơn giản như thế. Để sử dụng phương pháp này ta cần xác định được một song ánh giữa tập cần đếm vào một tập đã biết cách đếm việc làm này không phải lúc nào cũng thực hiện dễ dàng. Sau đây là một số bài tập áp dụng phương pháp trên II/ỨNG DỤNG CỦA ÁNH XẠ TRONG TỔ HỢP Để khởi đầu cho phần này tôi xin gửi đến các bạn một định lí đơn giản nhưng có ứng dụng rất lớn trong giải toán tổ hợp đó là “Bài toán chia kẹo của Euler” Định lí: Cho k,n là các số tự nhiên ; số nghiệm tự nhiên của phương trình + +…+ = n là Chứng minh Ta cho tương ứng mỗi nghiệm nguyên không âm của phương trình + +… + = n (1) với một xâu nhị phân độ dài n+k-1 trong đó có n bit 1 và k-1 bit 0, cụ thể xâu gồm bit 1, sau đó là 1 bit 0,tiếp theo là bit 1, sau đó là 1 bit 0, cứ như thế, cuối cùng là bit 1. Dễ dàng chứng minh được đây là một song ánh từ tập A các nghiệm nguyên không âm của (1) vào tập hợp B các xâu nhị phân độ dài n+k-1 với n bit 1 và k-1 bit 0. Từ đó, theo nguyên lý song ánh ta có (đpcm). Ví dụ 1: Có n người xếp thành hàng dọc.Hỏi có bao nhiêu cách chọn ra k người sao cho không có hai người liên tiếp được chọn ? Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 7 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP Lời giải Ta lần lượt đánh số thứ tự của hàng người bằng các số nguyên dương là 1,2,3,...,n. Vậy ta sẽ đưa đề về dạng : Cho n số nguyên dương 1,2,…,n.Hỏi có bao nhiêu cách chọn k số phân biệt trong n số đã cho sao cho không có 2 số nguyên liên tiếp nào? Một cách chọn thích hợp chính là bộ số 1 ≤ …< ≤ n thỏa mãn tức là . Vậy ta cần tìm số phần tử của A={( , , ,…, 1≤ …< ≤ n, với i=1,2,…,k-1} Xét ánh xạ : = với = thì rõ ràng ta có: i) ≥1 ii) iii) Suy ra là phần tử của tập hợp B B={ │1≤ …< ≤ n – k +1} Dễ thấy f là một đơn ánh Ngoài ra ánh xạ g = với cho chúng ta một đơn ánh từ B vào A.Vậy Ví dụ 2: Cho 49 số tự nhiên liên tiếp 1,2,…,49 . Hỏi có bao nhiêu cách chọn ra một bộ 6 số khác nhau từ 49 số đó trong đó có ít nhất 2 số nguyên liên tiếp Lời giải Giả sử bộ gồm 6 số tùy ý , , Không giảm tổng quát, ta giả sử …< (1) Ứng với dãy (1) xét tương ứng dãy sau : , , , , , (2) Rõ ràng dãy (2) gồm các số khác nhau khi cà chỉ khi dãy (1) không chứa 2 số nguyên liên tiếp.Rõ ràng ta có các số trong dãy (2) được sắp xếp từ bé đến lớn. Như vậy dãy 6 số trong đó không chứa 2 số nguyên liên tiếp được đặt tương ứng với dãy 6 số khác nhau được chọn từ các số 1 đến 44. Từ đây ta hoàn toàn có thể tính được kết quả cần tính Nhận xét: Bài toán đang xét với 1 tập 49 số và bạn đọc hoàn toàn có thể mở rộng ra với n số. Điểm nhấn đặc biệt đó là việc đặt tương ứng dãy (1) với dãy (2), điều này khá tự nhiên. Nhưng nó đã gắn kết bài toán và khiến mọi thứ trở nên tường minh hơn. Bài tập ứng dụng : Cho 2018 số tự nhiên liên tiếp 1,2,…,2018 . Hỏi có bao nhiêu cách chọn ra một bộ 6 số khác nhau từ 2018 số đó trong đó có ít nhất 2 số nguyên liên tiếp Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 8 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP Các bạn đã bao giờ nghĩ rằng nếu kết hợp cả hai ví dụ trên thì bài toán sẽ như thế nào không? Vâng tôi xin được gửi đến bạn sự kết hợp vi diệu ấy ở Ví dụ 3. Ví dụ 3: Cho n số 1,2,3,...,n.Có bao nhiêu cách chọn m số phân biệt từ n số đã cho sao cho trong m số ấy có ít nhất 2 số liên tiếp với giả thiết n ≥ 2m-1 Lời giải Gọi A là tập hợp tất cả các cách chọn m số từ n số phân biệt đã cho, ta có: = Gọi B là tập hợp các cách chọn m số phân biệt trong n số đã cho sao cho không có 2 số nguyên liên tiếp nào. Gọi C là tập hợp các cách chọn m số phân biệt trong n số đã cho sao cho có ít nhất 2 số nguyên liên tiếp. Áp dụng Ví dụ 1 , ta có : Kết quả : Nhận xét : Giả thiết n ≥ 2m-1 là cần thiết bởi vì khi đó n+1-m ≥ m. Vì nếu ngược lại thì theo nguyên lí Dirichlet trong mọi cách chọn đều có 2 số nguyên liên tiếp được chọn (Bạn đọc hãy tự lí giải điều này). Một câu hỏi các bạn cần trả lời được đó là : Nếu bỏ đi điều kiện n ≥ 2m-1 thì cần phải có thêm quy ước gì? Ví dụ 4: Cho tập hợp E ={1;2;…;n}.Gọi g(n,k) là số các tập con gồm k phần tử của E mà không chứa 2 số nguyên liên tiếp nào. Còn là số tất cả các tập con của E mà không chứa 2 số nguyên liên tiếp nào. Chứng mình rằng: a) g(n,k) = b) Lời giải Ở câu a) , ta có thể dễ dàng chứng minh như ở ví dụ trước Giờ ta chỉ việc xét câu b) Kí hiệu P là tập hợp tất cả các tập hợp con của E thỏa mãn điều kiện mà tập hợp con đó đều không chứa 2 số nguyên liên tiếp nào của E Đặt và A chứa n. và A không chứa n. Như vậy ta có Theo định nghĩa thì ta có Nếu A thì n A. Vì a nên a cũng thuộc P mà theo định nghĩa của P thì n nên n-a không thuộc A. Vậy A\{n} ’, ở đây P’ là tập hợp tất cả các tập hợp con của A\{n,n-1} thỏa mãn điều kiện là mỗi tập hợp con đó đều không chứa 2 Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 9 ỨNG DỤNG PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI TOÁN TỔ HỢP số nguyên liên tiếp nào của {1,2,3,…,n-2}. Như vậy với mỗi A tương ứng đúng với một tập con của P’. Vậy ta có : . Nhưng theo định nghĩa thì ta lại có . Lập luận tương tự ta có được : .Như vậy ta có điều phải chứng minh. Nhận xét : Kết quả của bài toán cho ta phép định nghĩa dãy Fibonacci theo tư tưởng của phép đếm. Một lần nữa chung ta thấy được vẻ đẹp của tổ hợp, những yếu tố tưởng chừng như không liên quan gì lại cho ta dãy Fibonacci. Từ đây đôi lúc khi làm việc với day Fibonacci ta có thể tổ hợp hóa và giải quyết bài toán theo hướng tổ hợp. Ví dụ 5:(VMO 2002) Cho tập S gồm tất cả các số nguyên trong đoạn [1,2001]. Gọi T là tập hợp tất cả các tập con không rỗng của S. Với mỗi X thuộc T, ký hiệu m(X) là trung bình cộng các phần tử của X. Tính m= . Lời giải Xét ánh xạ f :T → T như sau : f(X) = {2003 - x│x ∈ X},  X∈T. Vì f là song ánh nên m(X)=m(f(X)). Do đó : 2m = Mà m(X) +m(f(X)) = 2003 nên m = Ví dụ 6:( Trung Quốc 1994) Chứng minh rằng : Lời giải Bước 1 : Ta chọn ra n số từ 2n+1 số như sau. Trước hết từ 2n+1 số ta chia ra n cặp và số x. Bước 2 : Ta chọn ra k cặp rồi từ mỗi cặp chọn ra một số. Bước 3 : Chọn [ cặp trong n-k cặp còn lại. Ngoài ra số x sẽ được chọn nếu n-k lẻ và sẽ không được chọn nếu n-k chẵn.Rõ ràng ở bước 2 có cách chọn và bước 3 có được tổng cộng n số, trong đó k chạy từ 0 đến n. cách chọn. Lúc này, ta chọn Ví dụ 7: Cho n là một số nguyên dương. Xét bảng ô vuông n × n. Hỏi trong bảng đã cho có bao nhiêu hình vuông Lời giải Xét hình vuông như trên ( chỉ mang tính minh họa) Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Trang 10