Câu hỏi 13
Có các tuyến đường trực tiếp giữa mỗi hai thành phố trong một quốc gia. Giá vé giữa mỗi cặp thành phố là như nhau ở cả hai hướng. Hai du khách quyết định đến thăm tất cả các thành phố. Khách du lịch đầu tiên bắt đầu tại một thành phố và đi đến thành phố với giá vé đắt nhất (hoặc nếu có một số như vậy, bất kỳ ai trong số họ). Sau đó, anh ta lặp lại quá trình này, không bao giờ đến thăm một thành phố hai lần, cho đến khi anh ta đến tất cả các thành phố (vì vậy anh ta kết thúc ở một thành phố khác với thành phố mà anh ta bắt đầu). Du khách thứ hai cũng có kế hoạch tương tự, ngoại trừ việc anh ta luôn chọn giá vé rẻ nhất, và không nhất thiết phải bắt đầu ở cùng một thành phố. cho thấy rằng khách du lịch đầu tiên chi tiêu ít nhất nhiều nhất cho giá vé như lần thứ hai.