DE-MO 2015 Problem 3

To prepare a stay abroad, students meet at a workshop including an excursion. To promote interaction between the students, they are to be distributed to two busses such that not too many of the students in the same bus know each other. Every student knows all those who know her. The number of such pairwise acquaintances is $k$ .

Prove that it is possible to distribute the students such that the number of pairwise acquaintances in each bus is at most $\frac{k}{3}$ .