Luận văn Thạc sĩ Khoa học: Một số bài toán hình học tổ hợp

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

Thêm vào BST

Báo xấu

56
lượt xem 9
download

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

Các bài toán hình học tổ hợp là các bài toán hay và được nhiều người quan tâm. Trong những đề thi học sinh giỏi quốc gia và quốc tế cũng thường xuyên xuất hiện những bài toán về hình học tổ hợp. Đó là lý do luận văn này trình bày một số bài toán về hình học tổ hợp.

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ĩ Khoa học: Một số bài toán hình học tổ hợp

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN _______________******______________ VŨ MINH HẢI MỘT SỐ BÀI TOÁN HÌNH HỌC TỔ HỢP LUẬN VĂN THẠC SĨ KHOA HỌC Hà nội - 2015 1
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN _______________******______________ VŨ MINH HẢI MỘT SỐ BÀI TOÁN HÌNH HỌC TỔ HỢP Chuyên ngành: Phương pháp toán sơ cấp. Mã số: 60460113. LUẬN VĂN THẠC SĨ KHOA HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC PGS.TS. LÊ ANH VINH Hà nội – 2015 2
MỤC LỤC CHƢƠNG 1. BÀI TOÁN PHỦ HÌNH .....................................................................5 1.1. Một số lý thuyết cơ sở ................................................................................................ 5 1.2. Một số bài toán phủ hình .......................................................................................... 6 CHƢƠNG 2. BÀI TOÁN ĐỒ THỊ, TÔ MÀU ......................................................19 2.1. Lý thuyết cơ bản về bài toán tô màu ....................................................................... 19 2.2. Phương pháp tô màu giải bài toán hình học.......................................................... 20 2.2.1. Một số bài toán tô màu đồ thị ........................................................................ 20 2.2.2. Một số bài toán tô màu ô vuông ..................................................................... 37 2.2.3. Một số bài toán dùng phƣơng pháp tô màu ô vuông và tính chất bất biến41 CHƢƠNG 3. NGUYÊN LÝ CỰC HẠN ................................................................47 3.1. Nguyên lý cực hạn ................................................................................................... 47 3.2. Ứng dụng nguyên lý cực hạn .................................................................................. 47 3.2.1. Một số bài toán đánh giá góc.......................................................................... 47 3.2.2. Một số bài toán đánh giá khoảng cách, độ dài ............................................. 54 3.2.3. Một số bài toán đánh giá diện tích, thể tích .................................................. 63 1
LỜI NÓI ĐẦU Các bài toán hình học tổ hợp là các bài toán hay và được nhiều người quan tâm. Trong những đề thi học sinh giỏi quốc gia và quốc tế cũng thường xuyên xuất hiện những bài toán về hình học tổ hợp. Đó là lý do luận văn này trình bày một số bài toán về hình học tổ hợp. Luận văn “Một số bài toán hình học tổ hợp” được chia làm 3 chương: Chƣơng 1. Trình bày một số lý thuyết về bài toán phủ hình và cách giải những bài toán dạng đó. Chƣơng 2. Trình bày về các bài toán đồ thị, tô màu và một số bài toán thuộc dạng này được sử dụng trong các kì thi học sinh giỏi trong nước và quốc tế. Chƣơng 3. Trình bày về nguyên lý cực hạn và các bài toán hình học tổ hợp sử dụng nguyên lí cực hạn. Mục đích của luận văn là trình bày ngắn họn dễ hiểu lý thuyết về các bài toán : phủ hình, đồ thị, tô màu, bài toán sử dụng nguyên lý cực hạn và trình bày chi tiết cách giải các bài toán đó. Mặc dù có nhiều cố gắng trong việc nghiên cứu và thực hiện luận văn này nhưng không thể tránh khỏi có sai sót, kính mong được sự góp ý quý báu của các thầy, cô và các bạn. Tôi xin chân thành cảm ơn. 4
CHƢƠNG 1. BÀI TOÁN PHỦ HÌNH Bài toán phủ hình là một dạng bài toán có nhiều trong thực tế. Ví dụ như là việc lát vỉa hè, quảng trường, sàn nhà, ... bằng những viên gạch đa giác giống nhau. Câu hỏi được đặt ra ở đây là “Những viên gạch đa giác lồi giống nhau như thế nào thì có thể lát kín được mặt phẳng?”. Mặt phẳng được lấp đầy bởi những đa giác giống nhau sao cho hai đa giác tuỳ ý không có điểm chung, nhưng có thể có chung cạnh chung đỉnh. Từ câu hỏi trên có một số các dạng toán được sinh ra, đó là “Phủ hình bằng mạng lưới ô vuông”, “Phủ đa giác lồi bằng những đa giác vị tự (hoặc đồng dạng) với chính nó”, ... Dưới đây luận văn sẽ trình bày một số định lí, hệ quả và những bài toán cho dạng bài toán phủ hình như thế. 1.1. Một số lý thuyết cơ sở Một hệ thống vô hạn ô vuông tạo nên mặt phẳng được gọi là mạng lưới đỉnh ô vuông. Các ô vuông đó được gọi là ô vuông cơ sở. Các đỉnh ô vuông là các điểm nguyên (điểm có cả tung độ và hoành độ là các số nguyên) của một hệ trục toạ độ song song với các cạnh hình vuông cơ sở và có đơn vị gốc là độ dài cạnh hình vuông cơ sở. Một đa giác có đỉnh là các đỉnh lưới của mạng ô vuông được gọi là đa giác nguyên. Ta có một tính chất cơ bản của mạng lưới ô vuông là định lí sau Định lí 1. Đa giác đều duy nhất có đỉnh tại các điểm lưới ô vuông là hình vuông. Mạng lưới ô vuông có một ứng dụng khá thực tế đó là sử dụng để tính diện tích các hình phẳng. Ta có các định nghĩa sau Đa giác nguyên : Đa giác có đỉnh là các điểm có toạ độ nguyên. 5
Tam giác đơn: Tam giác có các đỉnh có toạ độ nguyên mà không chứa đỉnh nguyên nào bên trong hoặc trên cạnh của nó. Định lí 2. Diện tích của tam giác đơn trên mạng lưới ô vuông đơn vị đúng 1 bằng . 2 Định lí 3. (Định lí Picard) Các đỉnh của một đa giác P có cạnh không tự cắt (không nhất thiết phải lồi) nằm ở các điểm nguyên. Bên trong nó có n điểm nguyên, còn trên biên m điểm nguyên. Khi đó diện tích của nó bằng m SP  n  1 2 1.2. Một số bài toán phủ hình Sau đây luận văn trình bày một số bài toán phủ hình. Những bài toán này được tham khảo ở các tài liệu [1], [2] và [4] mục tài liệu tham khảo. Bài toán 1. Trên một tờ giấy có một vết mực diện tích nhỏ hơn 1. Chứng minh rằng ta có thể kẻ carô tờ giấy với các hình vuông đơn vị (cạnh 1) sao cho không có đỉnh của mạng lưới ô vuông nào rơi vào vết mực cả. Giải. Giả sử ta phủ tờ giấy bằng một mạng lưới ô vuông đơn vị bất kì. Sau đó nếu đem cắt các ô vuông đơn vị rời ra và xếp chồng lên nhau. Giả sử phần ô vuông bị thấm mực có thể thấm thẳng qua tất cả các ô vuông đó. Khi đó vì diện tích của vết mực nhỏ hơn 1. Nên trong ô vuông có ít nhất 1 điểm là không bị thấm mực. Ta đánh dấu điểm đó. Ta đem trải các ô vuông đó ra như cũ. Các điểm được đánh dấu như trên sẽ tạo thành một lưới ô vuông phủ tờ giấy mà không có điểm nào trong chúng nằm trong vết mực. Vậy bài toán được giải.  6
Bài toán 2. Cho tam giác nhọn ABC có diện tích bằng 1. Chứng minh rằng tồn tại một tam giác vuông có diện tích không vượt quá 3 phủ kín ABC . A Giải. Gọi BC là cạnh lớn nhất của tam giác nhon ABC có diện tích bằng R 1. Kẻ trung tuyến AM. Đặt MA = R. D E Vẽ đường tròn (M;R) cắt BC ở D, E. B H M C a Ta có DAE  90 . 0 Các điểm B, C đối xứng nhau qua M, chúng cùng nằm trong đường tròn. Ta chứng minh rằng tam giác vuông ADE là tam giác phải tìm. Rõ ràng ADE phủ ABC , cần chứng minh S ADE  3 . Kẻ đường cao AH. Đặt MB = MC = a. Ta có 1 2S 2 1 S ADE  DE. AH  R. AH ; AH  ABC   2 BC 2a a R nên S ADE  . a R Ta chứng minh  3. a Thật vậy, trong hai góc AMB, AMC tồn tại một góc lớn hơn hoặc bằng 900 , chẳng hạn AMC  900 , do đó AM 2  MC 2  AC 2 . Suy ra R2  a 2  AC 2  BC 2  4a 2 R  R 2  3a 2   3. a Vậy tam giác ADE vuông có diện tích không vượt quá 3 phủ kín ABC .  7
Bài toán 3. Một khu vực dân cư có hình tứ giác lồi. Tại trung điểm mỗi cạnh tứ giá, người ta đặt một trung tâm phát và nhận sóng. Vùng phát sóng và nhận sóng lớn nhất là hình tròn có đường kính là cạnh đó của tứ giác. Có thể khẳng định rằng toàn bộ khu vực dân cư ấy đều được phủ sóng hay không? Giải. A Giả sử có điểm M nằm trong khu B dân cư có hình tứ giác lồi ABCD mà không bị phủ bởi hình tròn nào như M hình vẽ. C D Lúc đó do M nằm ngoài cả 4 đường tròn có đường kính AB, BC, CD, DA nên AMB  900 , BMC  900 , CMD  900 , DMA  900. Suy ra tổng bốn góc trên nhỏ hơn 3600 , vô lí. Vậy không tồn tại điểm M như thế. Hay có thể khẳng định là khu dân cư ấy đều được phủ sóng.  Bài toán 4. Cho 100 điểm trên mặt phẳng, hai điểm nào cũng có khoảng cách không quá 1, ba điểm nào cũng là đỉnh của một tam giác tù. Chứng minh 1 rằng tồn tại một hình tròn có bán kính phủ 100 điểm đã cho. 2 Giải. Gọi A, B là hai điểm có khoảng cách lớn nhất trong 100 điểm đã cho, ta có AB  1. Vẽ đường tròn có đường kính AB, hình tròn này có bán kính không 1 quá . Ta chứng minh rằng hình tròn 2 đó chứa mọi điểm đã cho. 8
Thật vậy, vẽ hai đường thẳng vuông góc với AB tại A và tại B tạo thành một dải. Nếu tồn tại một điểm C đã cho nằm ngoài dải thì hoặc BC > AB hoặc AC > AB, trái với cách chọn hai điểm A, B. Nếu tồn tại một điểm C đã cho nằm trên dải và nằm ngoài hình tròn thì  ABC không có góc tù, trái với đề bài.  Bài toán 5. Cho bốn điểm trên mặt phẳng, hai điểm nào cũng có khoảng cách lớn hơn 1. Chứng minh rằng không thể phủ tất cả bốn điểm ấy bởi một hình tròn có đường kính không quá 2 . Giải. Ta sẽ chứng minh rằng trong bốn điểm đã cho, tồn tại hai điểm có khoảng cách lớn hơn 2 . Xét ba trường hợp : a) Bốn điểm A, B, C, D là đỉnh của một tứ giác lồi. Tồn tại một góc lớn hơn hoặc bằng 900 , chẳng hạn A . Ta sẽ chứng minh BC  2 . Thật vậy, do A  900 nên BC 2  AB2  AC 2  1  1  2 . Vậy BC  2 . b) Ba điểm (chẳng hạn A, B, C) là đỉnh của một tam giác, điểm thứ tư D nằm trong hoặc trên biên.  Nếu D nằm trên biên của tam giác, chẳng hạn D nằm giữa A và C thì AD > 1, DC > 1 nên AC > 2 > 2. 9
 Nếu D nằm trong  ABC thì trong ba góc ADB, BDC, CDA , tồn tại một góc lớn hơn hoặc bằng 1200 , giả sử CDA  1200 . Dễ thấy AC  2 . c) Bốn điểm A, B, C, D thẳng hàng. Bài toán hiển nhiên đúng.  Bài toán 6. Cho một đa giác đơn (không nhất thiết lồi) có chu vi 12. Chứng minh rằng có thể phủ kín đa giác bởi một hình tròn có bán kính 3. Giải. Gọi A, B là hai điểm thuộc biên của đa giác chia chu vi của đa giác thành hai phần bằng nhau, mỗi phần có độ dài 6. Ta có AB < 6. Gọi O là trung điểm của AB. Vẽ hình tròn (O ; 3), ta sẽ chứng minh rằng hình tròn này phủ kín đa giác. Chứng minh bằng phản chứng. Giả sử tồn tại điểm C thuộc biên của đa giác mà nằm ngoài đường tròn thì OC > 3. Điểm C chia biên của đường gấp khúc từ A đến B thành hai phần có độ dài m, n. Thế thì AC  m, CB  n nên AC + CB  m + n = 6 (1) Mặt khác, lấy C' đối xứng với C qua O, ta có : AC + CB = AC + AC'  CC' > 6 (2) Dễ thấy (1) và (2) mâu thuẫn. Vậy mọi điểm của đa giác đều thuộc hình tròn (O ; 3).  10
