Graphistan
Source: Turkish TST 2011 Problem 8
July 23, 2011
ceiling functioninductiongraph theorycombinatorics proposedcombinatorics
Problem Statement
Graphistan has cities and Graph Air (GA) is running one-way flights between all pairs of these cities. Determine the maximum possible value of the integer such that no matter how these flights are arranged it is possible to travel between any two cities in Graphistan riding only GA flights as long as the absolute values of the difference between the number of flights originating and terminating at any city is not more than