MathDB
Problems
Contests
National and Regional Contests
Russia Contests
All-Russian Olympiad Regional Round
2000 All-Russian Olympiad Regional Round
8.8
8.8
Part of
2000 All-Russian Olympiad Regional Round
Problems
(1)
2000 cities, airlines - All-Russian MO 2000 Regional (R4) 8.8
Source:
9/25/2024
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
1
1
,
2
2
2
,
4
4
4
,
8
8
8
,
.
.
.
...
...
). For each city
A
A
A
, the statistician calculated the number routes with no more than one transfer connecting
A
A
A
with other cities, and then summed up the results for all
2000
2000
2000
cities. He got
100
,
000
100,000
100
,
000
. Prove that the statistician was wrong.
combinatorics