Baltic Way 2023 Shortlist

Solution: We start with a lemma. Lemma. For any $n$, $x\in A_n$ implies $\frac{1}{x}\in A_n$. Proof. Induction. Case $n=1$ is clear. Now, if $x=a_i+a_{n-i}\in A_i+A_{n-i}\subset A_n$, then $\frac{1}{a_i}\in A_i$ and $\frac{1}{a_{n-i}}\in A_{n-i}$, and thus $$\frac{1}{x}\in \frac{1}{\frac{1}{A_i}+\frac{1}{A_{n-i}}}\subset A_n.$$ Similarly if $x=(\frac{1}{a_i}+\frac{1}{a_{n-i}}{)}^{-1}$, then $$\frac{1}{x}=\frac{1}{a_i}+\frac{1}{a_{n-i}}\in A_i+A_{n-i}\subset A_n.\square$$ Lower bound. We now prove that $|A_{n+1}|\ge 2|A_n|$ for all $n$, which proves the lower bound. Let $a$ denote the number of elements in $A_n$ which are larger than or equal to $1$ and let $b$ denote the number of elements in $A_n$ which are strictly larger than $1$. Clearly $a=b$ if $1\notin A_n$ and otherwise $a=b+1$.

First note that $A_1+A_n=\{1\}+A_n\subset A_{n+1}$, so $A_{n+1}$ contains at least $a$ elements which are $\ge 2$. Also note that for any $a_n\in A_n$ for which $a_n>1$ we have $$\frac{1}{2}<a_{n+1}:=\frac{1}{\frac{1}{1}+\frac{1}{a_n}}<1$$ and $a_{n+1}\in A_n$. Thus, $A_{n+1}$ contains at least $b$ elements in $(\frac{1}{2},1)$ and thus, by the lemma, at least $b$ elements in $(1,2)$. Therefore, $A_{n+1}$ has at least $a+b$ elements greater than $1$. By the lemma $A_{n+1}$ thus has at least $2(a+b)$ elements. If $a=b$, then $2|A_n|=4a=2(a+b)\le |A_{n+1}|$ and if $a=b+1$, then $2|A_n|=2(2b+1)=2(a+b)\le |A_{n+1}|$.

Upper bound. We then prove the upper bound. Define $s_n:=|A_n|$, let $c_n:=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ be the $n$-th Catalan number, and $b_n:=2^n{c}_{n-1}$. Then $$\begin{array}{rl}\sum _{i=1}^{n-1}{b}_i{b}_{n-i}& =\sum _{i=1}^{n-1}{2}^i\cdot c_{i-1}\cdot 2^{n-i}\cdot c_{n-2-(i-1)}\\ & =2^n\cdot \sum _{i=0}^{n-2}{c}_i{c}_{(n-2)-i}=2^n\cdot c_{n-1}=b_n,\end{array}$$ where we used the well-known recursion formula for the Catalan numbers. We prove that $s_n<b_n$ for all $n$, which certainly is enough since $b_n=\frac{2^n}{n}\left(\genfrac{}{}{0ex}{}{2(n-1)}{n-1}\right)<2^n\cdot 2^{2n}=8^n$. The proof is by induction. The cases $n\le 4$ may be checked by hand, as we have $$s_1=1<2=b_1,s_2=2<4=b_2,s_3=4<16=b_3,\text{and}{s}_4=9<80=b_4.$$ We now assume $n\ge 5$. We have the trivial bound $$s_n\le \sum _{i=1}^{\lfloor \frac{n}{2}\rfloor }2s_i{s}_{n-i}.$$

s_n \le \sum_{i=1}^{n-1} s_i s_{n-i}. $$Usetheinductionhypothesistoget$$ s_n \le \sum_{i=1}^{n-1} s_i s_{n-i} < \sum_{i=1}^{n-1} b_i b_{n-i} = b_n. For $n$ even we need more care. Note that $|A_{n/2} + A_{n/2}| \le \binom{s_{n/2}}{2} + s_{n/2}$ and \left| \frac{1}{\frac{1}{A_{n/2}} + \frac{1}{A_{n/2}}} \right| \le \binom{s_{n/2}}{2} + s_{n/2}. Therefore, for $n$ even we have s_n \le \sum_{i=1}^{\frac{n}{2}-1} 2s_i s_{n-i} + s_{n/2}^2 + s_{n/2} = \sum_{i=1}^{n-1} s_i s_{n-i} + s_{n/2}. We now note that for $n \ge 6$ we have, by the induction hypothesis, $s_3 s_{n-3} < (b_3 - 1) b_{n-3}$, and hence \sum_{i=1}^{n-1} s_i s_{n-i} + s_{n/2} < \sum_{i=1}^{n-1} b_i b_{n-i} - b_{n-3} + b_{n/2} \le \sum_{i=1}^{n-1} b_i b_{n-i} = b_n, $$asCatalannumbersandalsothe$b_n$ are increasing, concluding the proof.