Consider pairs of functions $(f, g)$ from the set of nonnegative integers to itself such that $f(0) + f(1) + f(2) + \cdots + f(42) \le 2022$; for any integers $a \ge b \ge 0$, we have $g(a+b) \le f(a) + f(b)$. Determine the maximum possible value of $g(0) + g(1) + g(2) + \cdots + g(84)$ over all such pairs of functions. Evan Chen (adapting from TST3, by Sean Li)
Problem
Source: USA December TST for EGMO 2023, Problem 2
Tags: functions, function, USA TST
12.12.2022 22:47
I apologize for reporting the post, I thought you were reposting the IMO TST one. Anyways, this is an interesting easier version of IMO TST/3
12.12.2022 22:57
04.01.2023 06:30
The answer is $7993$. To get the bound, we sum the following inequalities: \begin{align*} g(0) &\le f(0) + f(0) \\ g(1) &\le \tfrac{42}{43} \cdot \left( f(0)+f(1) \right) + \tfrac{1}{43} \left( f(0)+f(1) \right) \\ g(2) &\le \tfrac{42}{43} \cdot \left( f(1)+f(1) \right) + \tfrac{1}{43} \left( f(0)+f(2) \right) \\ g(3) &\le \tfrac{42}{43} \cdot \left( f(1)+f(2) \right) + \tfrac{1}{43} \left( f(0)+f(3) \right) \\ g(4) &\le \tfrac{42}{43} \cdot \left( f(2)+f(2) \right) + \tfrac{1}{43} \left( f(0)+f(4) \right) \\ g(5) &\le \tfrac{42}{43} \cdot \left( f(2)+f(3) \right) + \tfrac{1}{43} \left( f(0)+f(5) \right) \\ &\vdotswithin{\le} \\ g(41) &\le \tfrac{42}{43} \cdot \left( f(20)+f(21) \right) + \tfrac{1}{43} \left( f(0)+f(41) \right) \\ g(42) &\le \tfrac{42}{43} \cdot \left( f(21)+f(21) \right) + \tfrac{1}{43} \left( f(0)+f(42) \right) \\ g(43) &\le \tfrac{42}{43} \cdot \left( f(21)+f(22) \right) + \tfrac{1}{43} \left( f(1)+f(42) \right) \\ g(44) &\le \tfrac{42}{43} \cdot \left( f(22)+f(22) \right) + \tfrac{1}{43} \left( f(2)+f(42) \right) \\ g(45) &\le \tfrac{42}{43} \cdot \left( f(22)+f(23) \right) + \tfrac{1}{43} \left( f(3)+f(42) \right) \\ &\vdotswithin{\le} \\ g(82) &\le \tfrac{42}{43} \cdot \left( f(41)+f(41) \right) + \tfrac{1}{43} \left( f(40)+f(42) \right) \\ g(83) &\le \tfrac{42}{43} \cdot \left( f(41)+f(42) \right) + \tfrac{1}{43} \left( f(41)+f(42) \right) \\ g(84) &\le f(42)+f(42). \end{align*}This gives \[ g(0)+\dots+g(84) \le \frac{170}{43} \Big( f(0)+f(1)+\dots+f(42) \Big) \le \frac{170}{43} \cdot 2022 = 7993 + \frac{41}{43}. \]Hence, the desired sum is at most $7993$. Remark: One way to arrive at this is to prove \[g(0)+\dotsb+g(84)\leq 4(f(0)+\dotsb+f(42))-f(n)-f(42-n)\]for any $0\leq n\leq 42$ (which can be done without any extra weights) and then averaging over $n$. There are multiple equality cases, some of which can be obtained by offsetting the construction for IMO TST 3 with $s=1$. For example, \[ f(x) = \max(1-x, 0)+47 \quad\text{and}\quad g(y) = \max(2-y, 0)+94 \]or \[ f(x) = \max(1-x, 0)+(x+26) \quad\text{and}\quad g(y) = \max(2-y, 0)+(y+52). \] Alternative solution by Ankan Bhattacharya The key is the following: Claim: Let $m$ and $n$ be positive integers. Then there exists an $m \times n$ table of nonnegative numbers, not all zero, such that the $m$ rows all have equal sum, the $n$ columns all have equal sum, and the $m+n-1$ antidiagonals all have equal sum. Before describing its proof, we show how it applies to the problem. Let $(\lambda_{a, b})$, with $0 \le a, b \le 42$, be such a $43 \times 43$ table. Scale so that the sum along each antidiagonal $a+b = \bullet$ is one (so then the sum of each row and column is $\tfrac{85}{43}$). Consider the inequalities \[ \lambda_{a, b} g(a + b) \le \lambda_{a, b} f(a) + \lambda_{a, b} f(b). \]Sum this inequality over all $43^2$ choices of $(a, b)$: because of the regularity of the table, this becomes \[ g(0) + \dots + g(84) \le 2 \cdot \frac{85}{43} \cdot \big[f(0) + \dots + f(42)\big] \]after which we may continue as in the other solution. Proof. [Proof of the claim.] Consider all the down-right paths from the top-left cell to the bottom-right cell. Label each cell with the number of paths passing through it, as shown below for $(m, n) = (3, 4)$: \[ \begin{bmatrix*} \tbinom00\tbinom52 & \tbinom10\tbinom42 & \tbinom20\tbinom32 & \tbinom30\tbinom22\\ \tbinom11\tbinom41 & \tbinom21\tbinom31 & \tbinom31\tbinom21 & \tbinom41\tbinom11\\ \tbinom22\tbinom30 & \tbinom32\tbinom20 & \tbinom42\tbinom10 & \tbinom52\tbinom00 \end{bmatrix*} = \begin{bmatrix*} 10 & 6 & 3 & 1\\ 4 & 6 & 6 & 4\\ 1 & 3 & 6 & 10 \end{bmatrix*}. \]Once this grid is constructed, proving it's valid is relatively simple: Each down-right path passes through exactly one point on each antidiagonal. Thus, each antidiagonal sums to the total number of down-right paths. To see that each row has equal sum, express each down-right path as a sequence of $m-1$ Ds and $n-1$ Rs. Then the $k$\textsuperscript{th} row corresponds to points on the $k$\textsuperscript{th} row in down-right paths. In each path, the Ds split the Rs into $m$ groups; the number of such points is $1$ more than the number of Rs in the $k$\textsuperscript{th} group. But the distribution of Rs in the group is the same by symmetry, so each row has equal sum. The proof that each column has equal sum is analogous. The proof of the main claim is complete. $\blacksquare$
01.07.2023 19:46
pain and suffering.... The answer is $7993$, achieved when $f(0)=48$ and $f(i)=47$ for $1\leq i \leq 42$. Also, $g(0) = 96, g(1) = 95$, and $g(i)=94$ for $2\leq i \leq 84$. Let $S = g(0)+g(1) +\dots+g(84)$. We can write \begin{align*} S &\leq (2f(0))+(f(0)+f(1))+(2f(1))+\dots + (2f(42)) \\ &= 4(f(0)+f(1)+\dots + f(42)) - f(0)-f(42). \end{align*} Similarly, we can write \begin{align*} \sum_{i=0}^{41} g(i)&\leq 4f(0)+3f(1)+2f(2)+f(3)+\sum_{i=5}^{41} \left( f\left(\left\lfloor \frac i2 \right\rfloor\right)+\left(\left\lceil \frac i2 \right\rceil\right)\right) \\ f(42) &\leq f(2)+f(40)\\ \sum_{i=43}^{84}g(i) &\leq \sum_{i=43}^{79} \left( f\left(\left\lfloor \frac i2 \right\rfloor\right)+\left(\left\lceil \frac i2 \right\rceil\right)\right)+f(39)+2f(40)+3f(41)+4f(42). \end{align*}Summing, we find \[ S \leq 4(f(0)+f(1) + \dots +f(42)) - f(1)-f(41). \]We can repeat this procedure to find that for all $0\leq n \leq 42$, we have \[ S \leq 4(f(0)+f(1)+\dots + f(42)) - f(n) - f(42-n). \]Let $f(0)+f(1) + \dots + f(42)=k$. By Pigeonhole, there exists an $n$ such that $f(n) + f(42-n) \geq \frac{2k}{43}$. Then $S \leq 4k - \frac{2k}{43} = \frac{170}{43}\cdot k$. This is maximized when $k=2022$ and yields $S\leq7993$, as desired.
26.11.2023 06:59
Here is a slightly different solution than what others posted. Very similar to Ankan's solution in post #5, but the weights used are very different and are much cleaner and nice. The answer is $7993 = \lfloor 2 \cdot \tfrac{85}{43} \cdot 2022 \rfloor$. Construct a grid $G$ with cells $(0, 0)$ through $(42, 42)$ where the cell $(m, n)$ contains the number \[ \frac{\tbinom{42}{m} \cdot \tbinom{42}{n}}{\tbinom{84}{m+n}} \cdot g(m+n). \]Summing over diagonals and summing the results returns \[ g(0)+g(1)+\dots+g(84) \]by Vandermonde's identity. Lemma: The following equality holds: \[ \sum_{m=0}^{42} \frac{\tbinom{42}{m} \cdot \tbinom{42}{n}}{\tbinom{84}{m+n}} = \frac{85}{43}. \]Proof. Expanding the binomial coefficients of the LHS in factorial form rewrites as \[ \frac{1}{\tbinom{84}{42}} \sum_{m=0}^{42} \binom{m+n}{n}\binom{84-m-n}{42-n}. \]We compute the summation in the above using a generating function. It is the coefficient of $x^{42}$ in \[ [(1-x)^{-n-1}][(1-x)^{n-43}] = (1-x)^{-44}, \]which is $\tbinom{85}{43}$. Thus the LHS of the desired is \[ \frac{\tbinom{85}{43}}{\tbinom{84}{42}} = \frac{85}{43}, \]which proves the lemma. Now we compute an upper bound for the sum of the entries of $G$ by summing rectangularly. The sum of the entries of $G$ is at most \[ \sum_{m=0}^{42} \sum_{n=0}^{42} \frac{\tbinom{42}{m} \cdot \tbinom{42}{n}}{\tbinom{84}{m+n}} \cdot (f(m)+f(n)) = 2 \cdot \frac{85}{43} \sum_{k=0}^{42} f(k) = 2 \cdot \frac{85}{43} \cdot 2022. \]Thus \[ g(0)+g(1)+\dots+g(84) \le 2 \cdot \frac{85}{43} \cdot 2022, \]and since the LHS is an integer, it must be at most $7993$, as desired. For equality, one may use one of the examples in other solutions.
02.03.2024 06:22
The answer is $\boxed{7993}$ achieved by $f(0) = 48$ and all other values of $f$ are $47$, $g(0) = 96, g(1) = 95$, and all other values of $g$ are $94$. We have $g(0) + g(1) + \cdots + g(84) = 96 + 95 + 83 \cdot 94 = 7993$. Now we prove the bound. Let $s = g(0) + g(1) + \cdots + g(84)$ and $m = f(0) + f(1) + \cdots + f(42)$. We have \[ g(0) + g(1) + \cdots + g(84) \le \sum_{i=0}^{42} (f(0) + f(i)) + \sum_{i=1}^{42} (f(42) + f(i)) = 42(f(0) + f(42)) + 2 \sum_{i=0}^{42} f(i) - f(0)\] Therefore $s\le 4044 + 42(f(0) + f(42)) - f(0)$. Now notice that \[ s \le \sum_{i=0}^{42} (f(i) + f(i)) + \sum_{i=0}^{41} (f(i) + f(i+1)) = 4m - (f(0) + f(42)) \le 8088 - (f(0) + f(42))\] Notice that if $f(0) + f(42) \ge 95$, then $s \le 8088 - 95 = 7993$ and if $f(0) + f(42) < 95$, then $s \le 4044 + 42 \cdot 94 - f(0) < 7992$. Hence $s \le 7993$ regardless, as desired.