Maths Olympiad Prep

Library / /199 of 220

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Ukraine

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

(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 AA and BB we choose a partition where S=bSA+aSBS = b \cdot S_A + a \cdot S_B is the smallest, where SAS_A and SBS_B denote the amount of edges inside groups AA and BB. We show that this partition satisfies the required condition.

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

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

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