Problem

Source: St. Petersburg MO 2001, 11th grade, P2

Tags: algorithm, graph, graph theory, combinatorics



There are 2000 cities in a country and no roads. Prove that some cities can be connected by a road such that there would be 2 cities with 1 road passing through them, there would be 2 cities with 2 roads passim through them,...,there would be 2 cities with 1000 roads passing through them. Proposed by F. Bakharev