Vishal starts with $n$ copies of the number $1$ written on the board. Every minute, he takes two numbers $a, b$ and replaces them with either $a+b$ or $\min(a^2, b^2)$. After $n-1$ there is $1$ number on the board. Let the maximal possible value of this number be $f(n)$. Prove $2^{n/3}<f(n)\leq 3^{n/3}$.
Problem
Source: CMO 2022 P3
Tags: combinatorics
awesomeming327.
12.03.2022 07:46
optimal strategy: for 1,2,3,4,5: just add them all for n>5: for odd numbers n, take a 1 away, construct the best possible construction for the rest of the 1's, then add the 1 back in (wait does this work) for even numbers n, split it in half, take the best construction for each half, then min(squares)
MortemEtInteritum
12.03.2022 07:50
For the upper bound, the general idea is to consider $S=\log_3 x_1+\log_3 x_2+\dots+\log_3 x_k$ where $x_1, \dots, x_k$ are the numbers on the board. Unless Vishal makes the move $(b, 1)\rightarrow b+1$, the value of this sum is (nonstrictly) decreasing. Let $x$ be the number of times he makes the move $(1, 1)\rightarrow 2$, and let $y$ be the number of times he goes $(2, 1)\rightarrow 3$. Some bounding (namely $2x+y\leq n$ and $x\geq y$ shows us that $S$ increases by at most $\frac{n}{3}$ during this process, giving the desired upper bound. For the lower bound, I did some sketchy induction by generalizing the lower bound to $f(n)\geq 2^{\lceil (n+1)/2\rceil\cdot 2/3}$, which felt suspiciously like a fakesolve...but I basically said that if $n=2m$, $f(n)\geq f(m)^2\geq 2^{\lceil (m+1)/2\rceil\cdot 4/3}\geq 2^{\lceil (2m+1)/2\rceil\cdot 2/3}$. Similarly if $n=2m+1$, $f(n)\geq f(m)^2\geq 2^{\lceil (m+1)/2\rceil\cdot 4/3}\geq 2^{\lceil (2m+2)/2\rceil\cdot 2/3}$. I'm not sure why this strikes me as a fakesolve, but it just feels wrong :shrug:
awesomeming327.
12.03.2022 07:51
I did an very suspicious bash on the fact that if the final number came from a,b then a,b has to be maximal constructions idk this was a wacky problem upper bound wasn't too bad lower bound for evens was easy lower bound for odds was murder
CANBANKAN
12.03.2022 09:07
The key idea is to consider how the process ends, and use divide and conquer. I will prove $2^{\frac{n+1}{3}} \le f(n)\le 3^{\frac n3}$
For $2^{\frac{n+1}{3}}\le f(n)$: we can check this holds for $n=2,3$, and for $n$ odd we use the first $\frac{n-1}{2}$ numbers to form $f(\frac{n-1}{2})$ and other $\frac{n+1}{2}$ numbers to form $f(\frac{n+1}{2})$. Then we get $\min\{f(\frac{n-1}{2}), f(\frac{n+1}{2})\}^2\ge 2^{2\frac{\frac{n-1}{2}+1}{3}}=2^{2\frac{n+1}{6}}=2^{\frac{n+1}{3}}$. $n$ even is similar.
For $f(n)\le 3^{\frac n3}$. Consider how the process ends. $t$ numbers contribute to one number while $n-t$ numbers contribute to the other. Clearly, $f(t)f(n-t)\le 3^{\frac n3}$ by i.h. Check $f(t)+f(n-t)\le 3^{\frac n3}$ which is boring (of course I finished all the details in the test)
awesomeming327.
12.03.2022 19:46
oh are zee i did something kinda similar but i completely just threw the $n$ odd part.
CT17
18.03.2022 23:03
Does this work?
Let $a_1$, $a_2$, $a_3$, $\dots$ denote the number of moves where $1$ is added to $1$, $2$, $3$, $\dots$, respectively. Let $k$ be the maximal index such that $a_k > 0$. We can immediately make the following observations:
1) $2a_1 + a_2 + \dots + a_k\le n$ for all valid move sequences.
2) For any valid move sequence, $a_2\le a_1$.
3) If $x$ and $y$ are nonnegative integers such that $2x + y\le n$ and $y\le x$, then there exists a valid move sequence with $a_1 = x$, $a_2 = y$, and $a_i = 0$ for all $i\ge 3$.
Claim: the maximum value of $A = \prod_{i=1}^{k} \left(\frac{i+1}{i}\right)^{a_i}$ occurs when $a_i = 0$ for all $i\ge 3$.
Proof: consider any valid move sequence. Then we perform the following operation:
If $\sum_{i=3}^{k} a_i$ is even, we increase $a_1$ by $\frac{1}{2}\sum_{i=3}^{k} a_i$ and replace $a_i$ with $0$ for all $i\ge 3$.
If $\sum_{i=3}^{k} a_i$ is odd and $a_2\neq 0$, we increase $a_1$ by $\frac{1}{2} + \frac{1}{2}\sum_{i=3}^{k} a_i$, replace $a_i$ with $0$ for all $i\ge 3$, and reduce $a_2$ by $1$.
If $\sum_{i=3}^{k} a_i$ is odd and $a_2 = 0$, we increase $a_1$ by $-\frac{1}{2} + \frac{1}{2}\sum_{i=3}^{k} a_i$, replace $a_i$ with $0$ for all $i\ge 3$, and replace $a_2$ with $1$.
Clearly there exists a valid move sequence for the values of $\{a_i\}$ resulting from this operation. Moreover, the value of $A$ is not decreased, so the claim is proved.
With the claim, it is not hard to verify that the maximum value of $A$ is at most $3^{\frac{n}{3}}$. Since the product of the numbers on the board is initially $1$ and increases by a factor of at most $A$, our proof of the upper bound is complete.
We have two cases.
Case 1: $2\cdot 2^k\le n < 3\cdot 2^k$ for some $k$. Choose $2\cdot 2^k$ copies of $1$ on the board and ignore the rest (we can add them in at the end for a negligible increase). Pair off and add these numbers to create $2^k$ copies of $2$. Then repeatedly pair off these numbers and apply the $\text{min}(a^2,b^2)$ operation. The final number on the board is at least $2^{2^k} > 2^{\frac{n}{3}}$, as desired.
Case 2: $3\cdot 2^k\le n < 4\cdot 2^k$ for some $k$. Choose $3\cdot 2^k$ copies of $1$ on the board and ignore the rest (again, we can add them in at the end for a negligible increase). Group these numbers into triplets and add each triplet together to create $2^k$ copies of $3$. Then repeatedly pair off these numbers and apply the $\text{min}(a^2,b^2)$ operation. The final number on the board is at least $3^{2^k} = 2^{2^k\text{log}_2(3)} > 2^{\frac{n}{3}}$, as desired.
LLL2019
21.03.2022 07:54
CANBANKAN wrote:
The key idea is to consider how the process ends, and use divide and conquer. I will prove $2^{\frac{n+1}{3}} \le f(n)\le 3^{\frac n3}$
For $2^{\frac{n+1}{3}}\le f(n)$: we can check this holds for $n=2,3$, and for $n$ odd we use the first $\frac{n-1}{2}$ numbers to form $f(\frac{n-1}{2})$ and other $\frac{n+1}{2}$ numbers to form $f(\frac{n+1}{2})$. Then we get $\min\{f(\frac{n-1}{2}), f(\frac{n+1}{2})\}^2\ge 2^{2\frac{\frac{n-1}{2}+1}{3}}=2^{2\frac{n+1}{6}}=2^{\frac{n+1}{3}}$. $n$ even is similar.
For $f(n)\le 3^{\frac n3}$. Consider how the process ends. $t$ numbers contribute to one number while $n-t$ numbers contribute to the other. Clearly, $f(t)f(n-t)\le 3^{\frac n3}$ by i.h. Check $f(t)+f(n-t)\le 3^{\frac n3}$ which is boring (of course I finished all the details in the test)
yep the trick for the lower bound was really ingenious, the motivation was that $2^{\frac{n}{3}}$ I was unable to induct on, and it seemed like I was off by some factor $2^{\frac{1}{6}}$, so I thought about maybe changing the bound to $2^{\frac{2n+1}{6}},$ which then lead me to think about $2^{\frac{n+c}{3}}$ from which I saw the stronger bound.
mathaddiction
14.05.2022 05:02
We first show $f(n)\leq 3^{\frac{n}{3}}$. We proceed by strong induction. The base cases are obvious. Now suppose in the last step the two numbers are $c$ and $d$, where they are formed by $a$ copies of $1$ and $b$ copies of $1$ respectively, suppose $a\leq b$. $$\min(c^2,d^2)\leq \min(f(a)^2,f(b)^2)=f(a)^2\leq f(\lfloor\frac{n}{2}\rfloor)^2\leq 3^{\frac{n}{3}}$$By inductive hypothesis, meanwhile, if $a\geq 2$ then $$c+d\leq 3^{\frac{a}{3}}+3^\frac{b}{3}\leq 2\cdot 3^{\frac{b}{3}}\leq 3^{\frac{a+b}{3}}$$as $2\leq 3^{\frac{a}{3}}$. If $a=1$, then $c\leq f(a)\leq 1$ hence $$c+d\leq 1+3^{\frac{b}{3}}\leq 3^{\frac{b+1}{3}}$$as desired. Now we show that $f(n)>2^{\frac{n}{3}}$. Indeed it is easy to show that $f(1)=1$, $f(2)=2$ and $f(3)=3$. Now we claim that (i) If $2^k\leq a<3\cdot 2^{k-1}$ then $f(n)\geq 2^{2^{k-1}}$ (ii) If $3\cdot 2^{k-1}\leq a<2^{k+1}-1$ then $f(n)\geq 3^{2^{k-1}}$ Indeed using the fact that $f(2m+1)\geq f(m)^2$ and the base cases this is obvious using simple induction. Now $$2^{2^{k-1}}> 2^{\frac{3\cdot 2^{k-1}-1}{3}}$$while $$3^{3\cdot 2^{k-1}}> 2^{4\cdot 2^{k-1}}=2^{2^{k+1}}$$so we are done.
GAOMITIM
24.06.2022 03:22
What would be the MOHS difficulty for this question?
Rexaria112
09.08.2022 20:47
The lower bound: Claim: let $n$ be a natural number greater than 3, then: $f(n)> 2^{\frac{n}{3}+\frac{1}{2}}$ . Proof: notice that $f(2x) \geq {f(x)}^2$ and $f(2x+1) \geq {f(x)}^2+1$. Also we can check manually the original lower bound inequality for $\{1,2\}$ and the strong lower bound inequality for $\{3,4,5\}$. Then we proceed by strong induction; write for $n \geq 3$: $\bullet f(2n) \geq {f(n)}^2 > 2^{\frac{2n}{3}+1} \geq 2^{\frac{2n}{3}+\frac{1}{2}}$ $\bullet f(2n+1) \geq {f(n)}^2 > 2^{\frac{2n}{3}+1} > 2^{\frac{2n}{3}+\frac{1}{2}+\frac{1}{3}} = 2^{\frac{2n+1}{3}+\frac{1}{2}}$ And the claim is proved.$\square$ The upper bound: We proceed by strong induction. Notice that the last pair on the board can be written as $f(m),f(n-m)$ since we need to maximize $f(n)$. We encounter two cases: $\bullet f(n)=min\{{f(m)}^2,{f(n-m)}^2\} \leq {f(\left \lfloor \frac{n}{2} \right \rfloor)}^2 \leq 3^{\frac{2}{3}\left \lfloor \frac{n}{2} \right \rfloor} \leq 3^\frac{n}{3}$ $ \bullet f(n)=f(m)+f(n-m)$: check manually the cases where $n \in \{1,2,3,4,5\}$, and assume WLOG $m \leq \left \lfloor \frac{n}{2} \right \rfloor$: First case $m=1$: Notice that when $n \geq 6$ the following holds: $1+3^{\frac{n}{3}} \leq 3^{\frac{1+n}{3}} \Leftrightarrow 1 \leq (\sqrt[3]{3}-1)3^{\frac{n}{3}}$ Second case $m\neq 1$: Notice that $f(n) = f(m)+f(n-m) \leq f(m)f(n-m) \leq 3^{\frac{n}{3}}$ So we are done.$\blacksquare$
IAmTheHazard
01.09.2023 01:12
I assume that $n>1$, otherwise the problem is wrong since $f(1)=1<2^{1/3}$. For the lower bound, I claim that we can strengthen to $2^{(n+1)/3}$ (nonstrict). For $n \leq 5$ just add everything. Otherwise split into $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$ and reduce to having two numbers $f(\lfloor n/2\rfloor)$ and $f(\lceil n/2\rceil)$ on the board. Then apply the second operation to get at least $$f(\lfloor n/2\rfloor)^2 \geq (2^{(\tfrac{n-1}{2}+1)/3})^2=2^{(n+1)/3},$$which finishes by induction. For the upper bound, consider the last two numbers on the board, which must be at most $f(a)$ and $f(b)$ for some choice of $a,b>0$ such that $a+b=n$. Bash out $n \leq 4$ again to check that the upper bound holds for these $n$. Then observe that $$\min(3^{2a/3},3^{2b/3}) \leq 3^{n/3},$$and $$3^{a/3}+3^{b/3}\leq 3^{1/3}+3^{(n-1)/3}$$since $3^{x/3}$ is convex. It suffices to show that the RHS is at most $3^{n/3}$ for $n \geq 5$. This is equivalent to saying that $\sqrt[3]{3} \leq \sqrt[3]{3}^{n-1}(\sqrt[3]{3}-1) \iff \sqrt[3]{3}^{n-2}(\sqrt[3]{3}-1) \geq 1$, so it suffices to check this for $n=3$, in which case it is just $3\sqrt[3]{3} \geq 4 \iff 81 \geq 64$ which is true.
lamphead
03.03.2024 18:39
For the lower bound/odd case, why does it follow that $$f(\lfloor n/2\rfloor)^2 \geq (2^{(\tfrac{n-1}{2}+1)/3})^2$$I'm pretty sure that the +1 in the exponent comes from the strengthened lower bound. Without the strengthened bound, it seems that $$f\left(\frac{n-1}{2}\right)^2 > 2^{\frac{n-1}{3}}$$which isn't enough. So, my main question is why a strengthened condition leads to the proof, while the original condition (which contains the strengthened condition (?) since $\frac{n}{3}<\frac{n+1}{3}$) can't. And how does one even come up with the strengthened condition, intuition wise? Is it from testing small cases like $n=1$ to $n=5$? Is it a general technique to prove a stronger condition of an equality to prove the statement in question? Thanks.