2. You are transporting mangoes by aircraft from Manila to Singapore. There are 12
planes available with the following weight capacities: 2, 2, 3, 3, 4, 7, 8, 8, 10, 10,
11 and 13 tons. Since no two planes may be assigned to the same route, then you
may direct each plane to one of the following 12 routes:
Bangkok–Singapore Hong Kong–Kuala Lumpur
Hong Kong–Singapore Jakarta–Singapore
Kuala Lumpur–Bangkok Kuala Lumpur–Singapore
Manila–Hong Kong Manila–Jakarta
Manila–Kuala Lumpur Manila–Taipei
Taipei–Bangkok Taipei–Hong Kong
What is the maximum number of tons of mangoes you can ship from Manila to
Singapore?
【Solution】
The chart below shows that it is possible to ship 35 tons (5 points) of mangoes from
Manila to Singapore. (5 points)
Route Capacity Shipment
Bangkok–Singapore 4 4
Hong Kong–Kuala Lumpur 2 1
Hong Kong–Singapore 13 13
Jakarta–Singapore 8 8
Kuala Lumpur–Singapore 10 10
Kuala Lumpur–Bangkok 2 1
Manila–Kuala Lumpur 10 10
Manila–Taipei 7 6
Manila–Hong Kong 11 11
Manila–Jakarta 8 8
Taipei–Hong Kong 3 3
Taipei–Bangkok 3 3
It is not possible to ship more than 35 tons of mangoes from Manila to Singapore.
Note that there are four routes leading from Manila and four other routes leading into
Singapore. The highest capacities that can be assigned to these eight routes are 13, 11,
Bạn đang xem 2. - ĐỀ THI OLYMPIC TOÁN TMO VÒNG CÁ NHÂN