Problem

Source:

Tags: ceiling function, combinatorics proposed, combinatorics



The road ministry has assigned $80$ informal companies to repair $2400$ roads. These roads connect $100$ cities to each other. Each road is between $2$ cities and there is at most $1$ road between every $2$ cities. We know that each company repairs $30$ roads that it has agencies in each $2$ ends of them. Prove that there exists a city in which $8$ companies have agencies.