Flight Paths

One way to count the number of airways is to look at all the connections from a single airport to all the other airports. If we do this, we see that n airports are connected to every other airport with n – 1 airways, for a total of n(n – 1) airways. However, since we looked at every airport as the origin, as well as the destination, we must divide this total by 2 to find the total number of unique airways. One of the interesting things here is that even though we are counting lines instead of intersections, the number of airways is the same as the number of intersections in the Maximum Intersections problem! 

There is a direct correspondence between the number of lines in that problem and the number of airports in this problem. The number of intersections in the previous problem is the same as the number of airways in this problem. Note that if we started with only one airport, we would have zero airways just as one line had zero intersections.

Another way we can count the airways is so that it is systematic but also so they don't overlap. As we can see in the images, we can start with one airport and count all n connecting airports. Then when we move on to the next airport, we only need to consider the n – 1 airports that we haven't connected with yet, so the connecting airports that we count now is one less than the first. We continue like this until we get to the last airport which as already been connected to every single airway. So here we are adding together n + (n – 1) + (n – 2) + ... + 2 + 1; do you recognize the sum of consecutive integers from 1 to n in reverse? 

Check out our solution to the Sum of Integers problem for a strategy often cited as the clever method utilized by mathematician Carl Frederich Gauss when he was in primary school.