Maths Olympiad Prep

Library / /2 of 5

Combinatorics Difficulty 9.1 IMO level Prove it United States

Consider pairs (f,g)(f, g) of functions from the set of nonnegative integers to itself such that
* f(0)f(1)f(2)f(300)0f(0) \ge f(1) \ge f(2) \ge \dots \ge f(300) \ge 0;
* f(0)+f(1)+f(2)++f(300)300f(0) + f(1) + f(2) + \dots + f(300) \le 300;
* for any 20 nonnegative integers n1,n2,,n20n_1, n_2, \dots, n_{20}, not necessarily distinct, we have
g(n1+n2++n20)f(n1)+f(n2)++f(n20). g(n_1 + n_2 + \dots + n_{20}) \le f(n_1) + f(n_2) + \dots + f(n_{20}).
Determine the maximum possible value of g(0)+g(1)++g(6000)g(0) + g(1) + \dots + g(6000) over all such pairs of functions.

Solution

Replace 300=24252300 = \frac{24 \cdot 25}{2} with s(s+1)2\frac{s(s+1)}{2} where s=24s = 24, and 20 with kk. The answer is 115440=ks(ks+1)2115440 = \frac{ks(ks+1)}{2}. Equality is achieved at f(n)=max(sn,0)f(n) = \max(s-n, 0) and g(n)=max(ksn,0)g(n) = \max(ks-n, 0). To prove
g(n1++nk)f(n1)++f(nk), g(n_1 + \dots + n_k) \le f(n_1) + \dots + f(n_k),
write it as
max(x1++xk,0)max(x1,0)++max(xk,0) \max(x_1 + \dots + x_k, 0) \le \max(x_1, 0) + \dots + \max(x_k, 0)
with xi=snix_i = s - n_i. This can be proven from the k=2k=2 case and induction.

It remains to show the upper bound. For this problem, define a partition to be a nonincreasing function p:Z0Z0p: \mathbb{Z}_{\ge 0} \to \mathbb{Z}_{\ge 0} such that p(n)=0p(n) = 0 for some nn. The sum of pp is defined to be n=0p(n)\sum_{n=0}^{\infty} p(n), which is finite under the previous assumption. Let L=Z02L = \mathbb{Z}_{\ge 0}^2. The Young diagram of the partition is the set of points
P:={(x,y)L:y<p(x)}. \mathcal{P} := \{(x, y) \in L : y < p(x)\}.
The number of points in P\mathcal{P} is equal to the sum of pp. The conjugate of a partition defined as
p(n)=the number of i for which p(i)>n. p_*(n) = \text{the number of } i \text{ for which } p(i) > n.
This is a partition with the same sum as pp. Geometrically, the Young diagrams of pp and pp_* are reflections about x=yx = y.
Since each g(n)g(n) is independent, we may maximize each one separately for all nn and assume that
g(n)=minn1++nk=n(f(n1)++f(nk)).() g(n) = \min_{n_1+\cdots+n_k=n} (f(n_1) + \cdots + f(n_k)). \quad (*)
The conditions of the problem statement imply that f(s(s+1)2)=0f(\frac{s(s+1)}{2}) = 0. Then, for any nks(s+1)2n \le k \frac{s(s+1)}{2}, there exists an optimal combination (n1,,nk)(n_1, \dots, n_k) in (*) where all nin_i are at most s(s+1)2\frac{s(s+1)}{2}, by replacing any term in an optimum greater than s(s+1)2\frac{s(s+1)}{2} by s(s+1)2\frac{s(s+1)}{2} and shifting the excess to smaller terms (because ff is nonincreasing). Therefore we may extend ff to a partition by letting f(n)=0f(n) = 0 for n>s(s+1)2n > \frac{s(s+1)}{2} without affecting the relevant values of gg. Then (*) implies that gg is a partition as well.

