Problem
ALG-B2-M01-P018 Two sets with small sum
Sets \(A\) and \(B\) each consist of \(n\) distinct positive integers, and the sum of the numbers in each set is \(n^2\). Prove that \(A\) and \(B\) have a common element.
Hint 1. Assume the sets are disjoint.
Hint 2. Then the union contains \(2n\) distinct positive integers.
Assume \(A\cap B=\varnothing\). Then \(A\cup B\) contains \(2n\) distinct positive integers, so the sum of all its elements is at least \(1+2+\cdots+2n=n(2n+1)\). On the other hand, this sum equals \(n^2+n^2=2n^2\). But \(n(2n+1)>2n^2\), a contradiction. Hence a common element exists.
A. Source analysis. Main objects: inequalities, order, an extremal element, or an invariant. The obvious first move usually gives only a local estimate. The hidden observation is to choose the right nondecreasing quantity, or to add/multiply inequalities only after signs are controlled. The needed step is an ordering, an invariant, a product transformation, or a boundary case.
F. Difficulty justification. Regional level 6: the hidden step is estimating the union by the minimal possible sum.
G. Why this is not a one-step exercise. The sets cannot be compared element by element; one must pass to the union.