Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 40
(Sở Sóc Trăng 2025) Cho bảy điểm $ A,\,\,B,\,\,C,\,\,D,\,\,E,\,\,F,\,\,G $ có $ ABCD $ là hình chữ nhật, $ F $ là trung điểm $ AD $, độ dài các
cạnh được ghi như hình vẽ (đơn vị độ dài).
Một trò chơi được quy định như sau: xuất phát từ một điểm bất kỳ trong bảy điểm trên đi qua hết tất cả các cạnh trên hình vẽ mỗi cạnh ít nhất một lần rồi quay lại điểm xuất phát. Người chơi là người thắng cuộc nếu tổng độ dài đường đi là ngắn nhất. Tính tổng độ dài đường đi đó.
Xem lời giải
Lời giải
Đáp án: 106
Nhận thấy hình trên là một đa đồ thị, trong đó có đỉnh A và D có bậc lẻ, các đỉnh còn lại có bậc chẵn. Để đường đi qua tất cả các cạnh và quay về điểm xuất phát là ngắn nhất thì đường đi đó phải đi qua các cạnh một lần và nếu có lặp lại trên một số cạnh thì cũng lặp lại ít nhất và có tổng trọng số bé nhất.
Do đỉnh A và D có bậc lẻ nên theo định lý Euler ta sẽ có một đường đi Euler từ A đến D mà đi qua tất cả các cạnh chỉ duy nhất một lần, ta có thể chỉ ra con đường đó là AEDCBAFBGCFD. Các đỉnh còn lại sẽ không có con đường này.
Cho nên nếu xuất phát từ A hoặc D đi theo con đường Euler ở trên thì khi muốn quay lại điểm xuất phát chỉ đi thêm đoạn AD với trọng số là 12, đây là con đường ngắn nhất.
Độ dài con đường đó là: 8+10 + 8+8+12+12+8+8+10+10+12 = 106
