A country with $n$ cities has some two-way roads connecting certain pairs of cities. Someone notices that if the country is split into two parts in any way, then there would be at most $k n$ roads between the two parts (where $k$ is a fixed positive integer). What is the largest integer $m$ (in terms of $n$ and $k$) such that there is guaranteed to be a set of $m$ cities, no two of which are directly connected by a road?
The answer is $m=\left\lceil\frac{n}{4 k}\right\rceil$.

Call a collection of cities independent if no two cities in the collection are joined by a road. Let $r$ and $k$ be integers such that $n=4 k q+r$ where $1 \leq r \leq 4 k$.

First we show that $m \leq\left\lceil\frac{n}{4 k}\right\rceil=q+1$. Let $K_{i}$ denote a set of $i$ cities such that every pair of cities in $K_{i}$ is linked by a road. Consider a country containing $q$ copies of $K_{4 k}$ and one copy of $K_{r}$. An independent set of cities in this country contains at most one city from each $K_{4 k}$ or $K_{r}$ and therefore contains at most $q+1$ cities. Now note that any partition of the cities of the country into two new countries partitions each $K_{4 k}$ and $K_{r}$ into two sets. If $K_{i}$ where $i \leq 4 k$ is partitioned into two sets of cities of sizes $a$ and $b$, then the number of roads between the two sets is $a b \leq \frac{(a+b)^{2}}{4} \leq k i$. Summing this inequality over all copies of $K_{4 k}$ and $K_{r}$ yields that there are at most $k n$ roads between the two new countries. This implies that this particular country satisfies the given condition and it follows that $m \leq\left\lceil\frac{n}{4 k}\right\rceil$.

Now we show that any country satisfying the given condition has an independent set containing at least $\left\lceil\frac{n}{4 k}\right\rceil$ cities. Call a set of cities $i$-separable if it can be partitioned into $i$ disjoint independent sets of cities. Given a country satisfying the conditions, let $S$ be a largest set of cities in the country that is $2 k$-separable. We prove that $|S| \geq n / 2$. By definition of $S$, there exists a partition $A_{1}, A_{2}, \ldots, A_{2 k}$ of the cities in $S$ such that each $A_{i}$ is independent. Let $|S|=t$. Assume for contradiction that $t<\frac{n}{2}$. There are at most $k n$ roads between $S$ and the rest of the country, which by the pigeonhole principle implies that there is a city $u$ not in $S$ that is connected to at most $\frac{k n}{n-t}<2 k$ cities by road. Therefore $u$ is joined by a road to at most $2 k-1$ cities in $S$, and there must be an independent subset $A_{i}$ such that $u$ is not linked by a road to any city in $A_{i}$. Adding $u$ to $S$ maintains the fact that $S$ is $2 k$-separable but contradicts its maximality. Therefore it must follow that $t \geq \frac{n}{2}$. By the pigeonhole principle, one of the sets $A_{1}, A_{2}, \ldots, A_{2 k}$ must contain at least $\frac{t}{2 k} \geq \frac{n}{4 k}$ cities. This proves the claim and therefore $m=\left\lceil\frac{n}{4 k}\right\rceil$.