Problem

Source: Turkish TST 2011 Problem 8

Tags: ceiling function, induction, graph theory, combinatorics proposed, combinatorics



Graphistan has $2011$ cities and Graph Air (GA) is running one-way flights between all pairs of these cities. Determine the maximum possible value of the integer $k$ 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 $k.$