The problem can be restated as follows: ff is a partition with sum s(s+1)2\frac{s(s+1)}{2}, and gg is a partition defined by (*). Find the maximum possible sum of gg. The key claim is that the problem is the same under conjugation.
Claim — Under these conditions, we have
g(n)=minn1++nk=n(f(n1)++f(nk)). g_*(n) = \min_{n_1+\cdots+n_k=n} (f_*(n_1) + \cdots + f_*(n_k)).
Proof. Let F\mathcal{F} and G\mathcal{G} be the Young diagrams of ff and gg respectively, and F=LF\overline{\mathcal{F}} = L \setminus \mathcal{F} and G=LG\overline{\mathcal{G}} = L \setminus \mathcal{G} be their complements. The lower boundary of F\overline{\mathcal{F}} is formed by the points (n,f(n))(n, f(n)) for iZ0i \in \mathbb{Z}_{\ge 0}. By the definition of gg, the lower boundary of G\overline{\mathcal{G}} consists of points (n,g(n))(n, g(n)) which are formed by adding kk points of F\overline{\mathcal{F}}. This means
G=F++Fk times \overline{\mathcal{G}} = \underbrace{\overline{\mathcal{F}} + \cdots + \overline{\mathcal{F}}}_{k \text{ times}}
where ++ denotes set addition. This definition remains invariant under reflection about x=yx = y, which swaps ff and gg with their conjugates. \square

Let AA be the sum of gg. We now derive different bounds on AA. First, by Hermite's identity
n=i=0k1n+ik n = \sum_{i=0}^{k-1} \left\lfloor \frac{n+i}{k} \right\rfloor
we have
A=n=0g(n)n=0i=0k1f(n+ik)=k2n=0f(n)k(k1)2f(0)=k2s(s+1)2k(k1)2f(0). \begin{align*} A &= \sum_{n=0}^{\infty} g(n) \\ &\le \sum_{n=0}^{\infty} \sum_{i=0}^{k-1} f\left(\left\lfloor \frac{n+i}{k} \right\rfloor\right) \\ &= k^2 \sum_{n=0}^{\infty} f(n) - \frac{k(k-1)}{2} f(0) \\ &= k^2 \frac{s(s+1)}{2} - \frac{k(k-1)}{2} f(0). \end{align*}

By the claim, we also get the second bound Ak2s(s+1)2k(k1)2f(0)A \le k^2 \frac{s(s+1)}{2} - \frac{k(k-1)}{2} f_*(0).
For the third bound, note that f(f(0))=0f(f_*(0)) = 0 and thus g(kf(0))=0g(kf_*(0)) = 0. Moreover,
g(qf(0)+r)qf(f(0))+(kq1)f(0)+f(r)=(kq1)f(0)+f(r), g(qf_*(0) + r) \le q \cdot f(f_*(0)) + (k - q - 1)f(0) + f(r) = (k - q - 1)f(0) + f(r),
so we have
A=0q<k0r<f(0)g(qf(0)+r)k(k1)2f(0)f(0)+k0r<f(0)f(r)=k(k1)2f(0)f(0)+ks(s+1)2. \begin{align*} A &= \sum_{\substack{0 \le q < k \\ 0 \le r < f_*(0)}} g(qf_*(0) + r) \\ &\le \frac{k(k-1)}{2} f_*(0) f(0) + k \sum_{0 \le r < f_*(0)} f(r) \\ &= \frac{k(k-1)}{2} f_*(0) f(0) + k \frac{s(s+1)}{2}. \end{align*}

* If f(0)sf(0) \ge s then
Ak2s(s+1)2k(k1)2f(0)ks(ks+1)2. A \le k^2 \frac{s(s+1)}{2} - \frac{k(k-1)}{2} f(0) \le \frac{ks(ks+1)}{2}.
* If f(0)sf_*(0) \ge s then
Ak2s(s+1)2k(k1)2f(0)ks(ks+1)2. A \le k^2 \frac{s(s+1)}{2} - \frac{k(k-1)}{2} f_*(0) \le \frac{ks(ks+1)}{2}.
* Otherwise, f(0)f(0)s2f(0)f_*(0) \le s^2 and
Ak(k1)2f(0)f(0)+ks(s+1)2ks(ks+1)2. A \le \frac{k(k-1)}{2} f_*(0) f(0) + k \frac{s(s+1)}{2} \le \frac{ks(ks+1)}{2}.

In all cases, Aks(ks+1)2A \le \frac{ks(ks+1)}{2}, as desired.

Remark. One can estimate the answer to be around k2s(s+1)2k^2 \frac{s(s+1)}{2} by observing the set addition operation “dilates” F\mathcal{F} by a factor of kk, but significant care is needed to sharpen the bound.

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.