Maths Olympiad Prep

Library / NMO Selection Tests for BMO and IMO /16 of 47

NMO Selection Tests for BMO and IMO

Combinatorics Difficulty 7.9 National Olympiad, round 2 Prove it Romania

Given a positive integer nn, determine all functions ff from the first nn positive integers to the positive integers, satisfying the following two conditions:
(1)∑k=1nf(k)=2n; (1) \sum_{k=1}^{n} f(k) = 2n;
(2)∑k∈Kf(k)=n for no subset K of the first n positive integers. (2) \sum_{k \in K} f(k) = n \text{ for no subset } K \text{ of the first } n \text{ positive integers.}

Solution

If nn is odd, the required functions are the constant function f0≡2f_0 \equiv 2 along with the nn functions fi:{1,…,n}→N∗f_i: \{1, \dots, n\} \to \mathbb{N}^*,
fi(j)={n+1,if j=i,1,if j≠i,i=1,…,n; f_i(j) = \begin{cases} n+1, & \text{if } j = i, \\ 1, & \text{if } j \neq i, \end{cases} \quad i = 1, \dots, n;

notice that f0=f1f_0 = f_1 if n=1n = 1. If nn is even, f0f_0 is to be removed from the list, by (2). All these functions plainly satisfy the conditions in the statement.
Labelling the positive integers in the list f(1),…,f(n)f(1), \dots, f(n) increasingly, a1≤⋯≤ana_1 \le \dots \le a_n, the problem amounts to determining all lists of positive integers a1≤⋯≤ana_1 \le \dots \le a_n such that (1′)∑k=1nak=2n(1') \sum_{k=1}^n a_k = 2n and (2′)∑k∈Kak=n(2') \sum_{k \in K} a_k = n for no subset KK of the first nn positive integers. Notice that an≤n+1a_n \le n+1, by (1′)(1'), and an≠na_n \ne n, by (2′)(2'). With reference again to (1′)(1'), notice further that if an=n+1a_n = n+1, then the other aka_k are all 1, and if an=2a_n = 2, then so are the other aka_k. If nn is even, (2′)(2') rules out the latter case.
Leaving aside the trivial cases n=1n=1 and n=2n=2, let n≥3n \ge 3. To rule out an≠2,n+1a_n \ne 2, n+1, assume, if possible, this is the case, and notice that
a1−an,0,a1,a1+a2,…,a1+a2+⋯+an−1 a_1 - a_n, \quad 0, \quad a_1, \quad a_1 + a_2, \quad \dots, \quad a_1 + a_2 + \dots + a_{n-1}
are pairwise distinct integers, so at least two are congruent modulo nn. Since an≠2,n,n+1a_n \ne 2, n, n+1, the first two cannot be congruent modulo nn, and (2′)(2') rules out the remaining cases.

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.