Library / Ukrainian National Mathematical Olympiad /181 of 201

Ukrainian National Mathematical Olympiad

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Ukraine

Given positive integers $a$ , $b$ , $n$ such that $a + b = n - 1$ . In some school each student has at most $n$ friends from this school. Prove that one can split all the students from this school into two groups: $A$ and $B$ , in such a way that every student from the group $A$ will know at most $a$ students from the group $A$ , and every student from the group $B$ will know at most $b$ students from the group $B$ .

(Anton Trygub)

Solution

Consider a graph, where nodes represent pupils of this school and two nodes are connected by an edge if corresponding pupils are friends. Among all possible partitions of nodes on two sets $A$ and $B$ we choose a partition where $S = b \cdot S_A + a \cdot S_B$ is the smallest, where $S_A$ and $S_B$ denote the amount of edges inside groups $A$ and $B$ . We show that this partition satisfies the required condition.

Indeed, let's assume that there exists a node $X$ with a degree at least $a+1$ in the group $A$ , then all edges coming from $X$ add at least $b(a+1)$ to the sum $S$ . Also, there are no more than $b$ nodes in the group $B$ that are adjacent to $X$ . Thus if we shift $X$ to the group $B$ , the sum $S$ will decrease by at least $b(a+1)$ and increase by $ba$ . Therefore, $S$ decreases and we have a contradiction with our assumption of choosing the partition. Similarly, there is no node in the group $B$ with a degree $\ge b$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.