why were there three geo on tst

when the distrib is CGC:

i think you meant GGG

bro pls post p1 :sob: also was there no nt

p1 was geo combo (holden?)

Taco12 wrote: p1 was geo combo (holden?) bruh why

This is definitely A not G or C... Will post sol later

thanosaops wrote: This is definitely A not G or C... Will post sol later try the problem first! its definitely geo

That's basically my solution. I now agree in hindsight that this is more C than A, but the G part is only motivational...

The answer is $400\cdot 300-190\cdot 24=115440$. Construction is the same as above. Assume $f(0)+f(1)+\dots+f(300)=300$, or increase $f(0)$ until it does. Notice that $f(300)=0$. Let $r_i$ be the remainder when $i$ is divided by $20$, we have \begin{align*} g(0)+g(1)+\dots+g(6000) &= \sum_{i=0}^{6000} g\left((20-r_i)\left\lfloor\frac{i}{20}\right\rfloor+r_i\left\lceil\frac{i}{20}\right\rceil\right) \\ &\le \sum_{i=0}^{6000}\left[(20-r_i)f\left(\left\lfloor\frac{i}{20}\right\rfloor\right)+r_i f\left(\left\lceil\frac{i}{20}\right\rceil\right)\right] \\ &=400\sum_{i=0}^{300}f(i)-190(f(0)+f(300))\\ &=400\cdot 300-190f(0)\\ \end{align*}Denote this bound (*). If $f(0)\ge 24$, we are done so assume otherwise. Let $f(0)=24-a$. Consider blocks of equal positive integers in the sequence $f(0),f(1),\dots,f(300)$. Let the lengths of these blocks be $l_1,l_2,\dots,l_m$. (For example, the sequence $2,2,2,1,1,0,0$ gives $3,2$ as the lengths of such blocks, discarding the trailing zeros.) We have $\sum_{i=1}^m(l_i-1)\ge a$; otherwise, $f(0)+f(1)+\dots+f(300)$ would be at most $(24-a)+(23-a)+\dots+1+(a-1)(24-a)<24+23+\dots+1=300$ which is impossible. The following claim let us finish the problem. Claim: Each block of length $l+1$ lowers $(*)$ by at least $190l$. Proof: Let the block be $f(x)=f(x+1)=\dots=f(x+l)$. Note that $x+l+1\le300$ so $f(x+l)>f(x+l+1)$. For each term of the form $g(t(x+i)+(20-t)(x+(i+1)))$ where $0\le t\le20, 0\le i\le a$, instead of bounding it with $tf(x+i)+(20-t)f(x+(i+1))$ as in (*), we can do $$g(t(x+i)+(20-t)(x+i+1))\le f(x)+\dots+f(x)+f(x+\text{possible remainder})+\left\lfloor\frac{20i+(20-t)}{l+1}\right\rfloor f(x+l+1)$$and thus improving the bound by at least $\left\lfloor\frac{20i+(20-t)}{l+1}\right\rfloor$. Applying this to each of $g(20x),g(19x+(x+1)),\dots,g(20(x+l))$, we can improve (*) by at least $\left\lfloor\frac{0}{l+1}\right\rfloor+\left\lfloor\frac{1}{l+1}\right\rfloor+\dots+\left\lfloor\frac{20l}{l+1}\right\rfloor$. Similarly, for each term of the form $g(t(x+l)+(20-t)(x+(l+1)))$ where $0\le t\le20$, we bound $$g(t(x+l)+(20-t)(x+l+1))\le f(x)+\dots+f(x)+f(x+\text{possible remainder})+\left\lfloor\frac{tl}{l+1}\right\rfloor f(x+l+1)+(20-t)f(x+l+1)$$and thus improving the bound by at least $\left\lfloor\frac{tl}{l+1}\right\rfloor$. Applying this to each of $g(20(x+l)),g(19(x+l)+(x+l+1)),\dots,g((x+l)+19(x+l+1))$, we can improve (*) by at least $\left\lfloor\frac{19l}{l+1}\right\rfloor+\left\lfloor\frac{18l}{l+1}\right\rfloor+\dots+\left\lfloor\frac{l}{l+1}\right\rfloor$. Altogether, this block let us improve the bound by at least $$\left(\left\lfloor\frac{0}{l+1}\right\rfloor+\left\lfloor\frac{1}{l+1}\right\rfloor+\dots+\left\lfloor\frac{20l}{l+1}\right\rfloor\right)+\left(\left\lfloor\frac{19l}{l+1}\right\rfloor+\left\lfloor\frac{18l}{l+1}\right\rfloor+\dots+\left\lfloor\frac{l}{l+1}\right\rfloor\right) = \sum_{i=0}^{19}\left(\left\lfloor\frac{il}{l+1}\right\rfloor+\left\lfloor\frac{il+1}{l+1}\right\rfloor+\dots+\left\lfloor\frac{(i+1)l}{l+1}\right\rfloor\right).$$Surprisingly, this is exactly $190l$ by the following lemma, finishing the claim. Lemma: For any nonnegative integers $n,l$, $$\left\lfloor\frac{nl}{l+1}\right\rfloor+\left\lfloor\frac{nl+1}{l+1}\right\rfloor+\dots+\left\lfloor\frac{(n+1)l}{l+1}\right\rfloor=nl.$$Proof: Suppose the division algorithm gives $(n+1)l=(l+1)k+r$. The left expression then equals $\left\lfloor\frac{(l+1)(k-1)+(r+1)}{l+1}\right\rfloor+\dots+\left\lfloor\frac{(l+1)k+(r-1)}{l+1}\right\rfloor+\left\lfloor\frac{(l+1)k+r}{l+1}\right\rfloor=(l-r)(k-1)+(r+1)k=(l+1)k+r-l=nl.$ $\blacksquare$ By the claim, we can now improve the bound by at least $190\sum_{i=1}^m(l_i-1)\ge 190a$ so the bound is still $400\cdot 300- 190(24-a)-190a = 115440$.

