MathDB

C

Part of 2023 Taiwan TST Round 2

Problems(1)

3k+1cities with 4k roads

Source: 2023 Taiwan TST Round 2 Independent Study 1-C

4/7/2023
Integers nn and kk satisfy n>2023k3n > 2023k^3. Kingdom Kitty has nn cities, with at most one road between each pair of cities. It is known that the total number of roads in the kingdom is at least 2n3/22n^{3/2}. Prove that we can choose 3k+13k + 1 cities such that the total number of roads with both ends being a chosen city is at least 4k4k.
Taiwan TSTcombinatoricsTaiwan