Luận văn Sáu phương pháp giải các bài toán phổ thông

và những người quan tâm đến logic toán. Nó là bước tiếp 28 Chương 3. Phương pháp suy luận trực tiếp cận đầu tiên đến logic toán học. Nó rèn luyện tư duy logic, khả năng phản xạ, trí thông minh, là hình thức thể thao trí tuệ phục vụ cho đông đảo người đọc đặc biệt là lứa tuổi học sinh ở nhiều cấp học khác nhau. Điều cơ bản của phương pháp này là thông qua việc phân tích các điều kiện của bài toán, cần tìm ra mối quan hệ logic giữa các mệnh đề. 3.2 Các ví dụ về vận dụng phương pháp suy luận trực tiếp Ví dụ 3.2.1. Có ba em chơi trò đội mũ. Em chủ trì giơ ba mũ đỏ, hai mũ xanh, rồi yêu cầu ba em ngồi theo hàng dọc và không nhìn về phía sau, rồi từ phía sau chụp lên đầu mỗi em một cái mũ còn hai cái cất đi. Chứng minh rằng trong mọi cách đội đều có một em nhận ra màu mũ của mình. Lời giải: Giả sử em A ngồi sau em B, em B ngồi sau em C, rõ ràng em A quan sát được mũ của em B và C còn em B quan sát được mũ của em C. - Trước hết do chỉ có hai mũ xanh nên nếu B và C đội mũ xanh thì A đoán được ngay mũ của mình là mũ đỏ. - Nếu A im lặng, chứng tỏ trong B và C có một em đội mũ xanh, một em đội mũ đỏ hoặc cả hai em đội mũ đỏ. Khi đó B sẽ phải suy nghĩ và quan sát C. Nếu C đội mũ xanh thì B đoán ngay mình đội mũ đỏ. Nếu B thấy C đội mũ đỏ thì B đành im lặng và C sẽ nhận biết ngay mình đội mũ đỏ. Lời giải của bài toán trên có thể tóm tắt theo sơ đồ sau A Đ im B X C X XĐ Hình 3.1 Như vậy, trong mọi trường hợp, đều có ít nhất một em đội mũ đỏ. Dấu hiệu để các em dự đoán được mũ của mình là số mũ xanh mà mình hoặc bạn mình quan sát được. Em đoán đúng màu mũ của mình sẽ luôn là em đội mũ đỏ.  29 Chương 3. Phương pháp suy luận trực tiếp Ví dụ 3.2.2. (Vị sứ giả thông minh) Một viên quan nước Lỗ đi sang xứ Tề, bị vua Tề tuyên phạt tử hình và bị hành quyết hoặc chém đầu hoặc treo cổ. Trước khi hành quyết nhà vua cho sứ giả được nói một câu, nếu nói đúng thì bị chém đầu, nếu nói sai thì bị treo cổ. Sứ giả mỉm cười nói một câu, nhờ đó đã thoát chết. Bạn hãy cho biết câu nói của sứ giả đó như thế nào? Lời giải: Vị sứ giả đã nói rằng "Tôi sẽ bị treo cổ". Như vậy, nếu nhà vua đem treo cổ sứ giả thì sứ giả đó nói đúng. Mà theo điều lệnh sử phạt của nhà vua thì phải đưa sứ giả đi chém đầu (vì ông ta nói đúng). Nếu nhà vua chém đầu thì ông ta đã nói sai. Theo điều lệnh sử phạt của nhà vua thì phải đem sứ giả đi treo cổ. Thành thử nhà vua không thể hành quyết sứ giả bằng chém đầu cũng như treo cổ, nên sứ giả đã thoát chết. Ví dụ 3.2.3. Người bản sứ và tên thực dân Trước vành móng ngựa là ba người đàn ông, họ là người bản sứ hoặc tên thực dân. Quan tòa biết khi được hỏi người bản sứ bao giờ cũng nói thật, còn tên thực dân bao giờ cũng nói dối, nhưng quan tòa không biết ai là người bản sứ, ai là tên thực dân. Quan tòa hỏi người thứ nhất: "Anh là ai?". Nhưng anh ta nói ngọng nên quan tòa không hiểu câu trả lời. Hãy xác định câu trả lời của người thứ nhất? Lời giải: Nếu người được hỏi thứ nhất là tên thực dân thì theo bản chất của thực dân, anh ta sẽ trả lời "Tôi là người bản sứ". Nếu người đó là dân bản sứ thì theo bản chất của người dân bản sứ anh ta cũng trả lời "Tôi là người bản sứ". Như vậy câu trả lời của người thứ nhất chỉ có thể là: "Tôi là người bản sứ". Ví dụ 3.2.4. a. Trong một căn phòng có 10 người, biết rằng giữa ba người bất kỳ có hai người quen nhau. Chứng minh rằng, có thể tìm được bốn người mà hai người bất kỳ trong số đó đều quen nhau. b. Khẳng định trên có còn đúng nữa không nếu ở câu a số người trong phòng là 9. Lời giải: a. Giả sử bốn người bất kỳ có hai người không quen nhau. Khi đó A không thể có quá ba người không quen. Nếu A có bốn người không quen thì theo giả thiết giữa bốn người này có hai người không quen và họ cùng với 30 Chương 3. Phương pháp suy luận trực tiếp A hợp thành bộ ba đôi một không quen nhau. Vậy A có không nhiều hơn ba người không quen, nghĩa là A có không ít hơn sáu người quen. Giả sử A quen với B1, B2, · · · , B6. Khi đó giữa B1, B2, · · · , B6 không có bộ ba nào đôi một quen nhau (Nếu khác thì bộ ba này hợp thành với A thành bộ bốn đôi một quen nhau- trái với giả thiết). Hơn nữa có bộ ba mà hai người không quen nhau trong số sáu người B1, B2, · · · , B6. Chẳng hạn, nếu B1 không quen với B2, B3, B4 thì B2, B3, B4 đôi một quen nhau. Vì thế B1 phải có ít nhất ba người quen trong số B2, B3, · · · , B6. Khi đó trong số ba người này không tìm được hai người quen nhau, ngược lại họ tạo với A và B1 thành bộ bốn người đôi một quen nhau. Trái với giả thiết, suy ra tồn tại bộ bốn mà hai người bất kỳ quen nhau. b. Ta chứng minh cho khẳng định trên vẫn đúng. Nếu người nào đó quen với tất cả sáu người thì chứng minh sẽ tương tự phần a. Nếu mỗi người quen có đúng năm người thì tổng số các cặp quen nhau sẽ là 9.5/2 không là số nguyên- điều này không thể xảy ra. Cuối cùng nếu tìm được một người nào đó không quen với ít nhất bốn người thì bốn người này phải đôi một quen nhau (nếu khác ta sẽ tìm được bộ ba đôi một không quen nhau) có nghĩa là tạo thành bộ bốn cần tìm- đó là điều phải chứng minh.  Ví dụ 3.2.5. Mỗi bạn đạt giải mấy trong kỳ thi vô địch toàn quốc? Ba bạn Quân, Hùng, Mạnh vừa đạt giải nhất, nhì, ba trong kì thi học sinh giỏi toàn quốc. Biết rằng: 1. Không có học sinh trường chuyên nào đạt giải cao hơn Quân. 2. Nếu Quân đạt giải thấp hơn một bạn nào đó thì Quân không phải là học sinh trường chuyên. 3. Chỉ có duy nhất một bạn không học trường chuyên. 4. Nếu Hùng hoặc Mạnh đạt giải nhì, thì Mạnh đạt giải cao hơn bạn quê ở Hải Phòng. Hãy cho biết: Mỗi bạn đã đạt được giải nào? Bạn nào không học trường chuyên và bạn nào quê ở Hải Phòng? Lời giải: Ta nhận xét rằng: Nếu Quân đạt giải nhì hoặc ba, thì theo (2) Quân không học trường chuyên. Ta suy ra, theo (3) Hùng và Mạnh học trường chuyên, thành thử theo (1) Quân đạt giải nhất. Điều này vô lý. Vậy Quân phải đạt giải nhất. Trong hai bạn Hùng và Mạnh một người đạt giải nhì và một người đạt giải ba. Mạnh không thể đạt giải ba (vì theo (4) Mạnh còn đạt giải cao hơn bạn quê ở Hải Phòng). 31 Chương 3. Phương pháp suy luận trực tiếp Vậy Mạnh phải đạt giải nhì, Hùng đạt giải ba. Đồng thời ta cũng suy ra Quân không học trường chuyên và Hùng quê ở Hải Phòng. Ví dụ 3.2.6. Ai đã nói đùa? Nhà trường cử thầy Nghiêm dẫn bốn học sinh Lê, Huy, Hoàng, Tiến đi thi đấu điền kinh. Kết quả ba em đạt giải nhất, nhì, ba và một em không đạt giải. Khi về trường mọi người hỏi kết quả các em trả lời như sau: Lê: Mình đạt giải nhì hoặc ba. Huy: Mình đã đạt giải. Hoàng: Mình được giải nhất. Tiến: Mình không được giải. Nghe xong thầy Nghiêm mỉm cười và nói: "Chỉ có ba bạn nói thật còn một bạn đã nói đùa " Hãy cho biết học sinh nào đã nói đùa và ai đạt giải nhất, ai không đạt giải? Lời giải: 1) Nếu Lê nói đùa thì ba bạn Huy, Hoàng, Tiến nói thật. Như vậy Lê và Hoàng cùng đạt giải nhất. Điều này vô lý. Vậy Lê phải nói thật. 2) Nếu Huy nói đùa thì Huy không được giải và cả ba bạn còn lại đều nói thật. Như vậy cả Huy, Tiến đều không đạt giải. Điều này trái với giả thiết của đầu bài. Vậy Huy phải nói thật. 3) Nếu Tiến nói đùa thì Tiến đạt giải và cả ba bạn còn lại đều đạt giải. Như vậy cả bốn bạn đều đạt giải. Điều này trái với giả thiết. Như vậy Tiến nói thật. Vậy Hoàng đã nói đùa. Có nghĩa là Hoàng đã đạt giải nhì hoặc ba cho nên Huy đạt giải nhất. Còn Tiến không đạt giải. Kết luận: Huy đạt giải nhất, Tiến không đạt giải và Hoàng nói đùa. Ví dụ 3.2.7. Điều mâu thuẫn ở đâu? Trong một tòa nhà chỉ có những cặp vợ chồng và những con nhỏ chưa lập gia đình. Ban điều tra dân số yêu cầu báo cáo về số người sống trong tòa nhà, đại diện là một anh thợ thích đùa báo cáo như sau: Sống trong tòa nhà bố mẹ nhiều hơn con cái. Mỗi con trai đều có một chị hay em gái. Số con trai nhiều hơn số con gái. Mỗi cặp vợ chồng đều có con. Người ta không thể chấp nhận được báo cáo đó (dù là đùa vui) vì trong đó có mâu thuẫn. Hãy chỉ ra điều mâu thuẫn trong báo cáo trên? Lời giải: Vì mỗi gia đình đều có con, mỗi con trai đều có một chị gái hay em gái, nên tất cả các gia đình đều có con gái. Suy ra số con gái ít nhất bằng số gia đình. 32 Chương 3. Phương pháp suy luận trực tiếp Mặt khác, số con trai nhiều hơn số con gái, nên tổng số con nhiều hơn hai lần số gia đình, hay nhiều hơn số bố mẹ, điều này cho ta thấy mâu thuẫn trong báo cáo của anh thợ thích đùa ở câu đầu tiên "bố mẹ nhiều hơn con cái" với các câu tiếp theo. Ví dụ 3.2.8. Khi tổ chức múa hát tập thể một giáo viên đã xếp 20 nữ sinh và một số nam sinh thành vòng tròn sao cho đối diện với một nữ sinh qua tâm vòng tròn là một nam sinh. Hỏi trên vòng tròn này có hai nam sinh nào đứng kề nhau hay không? Lời giải: Giả sử không có hai nam sinh nào đứng kề nhau, vì vậy cũng không có hai nữ sinh nào đứng kề nhau. Do đó các bạn nam sinh và nữ sinh được xếp xen kẽ nhau trên vòng tròn, suy ra có tất cả là 20 nam sinh. Lấy hai bạn nam và nữ đứng ở vị trí đối xứng nhau qua tâm vòng tròn. Bắt đầu từ nữ sinh này ta đánh số các bạn đứng trên một nửa vòng tròn cho đến nam sinh đối diện. Rõ ràng bạn nữ này được đánh số 1 và bạn nam đối diện đánh số 21. Khi đó các bạn nữ lần lượt được đánh số 1, 3, 5, · · · , 19, còn các bạn nam được đánh số 2, 4, 6, · · · , 20. Do đó có hai bạn nam sinh được đánh số 20 và 21 đứng kề nhau. Điều này mâu thuẫn với giả thiết ban đầu. Vậy phải luôn luôn có hai nam sinh đứng kề nhau. Ví dụ 3.2.9. Trong tám viên bi có bề ngoài hoàn toàn giống nhau có một viên bi nặng hơn. Bằng hai lần cân trên đĩa (không được dùng quả cân). Hãy xác định viên bi nặng đó? Lời giải: Đầu tiên chia tám viên bi thành ba đống theo số lượng 3, 3, 2. Trong lần cân thứ nhất ta bỏ mỗi bên đĩa cân một đống gồm ba viên bi. Có hai khả năng xảy ra: a) Nếu cân thăng bằng. Thì viên bi nặng nằm trong đống hai viên bi. Khi đó, ta tiến hành cân hai viên bi ở đống gồm hai viên. Mỗi bên đĩa bỏ một viên bi ở đống hai viên bi. Viên bên chìm chính là viên bi nặng hơn. b) Nếu cân không thăng bằng, thì bên chìm chứa viên bi nặng hơn. Khi đó ta tiến hành cân lần thứ hai. Bỏ mỗi đĩa một viên bi trong ba viên bên chìm. Nếu cân thăng bằng, thì viên bi nặng hơn chính là viên bi còn lại nằm trên đĩa chìm. Nếu cân không thăng bằng, thì viên bi nặng hơn chính là viên bi bên chìm. Vậy chỉ bằng hai lần cân ta đã xác định được viên bi nặng hơn. 33 Chương 3. Phương pháp suy luận trực tiếp Ví dụ 3.2.10. Học sinh lớp 11 và 12 tổ chức thi đấu cờ với nhau. Số học sinh lớp 11 tham gia gấp 10 lần số học sinh lớp 12 tham gia thi đấu xong điểm học sinh lớp 11 gấp 4, 5 lần số điểm học sinh lớp 12. Hãy tính xem có bao nhiêu học sinh tham gia đấu cờ. (Nội quy thi đấu là mỗi người thi đấu một lần với tất cả những người còn lại, người thắng ghi 1 điểm người thua ghi 0 điểm). Biết rằng tất cả các trận đấu không có trận nào hòa. Lời giải: Gọi số học sinh lớp 12 tham gia đấu cờ là x. Khi đó số học sinh lớp 11 tham gia đấu cờ là 10x và có tất cả là 11x em tham gia đấu cờ. Số trận đấu có tất cả là 11x(11x−1)2 trận và cũng có chừng ấy điểm thắng. Số điểm thắng của học sinh lớp 11 đạt được là 4, 5 5, 5 × 11x (11x− 1) 2 = 4, 5x (11x− 1) Các em học sinh lớp 11 sẽ thi đấu với nhau 10x(10−1)2 trận và sẽ có số điểm là 5x (10x− 1) Hiển nhiên ta phải có 4, 5x(11x− 1) ≥ 5x(10x− 1) 99x2 − 9x ≥ 100x2 − 10x x ≥ x2. Điều này chỉ xảy ra khi x = 1. Vậy có 11 em tham gia đấu cờ. 34 Chương 4 Phương pháp đồ thị Rất nhiều bài toán có thể giải bằng cách đưa về bài toán trên đồ thị rồi suy ra đáp án. 4.1 Một số khái niệm và kết quả cơ bản của lí thuyết đồ thị Trên mặt phẳng hay trong không gian lấy n điểm. Giữa một số cặp điểm được nối bằng những đoạn thẳng hay đoạn cong được định hướng hoặc không. Người ta gọi hình nhận được là dạng biểu diễn hình học của đồ thị hay một đồ thị. Các điểm đã chọn được gọi là đỉnh của đồ thị. Các đoạn thẳng hay đoạn cong đã nối được gọi là cạnh của đồ thị. Nếu cạnh a nối giữa hai điểm A,B thì A,B được gọi là các đỉnh của cạnh a. Cặp đỉnh x, y được gọi là hai đỉnh kề nhau, nếu chúng khác nhau và là hai đầu của cùng một cạnh. Dãy α các đỉnh x1, x2, · · · , xi, xi+1, · · · , xm−1, xm được gọi là một đường, nếu với mọi chỉ số i(1 ≤ i ≤ m− 1) đều có xi và xi+1 là hai đỉnh kề nhau. Các đỉnh x1, xm được gọi là các đỉnh đầu của đường α. Người ta còn nói rằng đường α nối giữa đỉnh x1 và đỉnh xm. Chu trình là một đường có hai đầu trùng nhau. Chu trình mà nó đi qua mỗi đỉnh không quá một lần được gọi là chu trình sơ cấp. Chu trình (α) được gọi là chu trình Hamilton, nếu nó đi qua tất cả các đỉnh của đồ thị và qua mỗi đỉnh đúng một lần. 35 Chương 4. Phương pháp đồ thị Đồ thị G được gọi là đồ thị liên thông, nếu mỗi cặp đỉnh của nó đều có đường nối với nhau. Đồ thị G được gọi là đồ thị đầy đủ nếu mỗi cặp đỉnh của nó được nối với nhau bằng đúng một cạnh. Số cạnh xuất phát từ đỉnh x được gọi là bậc của đỉnh x. Cây là đồ thị liên thông và không có chu trình. Trong cây T tách ra một đỉnh được gọi là đỉnh gốc, còn các đỉnh có bậc bằng 1 và không phải gốc được gọi là lá hay đỉnh ngọn. Định lý 4.1.1. Đồ thị mà trong đó tổng bậc của hai đỉnh tùy ý đều không nhỏ hơn số đỉnh của đồ thị, liên thông. Định lý 4.1.2. Đồ thị mà trong đó bậc của mỗi đỉnh đều không nhỏ hơn 2, luôn luôn có chu trình sơ cấp. Hệ quả 4.1.1. Nếu trong đồ thị có đúng 2 đỉnh bậc 1, các đỉnh khác có bậc không nhỏ hơn 2, thì trong G có đường nối giữa hai đỉnh bậc 1. Định lý 4.1.3. Đồ thị, mà trong đó tổng bậc của hai đỉnh tùy ý không nhỏ hơn số đỉnh của đồ thị, luôn luôn có chu trình Hamilton. Định lý 4.1.4. Trong một đồ thị tùy ý số đỉnh, mà mỗi đỉnh có bậc lẻ, luôn luôn là một số chẵn. Định lý 4.1.5. Cho dãy số nguyên dương a1 = 2, a2 = 5, · · · , an+1 = (n+1)an+1. Khi đó đồ thị đầy đủ an+1 đỉnh với các cạnh được tô bằng n màu luôn luôn có tam giác cùng màu (chu trình gồm ba cạnh cùng màu). Định lý 4.1.6. Cho dãy số nguyên b2 = 3, b3 = 6, bn+1 = (bn−1)n+2. Đồ thị đầy đủ G với bn+1 − 1 đỉnh (n ≥ 2) và các cạnh được tô bằng n màu, sao cho không có tam giác cùng màu, thì trong đồ thị G có hình 5 cạnh với các cạnh cùng màu và các đường chéo được tô các màu khác. 4.2 Phương pháp đồ thị Để giải bài toán T bằng cách thông qua đồ thị, cần thực hiện lần lượt hai bước sau 36 Chương 4. Phương pháp đồ thị 4.2.1 Xây dựng đồ thị mô tả các quan hệ Lấy các điểm trên mặt phẳng hoặc trong không gian tương ứng với các đối tượng đã cho trong bài toán. Dùng ngay các kí hiệu đối tượng để ghi trên điểm tương ứng... Cặp điểm x, y được nối với nhau bằng một cạnh với "đặc điểm t", khi và chỉ khi các đối tượng x, y có quan hệ (t) với nhau. Khi đó bài toán T đã được chuyển về bài toán D trên đồ thị. 4.2.2 Dựa vào các kết quả của lý thuyết đồ thị hoặc lý luận trực tiếp suy ra đáp án của bài toán D Nếu đáp án của bài toán D còn dưới dạng "ngôn ngữ đồ thị", thì căn cứ vào phép đặt tương ứng khi xây dựng đồ thị mà diễn đạt thành đáp án bằng ngôn ngữ thông thường (tức là đáp án của bài toán T ). 4.3 Một số ví dụ Ví dụ 4.3.1. Trong một cuộc thi đấu bóng bàn An và Bình quy ước với nhau: Người thắng cuộc là người đầu tiên thắng ba ván hoặc thắng hai ván liên tiếp. Hãy xác định số khả năng có thể xảy ra? Lời giải: Dùng A để kí hiệu An thắng, B để kí hiệu Bình thắng. Dùng cây để mô tả toàn bộ hiện trạng có khả năng xảy ra. Xây dựng cây: Xuất phát từ điểm S. Ván đầu tiên có hai khả năng xảy ra: An thắng hoặc Bình thắng, nên lấy hai điểm sao cho hai điểm này với S không thẳng hàng. Một trong hai điểm này ghi A, còn điểm kia ghi B. Nối S với A bằng một đoạn thẳng hoặc một đoạn cong biểu thị A thắng. Tương tự, để biểu thị B thắng nối S với B bằng một đoạn thẳng hoặc một đoạn cong. Ván thứ hai lại có hai khả năng: An thắng hoặc Bình thắng, nên xuất phát từ A cũng lấy hai điểm mới và ghi các kí hiệu tương ứng A,B và từ A kẻ hai đoạn thẳng hoặc hai đoạn cong tới hai điểm mới thêm. Đối với điểm B cũng chọn thêm hai đỉnh mới ghi A và B, rồi từ B kẻ hai đoạn thẳng hay hai đoạn cong tới hai điểm mới thêm. Tiếp theo thực hiện kéo dài các đường một cách tương tự, nhưng do quy ước của An và Bình những đường mà trên đó xuất hiện hoặc hai đỉnh liên tiếp ghi 37 Chương 4. Phương pháp đồ thị cùng bằng một kí hiệu hoặc có ba đỉnh được ghi bằng cùng một kí hiệu đều không được kéo dài. S A B B B B B B BB B A A A A A AA A Hình 4.1 Vì An và Bình đấu với nhau năm ván, thì hoặc có người thắng hai ván liên tiếp hoặc có người thắng ba ván. Do đó những đường xuất phát từ S đều không có quá năm cạnh. (Hình 4.1) Cây có 10 đỉnh ngọn nên có 10 khả năng xảy ra. Ví dụ 4.3.2. Trên đảo có một số cụm dân cư. Mỗi cụm dân cư có hai đường lớn và ba đường mòn đi ra. Mỗi đường lớn cũng như đường mòn đều dẫn tới một cụm dân cư khác. Hai cụm dân cư khác nhau bất kì được nối liền bằng hoặc đường lớn hoặc đường mòn. Hỏi trên đảo này có bao nhiêu đường mòn, bao nhiêu đường lớn? Lời giải: Trước hết ta cần khẳng định rằng trên đảo có sáu cụm dân cư. Thật vậy, mỗi cụm dân cư ta biểu diễn bằng một điểm. Hai cụm dân cư có đường lớn (đường mòn) nối với nhau, thì hai cụm tương ứng được nối bằng một đường nét liền (đường nét đứt). Vì xuất phát từ mỗi cụm dân cư có hai đường 38 Chương 4. Phương pháp đồ thị lớn và ba đường mòn đi ra, nên xuất phát từ mỗi điểm đã chọn, chẳng hạn A, có hai đường nét liền và ba đường nét đứt. Bởi vậy mỗi điểm đã chọn A được nối với các điểm khác B,C,D,E, F bằng một đường nét liền hoặc một đường nét đứt. Như vậy phải có ít nhất sáu cụm dân cư (6 điểm đã chọn). Mặt khác hai cụm dân cư tùy ý đều phải có đường nối với nhau, nên mỗi điểm đều chỉ có thể nối tới với năm điểm. Do đó không còn điểm nào ngoài sáu điểm A,B,C,D,E, F . Bởi vậy, có sáu đường lớn và chín đường nhỏ. Căn cứ vào yêu cầu của bài toán ta có thể đưa ra một vài khả năng xảy ra các đường nối giữa các cụm dân cư như hình 4.2. B C D E F A A B C D E F Hình 4.2 Ví dụ 4.3.3. Tại một giải bóng đá có bốn đội Anh, Đan Mạch, Hà Lan, Thụy Điển vào bán kết. Có mấy dự đoán xếp hạng như sau 1. Đan Mạch vô địch, Thụy Điển nhì. 2. Đan Mạch nhì, Hà Lan ba. 3. Anh nhì, Hà Lan tư. Kết quả là mỗi dự đoán đúng được một đội. Hãy cho biết kết quả xếp hạng của các đội? Lời giải: Dùng xi để kí hiệu đội x được xếp hạng i(1 ≤ i ≤ 4). Ta vẽ cây, hai nhánh đầu tiên ứng với dự đoán thứ nhất là D1, T2. Từ mỗi nhánh này ta lại có hai nhánh tương ứng với dự đoán thứ hai. Tiếp tục rẽ nhánh với dự đoán thứ ba. Ta chọn đường đi từ gốc 0 tới các điểm thỏa mãn các điều kiện: • Một đội không thể được xếp hai hạng khác nhau. • Hai đội không thể xếp cùng một hạng. 39 Chương 4. Phương pháp đồ thị Suy ra chỉ có đường đi D1H3A2 thỏa mãn. O D1 D2 A2 A2 A2 A2H4 H4 H4 H4 H3H3 D2 T2 Hình 4.3 Đường tô đậm D1H3A2 thỏa mãn điều kiện mỗi dự đoán đúng được một đội mà thứ tự ghi trên đường. Vậy kết quả xếp hạng như sau: Đan Mạch vô địch. Anh nhì. Hà Lan ba. Còn lại là Thụy Điển thứ tư. Ví dụ 4.3.4. Cho 6 số nguyên dương tùy ý. Chứng minh rằng luôn có thể chọn ra được 2 bộ 3 số mà trong mỗi bộ, từng đôi một đều là nguyên tố cùng nhau hoặc đều không nguyên tố cùng nhau. Lời giải: Bước 1: Chuyển bài toán sang bài toán về đồ thị màu G(X,E). - Đỉnh: Cho tương ứng mỗi số với một đỉnh X = {A,B,C,D,E, F} - Cạnh: Đoạn nối giữa hai đỉnh tương ứng với hai số • Nguyên tố cùng nhau được tô màu xanh (đường nét đứt). • Không nguyên tố cùng nhau được tô màu đỏ (đường nét liền). Khi đó, ta được bài toán đồ thị màu: Trong đồ thị đầy đủ G(X, E) có 6 đỉnh với hai cạnh màu, thì luôn luôn có thể tìm được hai tam giác với cạnh cùng màu. Giả sử đỉnh A là mút của AB,AC,AD cùng màu đỏ (đường nét liền) như hình vẽ dưới đây 40 Chương 4. Phương pháp đồ thị A B C D Hình 4.4 Ta xét tam giác được lập nên từ ba đỉnh đối của A là BCD. Trong tam giác BCD hai khả năng có thể xảy ra: 1) Có ít nhất một cạnh màu đỏ. Chẳng hạn cạnh BC màu đỏ, khi đó tam giác ABC có cạnh màu đỏ. (Hình 4.5a) 2) Tam giác BCD không có cạnh nào màu đỏ. Nghĩa là tam giác BCD có cạnh đều là màu xanh. (Hình 4.5b) A BC F E D A B D C Hình 4.5a Hình 4.5b Vậy với mọi trường hợp, trong đồ thị G đều có tam giác cùng màu (theo Định lý (4.1.5)) Giả sử rằng trong G có tam giác màu đỏ, chẳng hạn tam giác ABC màu đỏ. Ta chứng minh tiếp G còn có tam giác thứ hai nữa với các cạnh cùng màu. Nếu trong G, ta tạm thời không xét đến một đỉnh của tam giác ABC, chẳng hạn đỉnh A cùng tất cả các cạnh thuộc nó. Ta được đồ thị con đầy đủ G1 có 5 đỉnh. Nếu trong G1 có tam giác cùng màu, thì bài toán đã được giải xong. 41 Chương 4. Phương pháp đồ thị Ngược lại, trong G1 không có tam giác cùng màu, thì theo Định lý (4.1.6) với n = 2, ta có thể biểu diễn G1 thành một hình 5 cạnh với các cạnh màu đỏ và đường chéo màu xanh. Bây giờ, ta khôi phục lại đỉnh thứ 6 A và các cạnh màu thuộc nó. Xét hai cạnh AD và AF nếu chúng đều màu xanh thì ta có tam giác mới ADF có màu xanh. Nếu AD hoặc AF màu đỏ thì ta có tam giác màu đỏ nữa được hình thành là ABD hoặc ACF . Vậy ngoài tam giác ABC, ta có thêm một tam giác nữa có các cạnh cùng màu. Khẳng định đã được chứng minh. C F E D B C B D E F AHình 4.6 Bước 3: Thuyết minh lời giải Trong G luôn tồn tại hai tam giác với cạnh cùng màu. Nếu cả hai tam giác đều màu đỏ, thì ta có hai bộ ba số, mà trong mỗi bộ chúng đôi một nguyên tố cùng nhau. Nếu chỉ có một tam giác màu đỏ, thì ta được một bộ ba số đôi một nguyên tố cùng nhau, và một bộ ba số đôi một không nguyên tố cùng nhau. Nếu cả hai tam giác màu xanh, nghĩa là ta được hai bộ ba số, mà trong mỗi bộ, chúng đôi một không nguyên tố cùng nhau. Ví dụ 4.3.5. Để mừng con đạt giải trong kì thi toán quốc tế lần thứ 42, một gia đình dự định mời tiệc. Trong số khách mời: a) Người chồng muốn có ít nhất ba người từng đôi một quen nhau. 42 Chương 4. Phương pháp đồ thị b) Người vợ lại muốn có ít nhất bốn người từng đôi một chưa quen nhau. Hỏi họ phải mời ít nhất bao nhiêu bạn, để mong muốn của chồng của vợ được thỏa mãn? Lời giải: Bước 1: Xây dựng đồ thị G(X,E) mô tả quan hệ của các đối tượng. • Đỉnh: Mỗi khách cho tương ứng với một đỉnh. • Cạnh: Đoạn nối giữa hai đỉnh tương ứng với hai khách: – Quen nhau được tô màu xanh (nét liền). – Không quen nhau tô màu đỏ (nét đứt). Khi đó đồ thị G(X,E) mô tả quan hệ quen biết của các khách dự kiến mời. Theo cách xây dựng trên, để thực hiện yêu cầu của người chồng, thì trong số khách mời phải có 3 người quen nhau từng đôi một, nên đồ thị G(X,E) phải có ít nhất một tam giác màu xanh, còn để thỏa mãn yêu cầu của người vợ, thì trong số khách mời phải có ít nhất 4 người từng đôi một không quen biết nhau, nên trong G(X,E) phải có ít nhất một tứ giác mà các cạnh và các đường chéo của nó phải có màu đỏ. Do đó bài toán được dẫn về bài toán trên đồ thị: Tìm số đỉnh ít nhất để đồ thị đầy đủ G(X,E) với các cạnh màu xanh hoặc đỏ mà a) Hoặc có ba đỉnh được nối với nhau bởi cạnh màu xanh, b) Hoặc bốn đỉnh từng đôi một được nối với nhau bởi cạnh màu đỏ. Bước 2: Giải bài toán đồ thị G 1) Nếu G có 8 đỉnh thì có thể xảy ra trường hợp mà cả (a) lẫn (b) không thỏa mãn. Như cách tô màu G ở hình 4.7, thì không có tam giác nào xanh, hoặc tứ giác nào với cạnh và đường chéo cùng màu đỏ. 43 Chương 4. Phương pháp đồ thị x1 x2 x3 x4 x5 x6 x7 x8 Hình 4.7 2) Xét G(X,E) đầy đủ với 9 đỉnh, các cạnh được tô bằng hai màu xanh, đỏ. X = {x1, x2, . . . , x8, x9} Hai khả năng có thể xảy ra: 10) Có 4 cạnh màu xanh xuất phát từ một đỉnh. Chẳng hạn x1 có 4 cạnh x1x2, x1x3, x1x4, x1x5 màu xanh. Khi đó nếu trong các cạnh nối đôi một giữa 4 đỉnh x2, x3, x4, x5 có một cạnh xanh, giả sử cạnh x3x4 xanh, thì có tam giác x1x3x4 cạnh xanh hình 4.8 a được thỏa mãn, nếu không thì tứ giác x2x3x4x5 có cạnh và các đường chéo màu đỏ hình 4.8 b, (b) được thỏa mãn. 44 Chương 4. Phương pháp đồ thị x1 x2 x3 x4 x5 x1 x2 x3 x4 x5 Hình 4.8 a Hình 4.8 b 20) Có nhiều nhất là 3 cạnh màu xanh xuất phát từ mỗi đỉnh. Bởi vậy, phải có ít nhất một đỉnh, x1 chẳng hạn, là đầu mút của không quá 2 cạnh màu xanh (vì nếu mỗi đỉnh là đầu mút của đúng 3 cạnh màu xanh, thì số cạnh màu xanh là 3×92 /∈ N). Khi đó, tại x1 phải là đầu mút của ít nhất 6 cạnh đỏ. Giả sử 6 cạnh đỏ đó là x1x4, x1x5, x1x6, x1x7, x1x8, x1x9. Xét đồ thị con đầy đủ G1 có 6 đỉnh x4, x5, . . . , x9 với 2 màu cạnh. Theo định lý (4.1.5) với n = 2, trong G1 có tam giác cùng màu. Nếu là tam giác màu xanh, thì (a) được thỏa mãn, nếu là tam giác màu đỏ thì 3 đỉnh này cùng với đỉnh x1 tạo thành đồ thị con đầy đủ có 4 đỉnh với các cạnh đều màu đỏ, (b) được thỏa mãn. x1 x2 x3 x4 x5 x6 x7 x8x9 Hình 4.9 Bước 3: Chuyển về ngôn ngữ xuất phát. 45 Chương 4. Phương pháp đồ thị Đồ thị đầy đủ với 9 đỉnh, các cạnh được tô bằng hai màu xanh, đỏ thì luôn có hoặc tam giác xanh hoặc tứ giác mà các cạnh và đường chéo đều màu đỏ, nhưng với 8 đỉnh thì tính chất trên không tồn tại. Vậy số đỉnh của đồ thị G phải ít nhất bằng 9, nên số khách ít nhất họ phải mời là 9, thì mong muốn của vợ hoặc chồng được thỏa mãn. Ví dụ 4