Câu hỏi 149
Một quốc gia có $n$ thành phố, một số cặp thành phố được nối với nhau bởi các con đường hai chiều. Có người nhận thấy rằng nếu chia quốc gia thành hai phần theo cách bất kỳ thì có nhiều nhất $k n$ con đường nối giữa hai phần (trong đó $k$ là một số nguyên dương cố định). Số nguyên $m$ lớn nhất (theo $n$ và $k$) là bao nhiêu để chắc chắn tồn tại một tập gồm $m$ thành phố mà không có hai thành phố nào được nối trực tiếp bởi một con đường?