MathDB

There are 2000 cities in the country. Every city is connected by non-stop two-way airlines with some other cities, and for each city, the number of airlines originating from it is a factor of two. (i.e.

1

2

4

8

...

). For each city

A

, the statistician calculated the number routes with no more than one transfer connecting

A

with other cities, and then summed up the results for all

2000

cities. He got

100,000

. Prove that the statistician was wrong.

Problem Statement