Aviaroutes in country
Source: All russian olympiad 2016,Day2,grade 11,P6
May 5, 2016
graph theorynumber theorycombinatorics
Problem Statement
There are cities in the country, some pairs of cities linked two-way through straight flight. For every pair of cities there is exactly one aviaroute (can have interchanges).
Major of every city X counted amount of such numberings of all cities from to , such that on every aviaroute with the beginning in X, numbers of cities are in ascending order. Every major, except one, noticed that results of counting are multiple of .
Prove, that result of last major is multiple of too.