SEED Science

Home > Science

Solution: Math Puzzle: The FedEx Problem

Solution: The FedEx Problem Math Puzzle

If you look at any one shipment, the system seems silly and wasteful, but let’s look at the big picture. For now imagine that FedEx serves only Boston, New York, Los Angeles, and San Francisco. People need to send packages from each city to each of the others. Here are the flights we need if we ship directly from each city to each of the others:

New York   Boston
New York   Los Angeles
New York   San Francisco
Boston   New York
Boston   San Francisco
Boston   Los Angeles
San Francisco   New York
San Francisco   Boston
San Francisco   Los Angeles
Los Angeles   New York
Los Angeles   Boston
Los Angeles   San Francisco 

That’s 12 flights. Now how does this work with everything going through Memphis? Here are the flights we need:

New York   Memphis
Boston   Memphis
Los Angeles   Memphis
San Francisco   Memphis
Memphis   New York
Memphis   Boston
Memphis   Los Angeles
Memphis   San Francisco

That’s only 8 flights. And, we get a 5th city thrown in as well: Memphis

If only 3 cities were served, it would require 6 flights by either method, but with 4 or more, the FedEx “hub” system requires fewer flights. And the difference gets much greater very quickly. With 10 cities, we’d need 90 direct flights: a flight from each of the 10 cities to the 9 others. 10 x 9 = 90.

With a central hub only 20 flights would be needed: 10 flights from the cities to the hub and 10 return flights.

What happens when there are 100 cities?

 
Print this Page
 |