BMO 2010 Shortlist

Let $\lfloor x\rfloor$ be the largest integer less than or equal to $x$ and $\lceil x\rceil$ the smallest integer greater than or equal to $x$. The smallest number $S$ that can be represented in the given form is $n-1$, while the largest number is $\lfloor \frac{n^2}{4}\rfloor$. Since $a_2{a}_3\ge a_3$, $a_3{a}_4\ge a_4$, $\dots$, $a_{k-1}{a}_k\ge a_k$, it follows $$S\ge a_1{a}_2+a_3+a_4+\cdots +a_k=n+a_1{a}_2-a_1-a_2=n-1+(a_1-1)(a_2-1)\ge n-1.$$ The equality holds if and only if $a_2=a_3=\cdots =a_{k-1}=1$. Indeed, for $a_2=a_3=\cdots =a_{k-1}=1$ we have $n=a_1+\underset{n-2}{\underbrace{1+1+\cdots +1}}+a_k$, and $$S=a_1\cdot 1+\underset{n-3}{\underbrace{1\cdot 1+1\cdot 1+\cdots +1\cdot 1}}+1\cdot a_k=n-1.$$ If $$S=a_1{a}_2+a_2{a}_3+\cdots +a_{k-1}{a}_k=n-1,$$ then $$\begin{gathered} S=a_1{a}_2+a_2{a}_3+\cdots +a_{k-1}{a}_k= \\ {a}_1+a_2+\cdots +a_k-1\iff \\ \iff a_1(a_2-1)+a_2(a_3-1)+\cdots +a_{k-1}(a_k-1)-(a_k-1)=0\iff \\ \iff a_1(a_2-1)+a_2(a_3-1)+\cdots +(a_k-1)(a_{k-1}-1)=0 \end{gathered}$$ Since $a_j\ge 1$ for all $j\in \{1,2,\dots ,n\}$, we have $a_2=a_3=\cdots =a_{k-1}=1$. From the arithmetic-geometric mean inequality for $k=2$ and $k=3$, we have $$S=a_1{a}_2\le \lfloor {\left(\frac{a_1+a_2}{2}\right)}^2\rfloor =\lfloor \frac{n^2}{4}\rfloor$$ and $$S=a_1{a}_2+a_2{a}_3=a_2(a_1+a_3)\le \lfloor \frac{n^2}{4}\rfloor .$$ Let $a_i$ be the maximal element among $a_1,a_2,\dots ,a_k$. It follows $$\begin{gathered} S=a_1{a}_2+a_2{a}_3+\cdots +a_{k-1}{a}_k= \\ {a}_1{a}_2+a_2{a}_3+\cdots +a_{i-1}{a}_i+a_i^2+a_i{a}_{i+1}+\cdots +a_{k-1}{a}_k-a_i^2\le \\ \le a_1{a}_i+a_2{a}_i+\cdots +a_{i-1}{a}_i+a_i^2+a_i{a}_{i+1}+a_i{a}_{i+2}+\cdots +a_i{a}_k-a_i^2= \\ =a_i(a_1{a}_2+a_2{a}_3+\cdots +a_{k-1}{a}_k)-a_i^2+a_{i}n-a_i^2=a_i(n-a_i)\le \lfloor \frac{n^2}{4}\rfloor . \end{gathered}$$ The equality holds for $k=2$ if and only if $|a_1-a_2|\le 1$ or for $k=3$ if and only if $|(a_1+a_3)-a_2|\le 1$. Indeed, for arbitrary positive integer numbers $a,b$ such that $a\le b$, $a+b=n$, $n>2$ there exists an integer number $\alpha$ such that $b=a+\alpha$. Then $$\begin{gathered} ab=\lfloor \frac{n^2}{4}\rfloor \iff ab=\lfloor \frac{(a+b{)}^2}{4}\rfloor \iff a(a+\alpha )=\lfloor \frac{(2a+\alpha {)}^2}{4}\rfloor \iff \\ {a}^2+\alpha a=\lfloor \frac{4a^2+4\alpha a+{\alpha }^2}{4}\rfloor \iff a^2+\alpha a=a^2+\alpha a+\lfloor \frac{{\alpha }^2}{4}\rfloor \iff \lfloor \frac{{\alpha }^2}{4}\rfloor =0 \end{gathered}$$ $$\iff 0\le \frac{{\alpha }^2}{4}<1\iff 0\le {\alpha }^2<4\iff 0\le {\alpha }^2\le 1\iff |a-b|\le 1.$$ We will prove by induction that all numbers from the interval $$\lfloor n-1,\lfloor \frac{n^2}{4}\rfloor \rfloor$$ can be represented using only the partitions with $a_1=1$. The cases $n=3$ and $n=4$ can be easily verified. Suppose it is true for $n-1$ and will prove for $n$. According to the step of induction we generate all numbers $S^{\prime }=a_1^{\prime }{a}_2^{\prime }+a_2^{\prime }{a}_3^{\prime }+\cdots +a_{k-1}^{\prime }{a}_k^{\prime }$ such that $$S^{\prime }\in \lfloor n-2,\lfloor \frac{(n-1{)}^2}{4}\rfloor \rfloor$$ and $a_1^{\prime }+a_2^{\prime }+\cdots +a_{k-1}^{\prime }+a_k^{\prime }=n-1$. Now, adding 1 as first element to every representation of $S^{\prime }$ we obtain all representations $S$ ($S=S^{\prime }+1$) of $n$ such that $$S\in \lfloor n-1,\lfloor \frac{(n-1{)}^2}{4}\rfloor +1\rfloor ,$$ where $$\lfloor \frac{(n-1{)}^2}{4}\rfloor +1=\lfloor \frac{n^2}{4}-\frac{n}{2}+\frac{1}{4}\rfloor +1.$$ Therefore, we only need to construct the numbers from $\lfloor \frac{n^2}{4}-\frac{n}{2}+\frac{1}{4}\rfloor +2$ to $\lfloor \frac{n^2}{4}\rfloor -1$. Set $k=4$ and $a_1=1$, $a_2=x$, $a_3=\lfloor \frac{n}{2}\rfloor -1$, $a_4=\lfloor \frac{n}{2}\rfloor -x$, with $1\le x\le \lfloor \frac{n}{2}\rfloor -1$. It follows $$S=x+x\left(\lfloor \frac{n}{2}\rfloor -1\right)+\left(\lfloor \frac{n}{2}\rfloor -1\right)\left(\lfloor \frac{n}{2}\rfloor -x\right)=x+\lfloor \frac{n}{2}\rfloor \lfloor \frac{n}{2}\rfloor -x=x+\lfloor \frac{n^2}{4}\rfloor -\lfloor \frac{n}{2}\rfloor .$$ The equality $$x+\lfloor \frac{n}{2}\rfloor \lfloor \frac{n}{2}\rfloor -x=x+\lfloor \frac{n^2}{4}\rfloor -\lfloor \frac{n}{2}\rfloor$$ can be proved considering both cases $n$ odd, and respectively $n$ even. For $x=1,2,\dots ,\lfloor \frac{n}{2}\rfloor -1$ we get all numbers from $1+\lfloor \frac{n^2}{4}\rfloor -\lfloor \frac{n}{2}\rfloor$ to $\lfloor \frac{n^2}{4}\rfloor -1$. Since $$\lfloor \frac{n^2}{4}-\frac{n}{2}+\frac{1}{4}\rfloor +2\ge 1+\lfloor \frac{n^2}{4}\rfloor -\lfloor \frac{n}{2}\rfloor ,$$ this completes the proof. $\square$