(Chuyên Phan Bội Châu - Nghệ An 2025) Trong một bệnh viện thông minh, hệ thống robot kỹ thuật có nhiệm vụ kiểm tra các thiết bị cảm biến tại các khu vực quan trọng trong tầng kỹ thuật. Có 6 khu được ký hiệu là A,B,C,D,E,F. Các khu vực này được nối với nhau bằng các hành lang hai chiều như sơ đồ dưới đây. Số ghi trên mỗi đoạn hành lang biểu thị chiều dài tuyến hành lang (đơn vị: mét). Robot bắt đầu từ khu A, và cần kiểm tra toàn bộ hành lang trong hệ thống, đi qua mỗi hành lang ít nhất một lần, sau đó quay trở lại khu A. Tổng quãng đường ngắn nhất robot phải đi để hoàn thành nhiệm vụ là bao nhiêu mét?

Question

Beedemy · Accepted Answer

Lời giải: Đáp án: 109 Vì đồ thị liên thông và có đúng hai đỉnh bậc lẻ là $ A $ và $ D $ nên có đường đi Euler từ $ A $ đến $ D $, tổng quãng đường đi $ 4+3+6+11+5+9+15+2+10+7+20=92\,m $. Bây giờ ta tìm đường đi ngắn nhất từ $ D $ về $ A $, đường đi ngắn nhất là $ DECFA $ với quãng đường là $ 7+2+5+3=17\,m. $ Vậy tổng quãng đường ngắn nhất robot phải đi để hoàn thành nhiệm vụ là $ 92+17=109\,m $

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 58