CombinatoricsDifficulty 9.1IMO levelProve itUnited States
Consider pairs (f,g) of functions from the set of nonnegative integers to itself such that * f(0)≥f(1)≥f(2)≥⋯≥f(300)≥0; * f(0)+f(1)+f(2)+⋯+f(300)≤300; * for any 20 nonnegative integers n1,n2,…,n20, not necessarily distinct, we have g(n1+n2+⋯+n20)≤f(n1)+f(n2)+⋯+f(n20). Determine the maximum possible value of g(0)+g(1)+⋯+g(6000) over all such pairs of functions.
Solution
Replace 300=224⋅25 with 2s(s+1) where s=24, and 20 with k. The answer is 115440=2ks(ks+1). Equality is achieved at f(n)=max(s−n,0) and g(n)=max(ks−n,0). To prove g(n1+⋯+nk)≤f(n1)+⋯+f(nk), write it as max(x1+⋯+xk,0)≤max(x1,0)+⋯+max(xk,0) with xi=s−ni. This can be proven from the k=2 case and induction.
It remains to show the upper bound. For this problem, define a partition to be a nonincreasing function p:Z≥0→Z≥0 such that p(n)=0 for some n. The sum of p is defined to be ∑n=0∞p(n), which is finite under the previous assumption. Let L=Z≥02. The Young diagram of the partition is the set of points P:={(x,y)∈L:y<p(x)}. The number of points in P is equal to the sum of p. The conjugate of a partition defined as p∗(n)=the number of i for which p(i)>n. This is a partition with the same sum as p. Geometrically, the Young diagrams of p and p∗ are reflections about x=y. Since each g(n) is independent, we may maximize each one separately for all n and assume that g(n)=n1+⋯+nk=nmin(f(n1)+⋯+f(nk)).(∗) The conditions of the problem statement imply that f(2s(s+1))=0. Then, for any n≤k2s(s+1), there exists an optimal combination (n1,…,nk) in (*) where all ni are at most 2s(s+1), by replacing any term in an optimum greater than 2s(s+1) by 2s(s+1) and shifting the excess to smaller terms (because f is nonincreasing). Therefore we may extend f to a partition by letting f(n)=0 for n>2s(s+1) without affecting the relevant values of g. Then (*) implies that g is a partition as well.
The problem can be restated as follows: f is a partition with sum 2s(s+1), and g is a partition defined by (*). Find the maximum possible sum of g. The key claim is that the problem is the same under conjugation. Claim — Under these conditions, we have g∗(n)=n1+⋯+nk=nmin(f∗(n1)+⋯+f∗(nk)). Proof. Let F and G be the Young diagrams of f and g respectively, and F=L∖F and G=L∖G be their complements. The lower boundary of F is formed by the points (n,f(n)) for i∈Z≥0. By the definition of g, the lower boundary of G consists of points (n,g(n)) which are formed by adding k points of F. This means G=k timesF+⋯+F where + denotes set addition. This definition remains invariant under reflection about x=y, which swaps f and g with their conjugates. □
Let A be the sum of g. We now derive different bounds on A. First, by Hermite's identity n=i=0∑k−1⌊kn+i⌋ we have A=n=0∑∞g(n)≤n=0∑∞i=0∑k−1f(⌊kn+i⌋)=k2n=0∑∞f(n)−2k(k−1)f(0)=k22s(s+1)−2k(k−1)f(0).
By the claim, we also get the second bound A≤k22s(s+1)−2k(k−1)f∗(0). For the third bound, note that f(f∗(0))=0 and thus g(kf∗(0))=0. Moreover, g(qf∗(0)+r)≤q⋅f(f∗(0))+(k−q−1)f(0)+f(r)=(k−q−1)f(0)+f(r), so we have A=0≤q<k0≤r<f∗(0)∑g(qf∗(0)+r)≤2k(k−1)f∗(0)f(0)+k0≤r<f∗(0)∑f(r)=2k(k−1)f∗(0)f(0)+k2s(s+1).
* If f(0)≥s then A≤k22s(s+1)−2k(k−1)f(0)≤2ks(ks+1). * If f∗(0)≥s then A≤k22s(s+1)−2k(k−1)f∗(0)≤2ks(ks+1). * Otherwise, f(0)f∗(0)≤s2 and A≤2k(k−1)f∗(0)f(0)+k2s(s+1)≤2ks(ks+1).
In all cases, A≤2ks(ks+1), as desired.
Remark. One can estimate the answer to be around k22s(s+1) by observing the set addition operation “dilates” F by a factor of k, 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.