Luận văn Thạc sĩ Toán học: Một số phương pháp đếm trong các bài toán hình học tổng hợp

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:74

Thêm vào BST

Báo xấu

13
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài được nghiên cứu với mong muốn sẽ cung cấp thêm cho các em học sinh phổ thông một tài liệu hay và bổ ích, nhằm đáp ứng được phần nào lòng đam mê, yêu thích và khám phá toán học của các học sinh, đồng thời tôi cũng mong rằng đây có thể là tài liệu bổ ích để các đồng nghiệp tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số phương pháp đếm trong các bài toán hình học tổng hợp

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG THÚY QUỲNH MỘT SỐ PHƯƠNG PHÁP ĐẾM TRONG CÁC BÀI TOÁN HÌNH HỌC TỔ HỢP LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2016
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG THÚY QUỲNH MỘT SỐ PHƯƠNG PHÁP ĐẾM TRONG CÁC BÀI TOÁN HÌNH HỌC TỔ HỢP LUẬN VĂN Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60.46.01.13 Người hướng dẫn khoa học: GS.TSKH. NGUYỄN VĂN MẬU THÁI NGUYÊN - NĂM 2016
i Mục lục Mở đầu 1 1 Một số kiến thức chuẩn bị 3 1.1 Các quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Quy tắc cộng và quy tắc nhân . . . . . . . . . . . . . . . . . 3 1.1.2 Tổ hợp và chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Một số nguyên lý cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Bất biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Nguyên lí Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.3 Nguyên lí cực hạn . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Phân loại và các phương pháp giải các bài toán đếm trong hình học tổ hợp 9 2.1 Phân loại các bài toán đếm . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Đếm đối tượng tạo bởi điểm, đoạn thẳng, đường thẳng . . . 9 2.1.2 Đếm đối tượng tạo thành miền trong mặt phẳng . . . . . . . 12 2.2 Các phương pháp giải bài toán đếm . . . . . . . . . . . . . . . . . . 14 2.2.1 Phương pháp sử dụng nguyên lí bất biến . . . . . . . . . . . 14 2.2.2 Phương pháp sử dụng nguyên lí Dirichlet . . . . . . . . . . . 22 2.2.3 Phương pháp sử dụng nguyên lí cực hạn . . . . . . . . . . . . 38 3 Các dạng toán liên quan 49 3.1 Bài toán về tô màu hình vẽ . . . . . . . . . . . . . . . . . . . . . . . 49 3.2 Đếm cấu hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.3 Phối hợp các phương pháp đếm khác nhau . . . . . . . . . . . . . . 64 Tài liệu tham khảo 71
1 Mở đầu Hình học tổ hợp là một phần quan trọng trong toán học nói chung và trong tổ hợp nói riêng, nó thường xuất hiện trong các đề thi học sinh giỏi và Olympic các cấp. Bài toán tổ hợp nói chung và hình học tổ hợp nói riêng thường là bài toán khó, rất phong phú và linh hoạt về cách giải. Tuy nhiên, ở nước ta hiện nay, tài liệu về tổ hợp chưa nhiều, tài liệu về hình học tổ hợp lại càng ít hơn. Do đó, tôi viết luận văn này với mong muốn sẽ cung cấp thêm cho các em học sinh phổ thông một tài liệu hay và bổ ích, nhằm đáp ứng được phần nào lòng đam mê, yêu thích và khám phá toán học của các học sinh, đồng thời tôi cũng mong rằng đây có thể là tài liệu bổ ích để các đồng nghiệp tham khảo. Luận văn này đề cập đến một số phương pháp chính để giải quyết các bài toán đếm trong hình học tổ hợp. Ngoài phần mở đầu, phần kết luận, nội dung của luận văn gồm ba chương. Chương 1 nhắc lại một số kiến thức chuẩn bị, liên quan đến các công thức đếm trong tổ hợp. Chương 2 đưa ra sự phân loại một số đối tượng đếm trong hình học tổ hợp và nêu ba phương pháp để giải quyết bài toán đếm. Phương pháp sử dụng nguyên lí bất biến là một phương pháp hiệu quả để giải quyết các bài toán đếm. Ta thường sử dụng nguyên lí bất biến trong những bài toán có một tính chất không thay đổi qua sự tác động, biến đổi của hệ thống. Phương pháp sử dụng nguyên lí Dirichlet là một phương pháp thông dụng để giải quyết các bài toán hình học tổ hợp. Dùng nguyên lí này trong nhiều
2 trường hợp ta dễ dàng chứng minh được sự tồn tại của một đối tượng với tính chất xác định, tuy rằng với nguyên lí này ta thường chỉ chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm được đối tượng cụ thể. Phương pháp sử dụng nguyên lí cực hạn vào giải các bài toán hình học tổ hợp là một phương pháp được vận dụng cho nhiều lớp bài toán khác nhau. Nguyên lí này dùng để giải các bài toán mà trong đối tượng phải xét của nó tồn tại các giá trị lớn nhất, giá trị nhỏ nhất theo một nghĩa nào đó và thường kết hợp với những phương pháp khác, đặc biệt là phương pháp phản chứng. Chương 3 nêu ra một số dạng toán liên quan như là bài toán tô màu, bài toán đếm cấu hình và một số bài toán hình học tổ hợp trong các đề thi học sinh giỏi quốc gia và quốc tế. Trong mỗi chương các bài tập thường được dẫn dắt theo những chủ đề nhất định. Đồng thời, mỗi bài đều có lời giải chi tiết, ngắn gọn, sáng tạo và bất ngờ. Tác giả hi vọng, chính điều này sẽ giúp người đọc tìm thấy cho mình những kiến thức bổ ích và kích thích sự ham hiểu biết và lòng say mê học toán của người đọc. Luận văn này được hoàn thành dưới sự hướng dẫn tận tình và nghiêm túc của thầy giáo GS.TSKH Nguyễn Văn Mậu. Tôi xin được bày tỏ lòng kính trọng và biết ơn sâu sắc đến thầy. Tôi xin trân trọng cảm ơn Ban Giám hiệu, Ban chủ nhiệm Khoa Toán Trường Đại học Khoa học, Đại học Thái Nguyên, các thầy cô giảng viên đã quan tâm, tạo điều kiện giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu tại Trường. Thái Nguyên, ngày 29 tháng 5 năm 2016. Học viên Dương Thúy Quỳnh
3 Chương 1 Một số kiến thức chuẩn bị 1.1 Các quy tắc đếm cơ bản 1.1.1 Quy tắc cộng và quy tắc nhân Quy tắc cộng: Nếu công việc A có hai phương án thực hiện (loại trừ lẫn nhau), phương án 1 có n1 cách thực hiện, phương án 2 có n2 cách thực hiện thì công việc A có n1 + n2 cách thực hiện. Trên ngôn ngữ tập hợp: A∩B = ∅ thì |A ∪ B| = |A| + |B|. Quy tắc nhân: Nếu công việc A có thể chia thành 2 công đoạn tiếp nối nhau, công đoạn 1 có n1 cách thực hiện, công đọan 2 có n2 cách thực hiện thì công việc A có n1 .n2 cách thực hiện. Trên ngôn ngữ tập hợp: |A.B| = |A|.|B|. Quy tắc phần bù: |A| = |X| − |A|, trong đó A là phần bù của A trong X. 1.1.2 Tổ hợp và chỉnh hợp Xét tập hợp X gồm n phần tử. Từ tập hợp cơ bản này, ta có thể xây dựng các đối tượng tổ hợp phong phú. Tập các tập con của tập X : Tập các tập con của X được ký hiệu là P (X). Dễ thấy |P(X)| = 2n . Các tập con của một tập hợp là một đối tượng xuất hiện khá nhiều trong các bài toán đếm. Chỉnh hợp: Chỉnh hợp chập k của một tập hợp là một bộ k phần tử phân
4 biệt được sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1, 2, 3} và k = 2 thì ta có các chỉnh hợp là (1, 2), (1,3), (2, 1), (2, 3), (3, 1), (3, 2). Số các chỉnh hợp chập k của n phần tử được ký hiệu là Akn . Hoán vị: Hoán vị của n phần tử là chỉnh hợp chập n của n phần tử đó, nói cách khác, là một cách sắp thứ tự các phần tử đó. Hoán vị của X còn có thể định nghĩa như một song ánh từ X vào X . Số các hoán vị của n phần tử được ký hiệu là Pn . Tổ hợp: Tổ hợp chập k của một tập hợp là một bộ k phần tử phân biệt không sắp thứ tự của tập hợp ấy. Nói cách khác, đó là một tập con k phần tử. Ví dụ nếu X = {1, 2, 3} và k = 2 thì ta có các tổ hợp là {1, 2}, {1, 3}, {2, 3}. Số các tổ chập k của n phần tử được ký hiệu là Cnk . Chỉnh hợp lặp: Chỉnh hợp lặp chập k của một tập hợp là một bộ k phần tử không nhất thiết phân biệt được sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1, 2, 3} và k = 2 thì ta có các chỉnh hợp lặp là {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}. Số các chỉnh hợp lặp chập k của k n phần tử được ký hiệu là An . Tổ hợp lặp: Tổ hợp lặp chập k của một tập hợp là một bộ k phần tử không nhất thiết phân biệt không sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1, 2, 3} và k = 2 thì ta có các tổ hợp lặp là {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}. Số các tổ hợp lặp chập k của n phần tử được ký hiệu k là C n . 1.2 Một số nguyên lý cơ bản 1.2.1 Bất biến a) Khái niệm bất biến Giả sử ta có một hệ thống (X) các đại lượng và các phép biến đổi theo thứ tự. Tính chất P được gọi là bất biến sau s bước trong hệ thống (X) nếu cứ sau s bước biến đổi ta đều nhận lại được tính chất P . b) Ứng dụng nguyên lý bất biến
5 Bất biến là những đại lượng (hay tính chất) không thay đổi trong quá trình chúng ta thực hiện các phép biến đổi. Chẳng hạn khi thực hiện phép tịnh tiến thì khoảng cách giữa hai điểm sẽ không thay đổi. Với phép vị tự thì khác, khoảng cách có thể sẽ thay đổi nhưng sẽ có một bất biến khác, đó là tỉ lệ giữa hai đoạn thẳng. Có hai mẫu bài toán tổng quát thường được giải quyết bằng bất biến Bài toán tổng quát 1.1. Có một tập hợp các trạng thái X và tập hợp các phép biến đổi T từ X vào X . Có hai trạng thái a và b thuộc X , hỏi có thể dùng hữu hạn các phép biến đổi thuộc T để đưa trạng thái a về trạng thái b được không? Bài toán tổng quát 1.2. Có một tập hợp các trạng thái X và tập hợp các phép biến đổi T từ X vào X . Cần chứng minh rằng bắt đầu từ một trạng thái a bất kì, sau một số hữu hạn các phép biến đổi từ T , ta sẽ đi đến trạng thái kết thúc (trong nhiều trường hợp đó là trạng thái ổn định, tức là sẽ không thay đổi khi tiếp tục tác động các phép biến đổi từ T ). 1.2.2 Nguyên lí Dirichlet a) Nguyên lí Dirichlet Nguyên lí Dirichlet - còn gọi là nguyên lí chuồng chim bồ câu (The Pi- geonhole Principle) - hoặc nguyên lý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật vào ngăn kéo (The Drawer Principle). Nguyên lí này được nhà toán học người Đức Johann Dirichlet phát biểu đầu tiên năm 1834 khi ông đề cập tới nó với tên gọi "nguyên lí ngăn kéo". Vì vậy, một tên gọi thông dụng khác của nguyên lý chuồng bồ câu chính là "nguyên lí ngăn kéo Dirichlet" hay đôi khi gọi gọn là "nguyên lí Dirichlet". Trong một số ngôn ngữ như tiếng Pháp, tiếng Ý và tiếng Đức, nguyên lí này cũng vẫn được gọi bằng tên "ngăn kéo" chứ không phải "chuồng bồ câu". Nguyên lí Dirichlet cơ bản:
6 Nếu nhốt n + 1 con thỏ vào n cái chuồng thì bao giờ cũng có ít nhất một chuồng chứa ít nhất hai con thỏ, với n là số nguyên dương. Nguyên lí Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít hN i nhất đồ vật (ở đây kí hiệu [α] để chỉ phần nguyên của số α). k Chứng minh. hN i Giả sử mọi hộp đều chứa ít hơn vật. Khi đó tổng số đồ vật là: k h N i hN i k −1
7 + Số "thỏ" phải hiều hơn số "chuồng"; + "Thỏ" phải được nhốt hết vào các "chuồng", nhưng không bắt buộc "chuồng" nào cũng phải có "thỏ". Thường phương pháp Dirichlet được áp dụng kèm theo phương pháp phản chứng. Ngoài ra nó còn có thể áp dụng với các phép biến hình. 1.2.3 Nguyên lí cực hạn a) Nguyên lý cực hạn Nguyên lí cực hạn được phát biểu đơn giản như sau: Nguyên lí 1: Trong một tập hữu hạn và khác rỗng các số thực luôn luôn có thể chọn được số bé nhất và số lớn nhất. Nguyên lí 2: Trong một tập khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất. b) Ứng dụng nguyên lý cực hạn Sử dụng nguyên lí cực hạn là một phương pháp được vận dụng cho nhiều lớp bài toán khác, đặc biệt nó có ích khi giải các bài toán tổ hợp nói chung và hình học nói riêng. Trong quá trình tìm kiếm lời giải nhiều bài toán hình học, sẽ rất có lợi nếu chúng ta xem xét các phần tử biên, phần tử tới hạn (cực biên) nào đó, tức là phần tử mà tại đó mỗi đại lượng hình học có thể nhận giá trị lớn nhất hoặc giá trị nhỏ nhất, chẳng hạn như cạnh lớn nhất, cạnh nhỏ nhất của một tam giác, góc lớn nhất hoặc góc nhỏ nhất của một đa giác . . . Những tính chất của các phần tử biên, phần tử tới hạn nhiều khi giúp chúng ta tìm kiếm được lời giải thu gọn của bài toán. Nguyên lí cực hạn thường được sử dụng kết hợp với các phương pháp khác, đặc biệt là phương pháp phản chứng, được vận dụng trong trong trường hợp tập các giá trị cần khảo sát là tập hợp hữu hạn (nguyên lí 1) hoặc có thể có vô hạn nhưng tồn tại một phần tử lớn nhất hoặc nhỏ nhất (nguyên lí 2). Khi vận dụng nguyên lí này, ta phải tiến hành các bước sau: Bước 1: Chứng minh rằng trong tất cả các giá trị cần khảo sát luôn tồn
8 tại giá trị lớn nhất hoặc giá trị nhỏ nhất. Bước 2: Xét bài toán trong trường hợp riêng khi nó nhận giá trị này (nhỏ nhất hoặc lớn nhất). Bước 3: Chỉ ra một mâu thuẫn, chỉ ra một giá trị còn nhỏ hơn (hay lớn hơn) giá trị ta đang khảo sát. Theo nguyên lí của phương pháp phản chứng, ta sẽ suy ra điều phải chứng minh.
9 Chương 2 Phân loại và các phương pháp giải các bài toán đếm trong hình học tổ hợp 2.1 Phân loại các bài toán đếm 2.1.1 Đếm đối tượng tạo bởi điểm, đoạn thẳng, đường thẳng Bài toán 2.1. Một lưới tạo bởi m đường thẳng ngang và n đường thẳng đứng. Có bao nhiêu đỉnh phân biệt trong lưới này? Lời giải. Mỗi đường thẳng ngang chứa n điểm (đó là giao điểm của đường thẳng đó với những đường thẳng đứng) và có m đường thẳng như vậy. Do đó tổng số điểm giao là m.n. Bài toán 2.2. Mỗi cạnh AB và CD của hình chữ nhật ABCD được chia thành m phần bằng nhau, còn mỗi cạnh BC và AD được chia thành n phần bằng nhau. Bằng cách nối các điểm tương ứng ở các cạnh đối nhau tạo ra một lưới hình chữ nhật. Hãy tìm số giao điểm tạo bởi đường chéo AC và những đường lưới. Lời giải. Ta có m + 1 đường thẳng ngang và n + 1 đường thẳng đứng. Đường chéo
10 cắt tất cả các đường thẳng đã cho nhưng có một số điểm trùng vào điểm lưới. Dễ thấy điểm trùng với điểm lưới là điểm nằm trên cả đường thẳng ngang và đường thẳng đứng, như vậy những giao là m + n + 1 − (m, n) (trong đó (m, n) là ước chung lớn nhất của m và n). Bài toán 2.3. Số giao điểm lớn nhất là bao nhiêu khi ta vẽ n đường thẳng trong cùng một mặt phẳng? Lời giải. Số giao điểm lớn nhất chỉ xuất hiện khi và chỉ khi các đường thẳng đôi một có giao điểm phân biệt, nhưng không có ba đường nào đồng quy. Trong trường hợp này tồn tại n − 1 giao điểm trên mỗi đường thẳng. Do đó số điểm n (n − 1) giao nhau là Cn2 = . 2 Bài toán 2.4. Số giao điểm lớn nhất là bao nhiêu khi ta vẽ n đường tròn trong cùng một mặt phẳng ? Lời giải. Lập luận tương tự bài toán trên, số giao điểm là lớn nhất khi và chỉ khi các đường tròn đôi một có hai giao điểm phân biệt, nhưng không tồn tại điểm giao nào nằm trên cùng ba đường tròn. Do đó số điểm giao nhau là 2.Cn2 = n(n − 1). Bài toán 2.5. Số giao điểm lớn nhất là bao nhiêu khi ta vẽ n hình tam giác (hình vuông) trong cùng một mặt phẳng? Lời giải. Vì mỗi cạnh của một tam giác chỉ có thể giao với nhiều nhất hai cạnh của một tam giác khác nên những cạnh của hai tam giác bất kì không thể có nhiều hơn 6 giao điểm. Như vậy nếu mọi cặp tam giác có 6 điểm chung và không có điểm chung nào là điểm chung của hơn 2 tam giác thì ta có thể nhận được 6.Cn2 = 3n(n − 1). Bằng phương pháp tương tự, ta nhận được kết quả số điểm giao lớn nhất là 4n.(n − 1) với những hình vuông.
11 Bài toán 2.6. Cho hai đường thẳng d1 và d2 song song. Lấy các điểm A1 , A2 , . . . , Am nằm trên d1 và các điểm B1 , B2 , . . . , Bn nằm trên d2 . Ta dựng tất cả giao điểm của các đoạn thẳng Ai Bj , i = 1, . . . , m; j = 1, . . . , n. Từ các đoạn thẳng đó ta có thể nhận được số giao điểm lớn nhất là bao nhiêu? Lời giải. Nếu số giao điểm là lớn nhất thì không tồn tại ba đương thẳng đồng quy trong cấu trúc này. Do đó nếu chọn hai điểm trên d1 và hai điểm trên d2 thì chúng xác định một giao điểm. 2 m (m − 1) Số cách chọn hai điểm trên d1 là Cm = và số cách chọn hai điểm 2 n (n − 1) trên d2 là Cn2 = . 2 m.n. (m − 1) . (n − 1) Như vậy số giao điểm là . 4 Bài toán 2.7. Có n−giác lồi A1 A2 . . . An . Xác định số giao điểm của các đường chéo của đa giác A1 A2 . . . An nằm trong đa giác đó. Lời giải. Ta xét một đường chéo cố định A1 Ak (k = 3, 4, . . . , n − 1) và xác định số giao điểm trên đường chéo này. Trong một nửa mặt phẳng xác định bởi đường thẳng A1 Ak có k − 2 điểm và nửa mặt phẳng còn lại chứa n − k điểm của n − 2 đỉnh còn lại của đa giác lồi A1 A2 . . . An . Do đó đường chéo A1 Ak giao với những đường chéo khác tại (n−k)(k −2) điểm nên số giao điểm trên tất cả các đường chéo xuất phát từ A1 là n−1 n−1 (n + 2) k − k 2 − 2n P P a1 (n) = (n − k) (k − 2) = k=3 k=3 (n − 1) (n − 2) (n − 3) = . 6 Nếu ta cộng tất cả các số giao điểm này của tất cả các đỉnh A1 , A2 ,. . . , An của đa giác thì ta đếm số điểm giao 4 lần. Do đó tổng số tất cả các giao điểm của tất cả các đường chéo là n n (n − 1) (n − 2) (n − 3) a1 (n) = = Cn4 . 4 24
12 Bài toán 2.8. Phần trong của mỗi cạnh hình vuông ta chọn n điểm khác nhau. Tìm số tất cả các tam giác mà đỉnh của nó là những điểm ta vừa lấy. Lời giải. 3 Từ 4n điểm đã chọn ta được tổng cộng C4n bộ ba điểm, trong số đó có 4.Cn3 bộ ba điểm không tạo thành tam giác, do bộ ba điểm đó đều nằm trên cùng một cạnh của hình vuông. Do đó số tam giác được tạo thành là 3 C4n − 4.Cn3 = 2n2 (5n − 3). Bài toán 2.9. Cho n−giác lồi H . Tìm tất cả số tam giác mà đỉnh là đỉnh của H và cạnh là đường chéo của H. Lời giải. Từ số tất cả các tam giác có đỉnh của H ta trừ đi số tam giác có một cạnh hoặc hai cạnh là cạnh của đa giác đã cho. Tổng số tất cả các tam giác có đỉnh của H là Cn3 . Số tam giác có một cạnh là cạnh của đa giác là n(n − 4), vì mỗi cạnh trong n cạnh của đa giác có thể chọn đỉnh thứ ba của tam giác trong n − 4 đỉnh còn lại. Số tam giác có hai cạnh là cạnh của đa giác là n, vì mỗi tam giác có hai cạnh kề nhau của đa giác, tức là tương ứng với bộ 3 đỉnh liên tiếp của đa giác đã cho. n (n − 4) (n − 5) Vậy số tam giác cần tính là Cn3 − n(n − 4) − n = . 6 2.1.2 Đếm đối tượng tạo thành miền trong mặt phẳng Bài toán 2.10. Trong mặt phẳng, cho n đường thẳng phân biệt. Gọi P (n) là số miền mặt phẳng mà các đường thẳng trên tạo ra. Tìm giá trị lớn nhất của số P (n). Lời giải. Dễ thấy P (1) = 2. Giả sử biết số lớn nhất P (n) miền mặt phẳng có thể được chia ra bởi các đường thẳng đã cho q1 , q2 ,. . . , qn . Bằng cách thêm vào một đường thẳng nữa
13 qn+1 , số những phần trong mặt phẳng tăng lên bằng số những phần mà đường thẳng qn+1 được chia ra với các đường thẳng q1 , q2 ,. . . , qn . Tồn tại nhiều nhất n những giao điểm như vậy trên đường thẳng qn+1 , như vậy nó chia đường thẳng nhiều nhất thành n + 1 phần. Hai trong chúng là nửa đường thẳng và còn lại là những đoạn thẳng. Do đó có quan hệ P (n + 1) ≤ P (n) + n + 1. Để xác định công thức P (n) theo biến n, ta dùng kỹ thuật sau P (1) = 2, P (2) ≤ P (1) + 2, P (3) ≤ P (2) + 3, ..................... P (n) ≤ P (n − 1) + n. Cộng hai vế của các bất đẳng thức trên ta được n (n + 1) n2 + n + 2 P (n) ≤ 1 + (1 + 2 + 3 + · · · + n) = 1 + = . 2 2 n2 + n + 2 Giá trị P (n) = khi và chỉ khi với mỗi i = 2, 3, . . . , n đường thẳng 2 qi có đúng i − 1 giao điểm với những đường thẳng trước nó q1 , q2 , . . . , qn−1 . Điều này xảy ra khi hệ gồm n đường thẳng đã cho không có hai đường thẳng nào song song và không có ba đường thẳng nào đồng quy. Bài toán 2.11. Trong mặt phẳng, cho n đường tròn phân biệt. Gọi K(n) là số miền mặt phẳng được chia ra bởi n đường tròn phân biệt đó.Tìm giá trị lớn nhất của K(n). Lời giải. Dễ thấy K(1) = 2. Giả sử đã biết số có khả năng lớn nhất K(n) miền mặt phẳng được chia ra bởi n đường tròn phân biệt. Ta thêm đường tròn thứ n + 1 vào mặt phẳng, nó sẽ có nhiều nhất 2n giao điểm với những đường tròn đã cho và nó xác định nhiều nhất 2n cung trên đường tròn mới thêm vào. Mỗi cung chia miền chứa nó ra thêm một miền mới, do đó K(n + 1) ≤ K(n) + 2n.
14 Từ đây ta cho từng giá trị của n và cộng theo vế ta được K(n) ≤ 2 + 2 + 4 + 6 + · · · + 2(n − 1) = n2 − n + 2. Đẳng thức chỉ xảy ra nếu hệ thống n đường tròn đôi một cắt nhau tại hai điểm phân biệt và không có hai đường tròn nào cùng đi qua một điểm. Để xây dựng một cấu trúc hình như thế, ta chọn một đoạn thẳng bất kì AB có độ dài d, xét hệ gồm n đường tròn nhau có bán kính d và tâm của chúng khác nhau, cùng nằm bên trong đoạn AB . Hai đường tròn bất kì trong hệ thống này có đúng hai giao điểm chung phân biệt vì khoảng cách giữa hai tâm nhỏ hơn d. Nếu ba đường tròn cùng đi qua một điểm M thì tâm của những đường tròn này tạo thành một bộ ba điểm cùng nằm trên một đường thẳng và có cùng khoảng cách tới M , điều này không thể xảy ra. Do đó giá trị lớn nhất của K(n) bằng n2 − n + 2. 2.2 Các phương pháp giải bài toán đếm 2.2.1 Phương pháp sử dụng nguyên lí bất biến Bài toán 2.12. Trên bảng đen ta viết 2015 dấu cộng (+) và 2016 dấu trừ (−). Mỗi lần thực hiện, cho phép xóa đi hai dấu tùy ý và viết thay vào đó một dấu cộng nếu hai dấu xóa đi là như nhau, và dấu trừ nếu ngược lại. Lặp lại phép tính đó 4030 lần. Hỏi trên bảng còn lại dấu gì? Lời giải. Giả sử thay dấu cộng bởi số 1, thay dấu trừ bởi số −1. Khi đó phép toán đã cho tương đương với việc thay hai số tùy ý bởi tích của chúng. Phép tính này không làm thay đổi tích của tất cả các số đã cho. Như vậy tích của tất cả các số đã cho là một bất biến trong quá trình lặp lại phép toán. Tại trạng thái xuất phát, tích này bằng 1 nên ở trạng thái cuối cùng, tích đó cũng phải bằng 1. Sau 4030 lần thực hiện, ta chỉ còn một số trên bảng, số đó phải là 1. Do đó dấu còn lại trên bảng là dấu (+). Bài toán 2.13. Cho một bảng hình vuông có cạnh 10cm được chia ra thành 100 ô vuông nhỏ với cạnh 1cm. Ta đặt lên bảng hình vuông đó 25 hình chữ
15 nhật như nhau, mỗi hình chữ nhật có chiều dài 4cm, chiều rộng 1cm và được chia thành 4 ô vuông có cạnh là 1cm. Có thể sắp xếp những hình chữ nhật trên bảng hình vuông sao cho chúng phủ toàn bộ bảng hình vuông hay không? Lời giải. Ta tô bảng vuông bằng màu đen trắng như hình vẽ: Ta nhận được 25 ô đen và 75 ô trắng. Ta chú ý là đặt những hình chữ nhật trên bảng vuông sao cho mỗi ô vuông của hình chữ nhật trùng với một ô vuông nào đó của bảng vuông. Hình chữ nhật này sẽ phủ lên hoặc là 2 hoặc là 0 ô vuông đen. Từ đó suy ra khi đặt tất cả 25 hình chữ nhật trên bảng vuông, chúng sẽ phủ kín một số chẵn những ô vuông đen. Bởi vì số lượng của ô vuông đen đã tô là 25, nó không phải là một số chẵn. Như vậy không thể phủ bằng 25 hình chữ nhật trên hình vuông đã cho. Bài toán 2.14. Một nền nhà hình chữ nhật được lát kín bằng những viên gạch men kích thước 2 × 2 và 1 × 4. Khi sửa nền nhà, người ta phải dỡ tất cả các viên gạch men đã lát, nhưng không may bị vỡ mất một viên kích thước 2 × 2. Vì không có loại gạch men kích thước 2 × 2 nên người ta phải thay viên bị vỡ bởi các viên kích thước 1 × 4. Chứng minh rằng bây giờ nền nhà không thể được lát kín bởi các viên gạch ấy. Lời giải.
16 Chia nền nhà thành các hình vuông kích thước 1 × 1 và tô đen các ô ở dòng lẻ, cột lẻ. Ta thấy mỗi viên gạch 1×4 chiếm 4 ô trên nền nhà sẽ chứa một số chẵn các ô đen, còn các viên gạch 2×2 chiếm đúng một ô đen. Do lúc đầu tất cả gạch lát kín nền nhà nên số viên gạch 2×2 có cùng tính chẵn lẻ với số ô được tô đen. Vì vậy, nếu số các viên gạch 2×2 bớt đi một đơn vị, tức là tính chẵn lẻ bị thay đổi (khác với tính chẵn lẻ của các ô đen). Do đó nền nhà không thể được lát kín. Bài toán 2.15. Cho một bàn cờ vua 8 × 8. Hỏi rằng quân mã có thể đi từ nước đầu tiên ở ô dưới cùng bên trái và kết thúc ở ô trên cùng bên phải hay không? (với điều kiện nó phải đi qua tất cả các ô trên bàn cờ và mỗi ô chỉ đi qua đúng một lần). Lời giải. Để đi qua tất cả các ô trên bàn cờ, từ ô dưới cùng bên trái đến ô trên cùng bên phải, mỗi ô chỉ đi qua một lần, quân mã phải đi tất cả 63 nước. Do ở mỗi nước đi, quân mã sẽ chuyển từ ô đen sang ô trắng hoặc ngược lại, nên sau 63 nước đi, ô cờ mà quân mã đứng sẽ đổi màu so với vị trí ban đầu. Vì ô dưới cùng bên trái và ô trên cùng bên phải luôn cùng đen hoặc cùng trắng nên không thể tồn tại một cách đi thỏa mãn đề bài. Bài toán 2.16. Dùng những viên gạch 2 × 2 và 3 × 3 để lát sân kích thước n × n. Xác định điều kiện của sân n × n (n ≥ 2) để lát được mà không phải cắt gạch. Lời giải.
17 Với n chẵn, ta có thể dùng toàn gạch 2 × 2 để lát được. Với n lẻ. Ta xét các trường hợp sau: + Trường hợp 1: n chia hết cho 3. Có thể lát được bằng cách dùng toàn gạch 3 × 3. + Trường hợp 2: n không chia hết cho 3. Chia sân thành bảng ô vuông kích thước 1 × 1. Ta tô màu đỏ cho các ô ở cột lẻ, tô màu xanh cho các ô ở n − 1 n−1 cột chẵn. Có tất cả n + 1 ô màu đỏ và n + 1 ô màu xanh. n n Nhận thấy rằng: mỗi viên gạch 2 × 2 luôn phủ 2 ô màu đỏ và hai ô màu xanh, và mỗi viên gạch 3 × 3 phủ 6 ô màu đỏ và 3 ô màu xanh hoặc 3 ô màu đỏ và 6 ô màu xanh. Nếu sân bị phủ kín thì hiệu của tổng số ô màu đỏ và tổng số ô màu xanh chia hết cho 3. Tuy nhiên, thực tế trong bảng hiệu đó là n không chia hết cho 3. Điều mâu thuẫn này chứng tỏ trường hợp này sân không thể được lát kín. Vậy kích thước sân là 2k × 2k hoặc 3k × 3k . Bài toán 2.17. Các dấu cộng (+) và dấu trừ (−) được viết vào các ô trong một bảng 6 × 6 như trong hình vẽ. Mỗi lần thực hiện, cho phép đảo ngược tất cả các dấu trong cùng một hàng, trong cùng một cột, hoặc dọc theo một đường bất kì song song với một trong hai đường chéo của bảng (đặc biệt có thể dỏ dấu của các ô ở góc). Có thể hay không, bằng cách thực hiện các phép tính trên đây, nhận được một bảng không có dấu trừ? Lời giải.