Olympiad Maths Prep

Library / /6 of 14

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)kKf(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 f02f_0 \equiv 2 along with the nn functions fi:{1,,n}Nf_i: \{1, \dots, n\} \to \mathbb{N}^*,
fi(j)={n+1,if j=i,1,if ji,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, a1ana_1 \le \dots \le a_n, the problem amounts to determining all lists of positive integers a1ana_1 \le \dots \le a_n such that (1)k=1nak=2n(1') \sum_{k=1}^n a_k = 2n and (2)kKak=n(2') \sum_{k \in K} a_k = n for no subset KK of the first nn positive integers. Notice that ann+1a_n \le n+1, by (1)(1'), and anna_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 n3n \ge 3. To rule out an2,n+1a_n \ne 2, n+1, assume, if possible, this is the case, and notice that
a1an,0,a1,a1+a2,,a1+a2++an1 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 an2,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.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.