DottedCaculator wrote:

the first thought occur to me is that we need to find a way to discribe how we make the partition of every n.

so above all ,we set n in the form of 20k+r (for all n).then we partite n as averge as we can.now we check the upper bound of sum of g(n) we obtain the first inequality.next by using the symmetry of x and f(0).finally we partite n as we add many x and 0,now we get 3 inequalities about both x and f(0) ,i.e you finish the whole puzzle

f(0)+f(1)+f(2)+..+f(300)<=300 implies that 300 is the greatest value of the f g(n1+n2+..+n20)=g(n0)+g(n1)+g(n2)+..g(n20) The greatest value of g is g(n1+..+n20)=f(n1+..+n20) Therefore g(0)+g(1)+..+g(6000)'s greatest value is 6000.

Here is a much neater solution via grids, since it appears that my solution to USA EGMO TST P2 seems to generalize to higher dimensions. The answer is $\tbinom{481}{2}=\boxed{115440}$. Construction: Take $f(x)=\max(0, 24-x)$ and $g(x)=\max(0, 480-x)$. These functions clearly satisfy the first two conditions, and the third condition is a simple inductive exercise. This selection returns a sum of \[ g(0)+g(1)+\dots+g(6000) = 480+479+\dots+1+0+\dots+0 = \binom{481}{2}. \] Bound: Note that the range of $f$ can be represented by at most $25$ distinct values (by say, Pigeonhole), and we refer to the product of each value and its multiplicity as a block. Main Claim: An upper bound for the sum of the $g(i)$ is the answer to the following easier problem: 2023 USA EGMO TST/2, modified wrote: Consider pairs of functions $(f, g)$ from the set of nonnegative integers to itself such that $f(0) + f(1) + f(2) + \cdots + f(24) \le 300$; for any integers $n_1, \dots, n_{20} \ge 0$, we have \[ g(n_1+\dots+n_{20}) \le f(n_1) + \dots + f(n_{20}). \] Determine the maximum possible value of $g(0) + g(1) + g(2) + \cdots + g(480)$ over all such pairs of functions. Proof. We let the $f(i)$ correspond to the blocks used, where we set it to $0$ if there are less than $25$ blocks, and set the $f(i)$ to correspond to range values in increasing order. (Note: the $f(i)$ need not be in increasing or decreasing order, however.) Now split the set $\{0, 1, \dots, 6000\}$ into $481$ classes labeled $0$ through $480$. For each class $i$, consider the psartitions of $i$ into $20$ parts each at most $24$, and correspond these parts to their $f$-values and add them. This makes the sum of the $g$-values in this problem at least that of those in the original problem, and we are done. Claim: The answer to the problem in the previous claim is $115440$. Proof. Draw the lattice $\{0, 1, \dots, 24\}^{20}$, and at the lattice point $(n_1, \dots, n_{20})$ write down a weight \[ \frac{\binom{24}{n_1} \cdot \dots \cdot \binom{24}{n_{20}}}{\binom{480}{n_1+\dots+n_{20}}} \cdot g(n_1+\dots+n_{20}). \]By Vandermonde's identity, we can sum over all hyperplanes of the form $n_1+\dots+n_{20}=\bullet$, so that the sum of all weights is equal to $g(0)+g(1)+\dots+g(480)$. Lemma: We have for fixed $r_1$ that \[ \sum_{r_2, r_3, \dots, r_{20} \in \{0, 1, \dots, 24\}} \frac{\binom{24}{r_1} \cdot \dots \cdot \binom{24}{r_{20}}}{\binom{480}{r_1+\dots+r_{20}}} = \frac{481}{25}. \]Proof. Bash. $\blacksquare$ Now compute \[ g(0)+g(1)+\dots+g(480) \le \sum \frac{\binom{24}{n_1} \cdot \dots \cdot \binom{24}{n_{20}}}{\binom{480}{n_1+\dots+n_{20}}} \cdot (f(n_1)+\dots+f(n_{20})) \le 20 \sum \frac{\binom{24}{n_1} \cdot \dots \cdot \binom{24}{n_{20}}}{\binom{480}{n_1+\dots+n_{20}}} \cdot f(n_1) = 20 \cdot \frac{481}{25} \sum f(n_i) \le 20 \cdot \frac{481}{25} \cdot 300 = 115440, \]as desired. Hence, $115440$ is also an upper bound on the sum of the $g(i)$, as desired.

