CombinatoricsDifficulty 6.5National OlympiadFind the answer
The attached figure is an undirected graph. The circled numbers represent the nodes, and the numbers along the edges are their lengths (symmetrical in both directions). An Alibaba Hema Xiansheng carrier starts at point A and will pick up three orders from merchants B_{1}, B_{2}, B_{3} and deliver them to three customers C_{1}, C_{2}, C_{3}, respectively. The carrier drives a scooter with a trunk that holds at most two orders at any time. All the orders have equal size. Find the shortest travel route that starts at A and ends at the last delivery. To simplify this question, assume no waiting time during each pickup and delivery.
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
The shortest travel distance is 16, attained by the carrier taking the following stops: A ⇝B2⇝C2⇝B1⇝B3⇝C3⇝C1. There are two slightly different routes with the same length of 16: Route 1: 2(A) →6→7(B2)→8→11(C2)→8→3(B1)→4(B3)→15→14→13(C3)→12(C1). Route 2: 2(A) →6→7(B2)→10→11(C2)→8→3(B1)→4(B3)→15→14→13(C3)→12(C1).
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.