Bài toán 7. Cho một đa giác lồi. Xếp được nhiều nhất 10 đồng xu hình tròn có đường kính 1, đôi một không giao nhau và có tâm nằm trong đa giác. Chứng minh rằng 10 hình tròn có bán kính 1 đồng tâm với 10 đồng xu sẽ phủ kín đa giác. Giải. Giả sử 10 hình tròn lớn (bán kính 1) không phủ kín đa giác (h. 200) thế thì tồn tại một điểm A nằm ngoài các hình tròn lớn và nằm trong đa giác. Như vậy còn đặt được thêm một đồng xu có đường kính 1 có tâm A mà không cắt các đồng xu trước, tức là số đồng xu có đường kính 1 không cắt nhau và có tâm nằm trong đa giác lớn hơn 10, trái với giải thiết. Vậy bài toán được chứng minh. Bài toán 8. Cho một đa giác lồi. Xếp được nhiều nhất 20 hình tròn có bán kính 1, đôi một không giao nhau và có tâm nằm trong đa giác, xếp được ít nhất n hình tròn có bán kính 2 phủ kín đa giác. Chứng minh rằng n  20. Giải. Vẽ 20 hình tròn có bán kính 2 đồng tâm với 20 hình tròn có bán kính 1 đã xếp. 20 hình tròn lớn này phủ kín đa giác (chứng minh tương tự bài toán 8). Điều đó chứng tỏ n  20.  Bài toán 9. Bên trong một hình chữ nhật có diện tích 35, đặt năm tam giác, mỗi tam giác có diện tích 9. Chứng minh rằng tồn tại hai tam giác có diện tích phần chung không nhỏ hơn 1. Giải. Gọi các tam giác là D1 , D2 ,..., D5 . Giả sử diện tích phần chung của hai tam giác nào cũng nhỏ hơn 1. D1 có diện tích bằng 9. 11
Phần diện tích của D2 không bị phủ bởi D1 lớn hơn 9  1 = 8. Phần diện tích của D3 không bị phủ bởi D1 , D2 lớn hơn 9  1  1 = 7. Phần diện tích của D4 không bị phủ bởi D1 , D2 , D3 lớn hơn 9  1  1  1 = 6. Phần diện tích của D5 không bị phủ bởi D1 , D2 , D3 , D4 lớn hơn 9  1  1  1  1 = 5. Diện tích của hợp D1 , D2 , D3 , D4 , D5 lớn hơn 9 + 8 + 7 + 6 + 5 = 35. Điều này vô lí. Vậy bài toán được chứng minh.  Bài toán 10. Trong mặt phẳng cho một số hữu hạn điểm không cùng nằm trên một đường thẳng. Chứng minh rằng tồn tại một đường tròn đi qua ba điểm trong chúng và nó phủ tất cả các điểm còn lại. Giải. Trước tiên ta có chú ý sau : Cho đoạn thẳng AB và hai điểm M và N không thuộc đoạn thẳng trên. Ta xét trường hợp khi nào thì bán kính r của đường tròn ngoại tiếp tam giác ABN lớn hơn bán kính k của đường tròn ngoại tiếp tam giác ABM. a) Cho ANB và AMB là những góc nhọn. Khi đó dễ thấy rằng r > k chỉ khi ANB < AMB . Điều này vẫn đúng khi cả hai góc không là tù. 12
b) Nếu một trong các góc là tù, giả sử là ANB , còn góc kia không tù, thì ta sẽ có r > k khi và chỉ khi ANB > 1800 - AMB . c) Nếu cả hai góc đều là tù, thì r > k khi ANB > AMB . Quay trở lại bài toán. Ta dựng bao lồi P của tập điểm đã cho. Vì các điểm không cùng nằm trên một đường thẳng nên bao lồi của chúng không phải là một đoạn thẳng. Ta xét tất cả các tam giác có những đỉnh giữa các đỉnh của P và chọn tam giác có bán kính đường tròn ngoại tiếp lớn nhất. Ta cho đó là tam giác ABC. Giả sử tồn tại đỉnh N của P nằm α ngoài đường tròn ngoại tiếp tam giác N M ABM. Khi đó N nằm ngoài ABM. Suy ra tồn tại ít nhất 1 đỉnh của tam giác ABM, giả sử là B sao cho N và B A nằm ở hai nửa mặt phẳng khác nhau B α α đối với cạnh AM của nó. Cần chú ý là vì tính lồi của P nên không một đỉnh nào có thể nằm ở các vùng  . Hơn nữa một trong những góc BAM và BMA là góc tù. Ta cho đó là BAM . Khi đó MNB  BAM , điều này có nghĩa là bán kính đường tròn ngoại tiếp tam giác MNB lớn hơn bán kính đường tròn ngoại tiếp BAM, điều này trái với cách chọn tam giác ABM. Vậy không tồn tại đỉnh N nằm ngoài đường tròn ngoại tiếp tam giác ABM.  13
Bài toán 11. Chứng minh rằng mỗi đa giác lồi có diện tích bằng 1 có thể phủ bằng một hình bình hành có diện tích bằng 2. Giải. Ta kí hiệu C là đỉnh xa nhất đối với một cạnh của đa giác M. Đường thẳng AC chia M thành hai phần (hoặc chỉ một phần) M1 và M2. Cho D1 là đỉnh của M1 và D2 là đỉnh của M2 sao cho D1 và D2 là những đỉnh xa nhất đối với AC. S C R D1 D2 P B Q A Qua C, D1, D2 lần lượt dựng các đường thẳng song song với AB, AC, AC. Ta có được hình bình hành PQRS. 1 1 Ta có S ACD  S ACSP , S ACD  S AQRC . 1 2 2 2 1 Do đó S AD CD  S PQRS . 1 2 2 Dễ thấy đa giác M có diện tích lớn hơn diện tích đa giác AD1CD2, mặt khác nếu diện tích đa giác AD1CD2 là 1 thì diện tích đa giác PQRS là 2. Vậy kết luận một đa giác có diện tích 1 có thể được phủ bởi một hình bình hành có diện tích 2.  14
Bài toán 12. Trong không gian cho một số hữu hạn các điểm, mà không có bốn điểm nào trong chúng cùng nằm trên một mặt phẳng sao cho thể tích mỗi tứ diện tạo ra bởi đỉnh là những điểm này không lớn hơn 1. Chứng minh rằng tất cả các điểm có thể phủ bởi một tứ diện có thể tích bằng 27. Giải. Giả sử trong tất cả các tứ diện được tạo bởi các điểm đó, tứ diện ABCD là tứ diện có thể tích lớn nhất. Qua các đỉnh A, B, C, D dựng các mặt phẳng song song với các mặt đối diện của đỉnh đó. Lúc đó ta có tứ diện A1B1C1D1. D1 M A B C C1 B1 D A1 Khi đó những điểm A, B, C, D là trọng tâm tương ứng của các tam giác 1 1D1 , B1 A1D1 , B1C1 A1 . B1C1D1, AC 15
Thật vậy, kéo dài B1C cắt A1D1 tại K, kéo dài B1A cắt C1D1 tại S, kéo dài B1D cắt C1A1 tại R như hình vẽ dưới đây ta thấy : CD // KR, CD // C1D1 suy ra KR // SD1 AD // SR, AD // A1D1 suy ra SR // KD1 Do đó SRKD1 là hình bình hành, suy ra SR = KD1. Chứng minh tương tự ta có SRKA1 là hình bình hành và SR = KA1. Như vậy K là trung điểm của A1D1. Tương tự S, R là trung điểm của C1D1 và C1A1. Do đó có thể kết luận những điểm A, B, C, D là trọng tâm tương ứng của các tam giác B1C1D1, AC 1 1D1 , B1 A1D1 , B1C1 A1 . Theo cách này ta nhận được quan hệ tỉ lệ 1 DC AB AC AD CB DB       . 3 D 1C1 A 1B1 A 1C1 A 1D1 C 1B1 D 1B1 Từ đây suy ra tỉ số thể tích giữa hai đa diện là 16
Ta sẽ chứng minh tứ diện A1B1C1D1 phủ tất cả các điểm đã cho. Giả sử tồn tại điểm M trong các D1 điểm đã cho nằm ngoài tứ diện M A1B1C1D1. Khi đó tồn tại ít nhất một A đỉnh của đa diện, cho nó là B1 và điểm M nằm trong hai nửa không gian giác B C C1 B1 nhau như ở hình vẽ trên. Lúc đó D VMACD  VABCD . A1 Điều này trái với việc chọn ABCD là tứ diện có thể tích lớn nhất. Vậy tứ diện A1B1C1D1 phủ tất cả các điểm của tập hợp đã cho. Và VA1B1C1D1  27VABCD  27 . Vậy bài toán được chứng minh.  Bài toán 13. Chứng minh rằng không tồn tại phủ mặt phẳng bằng những tam giác mà mỗi đỉnh của tam giác là đỉnh của 5 tam giác. Giải. Giả sử tồn tại một phủ mặt phẳng bằng những tam giác mà mỗi đỉnh của nó là đỉnh của 5 tam giác. Cho  là một trong những tam giác đó. Những tam giác có chung đỉnh với  sẽ tạo ra một lục giác B1A1 B2A2 B3A3 như hình vẽ dưới đây. 17
C3 B3 A2 A3 B2 B1 A1 C2 C1 Như vậy những điểm Ak, k = 1, 2, 3 là những đỉnh của hai tam giác nằm trong lục giác, còn Bk, k = 1, 2, 3 là những đỉnh của ba tam giác nằm trong lục giác. Do đó những điểm Ak, k = 1, 2, 3 còn là những đỉnh của ba tam giác nằm ngoài lục giác, còn Bk, k = 1, 2, 3 còn là những đỉnh của hai tam giác nằm ngoài lục giác. Như vậy ta nhận được tam giác C1C2C3. Mỗi đỉnh của tam giác này là đỉnh của 4 tam giác nằm trong C1C2C3. Tổng của bốn góc mà chúng có đỉnh là một trong các điểm C1, C2, C3 là nhỏ hơn 1800, dễ thấy các điểm đó không thể tiếp tục là đỉnh của 5 tam giác nữa (xem hình vẽ). Vậy không thể phủ mặt phẳng bằng những tam giác mà mỗi tam giác là đỉnh của 5 tam giác.  18
CHƢƠNG 2. BÀI TOÁN ĐỒ THỊ, TÔ MÀU 2.1. Lý thuyết cơ bản về bài toán tô màu Khi gặp những bài toán có nội dung phức tạp, một công việc mà ta cần làm là đưa nó trở về ngôn ngữ toán học quen thuộc. Điều đó giúp chúng ta dễ dàng tư duy và việc trình bày lời giải cũng trở nên đơn giản hơn. Một trong các phương pháp hữu hiệu là phương pháp tô màu. Ta chia các đối tượng đang xét thành nhiều nhóm đối tượng nhỏ hơn và tô mỗi nhóm bởi các màu khác nhau. Kết hợp với các kiến thức hình học và một số phương pháp khác để giải bài toán. Một số nguyên lý thường dùng cùng với phương pháp này như nguyên lý cực hạn, nguyên lý Dirichlet, một số tính chất về các số Ramsey… Dưới đây tôi trình bày vắn tắt các nội dung này. Nguyên lý cực hạn. Trong một tập hợp hữu hạn khác rỗng các số thực luôn tồn tại số nhỏ nhất và số lớn nhất. Nguyên lý Dirichlet. Nếu nhốt n con thỏ vào k cái lồng, thì tồn tại ít nhất n một chuồng có    1 con thỏ. k  Định lý 1. Cho k, l là hai số nguyên dương, khi đó tồn tại số nguyên dương nhỏ nhất R(k;l), sao cho khi ta tô màu tất cả các cạnh của một đồ thị đầy đủ có R(k;l) đỉnh bởi hai màu xanh và đỏ thì luôn tồn tại đồ thị con Kk có tất cả các cạnh màu đỏ hoặc đồ thị con Kl có tất cả các cạnh màu xanh. Trên cơ sở định lý này ta chứng minh được một số kết quả quen thuộc. R(3;3) = 6; R(3;4) = R(4;3) = 9. R(4;4) = 18. R(k,2) = k; R(2;l) = l. Các kết quả này được áp dụng nhiều trong các bài toán ở phần sau. 19
2.2. Phƣơng pháp tô màu giải bài toán hình học 2.2.1. Một số bài toán tô màu đồ thị Ở phần này chúng ta xem xét một số bài toán hình học sử dụng phương pháp tô màu đồ thị. Các bài toán đưa ra từ mức đơn giản đến phức tạp. Trước hết ta xem xét một số bài toán tô bởi hai màu. Những bài toán này được tham khảo trong các tài liệu [1], [2], [6] và [7] ở mục tài liệu tham khảo. Bài toán 14. Cho sáu điểm trong mặt phẳng trong đó không có ba điểm nào thẳng hàng. Các đoạn thẳng nối hai trong sáu điểm đó với nhau được tô bởi màu xanh hoặc đỏ. Chứng minh luôn tồn tại một tam giác có ba cạnh cùng màu. Giải. Gọi sáu điểm đã cho là A, B, C, D, E, F. Điểm A được nối với năm điểm còn lại bởi năm đoạn thẳng. Năm đoạn thẳng này được tô bởi hai màu. Nên có ba đoạn thẳng được tô bởi một màu. Không giảm tính tổng quát ta giả sử ba đoạn thẳng đó là AB, AC, AD và được tô bởi màu đỏ. Xét tam giác BCD. Có hai trường hợp xảy ra B + Nếu cả ba cạnh của tam giác BCD C được tô bởi màu xanh ta có điều phải chứng minh. + Nếu có một cạnh của tam giác BCD A D B được tô bởi màu đỏ, thì cạnh đó cùng hai C trong ba cạnh AB, AC, AD tạo thành tam giác có màu đỏ.  A D 20