Nice geometry problem!

Solution is same as others so here's some waxing about how to think about this problem. First, we have that $f$ is a Young Tableaux. We also pretty easily want to set a bunch of our inequalities to be strict. Taco12 wrote: Consider pairs $(f,g)$ of functions from the set of nonnegative integers to itself such that $f(0) \geq f(1) \geq f(2) \geq \dots \geq f(300) \geq 0$ $f(0)+f(1)+f(2)+\dots+f(300) = 300$ for any 20 nonnegative integers $n_1, n_2, \dots, n_{20}$, not necessarily distinct, we have $$g(k) = \min_{n_1 + n_2 + \dots + n_{20} = k} f(n_1)+f(n_2)+\dots+f(n_{20}).$$ Determine the maximum possible value of $g(0)+g(1)+\dots+g(6000)$ over all such pairs of functions. Sean Li We can make the assumption for bounding that if $(n_1, \dots, n_{20})$ is minimal then we can get the next minimal tuple by incrementing one of $n_i$. Then we can rewrite the problem with the following flavor text. Minecraft wrote: You are being attacked by $20$ identical zombies which each have $300$ health points. Zombies with $i$ health do $\alpha_i \ge 0$ damage, and $\alpha_0 + \dots + \alpha_{300} = 300$. The more damage you do to a zombie, the less damage they do. You alternate between getting attacked by all $20$ zombies, and swinging a sword, doing damage to a zombie until all the zombies are dead. What's the strategy for minimizing damage taken while you are killing the zombies? If $\alpha_{i} = \alpha_{i-1} = \alpha_{i-2} = \alpha_{i-3} = 5$ and $\alpha_{i-4} = 1$, and you have all your zombies at $i$ health points, its probably optimal to attack one zombie until its at $i-4$ health points, then go to the next zombie rather than attacking each zombie one by one. This motivates considering $x_i$ to try and have a decent space of strategies to sift through, as well as the strategy in #12 to consider the scenarios when you have these cliffs you want to attack zombies at. (The official solution makes the additional observation that you can replace the Young Tableaux $f$ with its conjugate; This is equivalent to the cases $f(0) \ge 24$, $f(24) = 0$ effectively being mirrors of each other).