MathDB

Integers

n

and

k

satisfy

n > 2023k^3

. Kingdom Kitty has

n

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

2n^{3/2}

. Prove that we can choose

3k + 1

cities such that the total number of roads with both ends being a chosen city is at least

4k

Problem Statement