Algebra Challenge – 2025/10/09

Solution: Assume that $k>\dfrac{n(n+1)}{2}$, we have $$(k^2-n^3)-(k-n)^2=k^2-n^3-(n^2-2kn+k^2)=2nk-n^3-n^2$$ $$\ \ \ \ \ \ \ >2n\cdot\dfrac{n(n+1)}{2}-n^3-n^2=0$$Therefore $$k^2-n^3>(k-n)^2\ge 0$$ Rewriting $$k\cdot(r_i+c_i)-r_i\cdot c_i\le n^3$$ as $$k^2-(k-r_i)(k-c_i)\le n^3$$ i.e. $$(k-r_i)(k-c_i)\ge k^2-n^3$$ We have $$(k-r_i)(k-c_i)>(k-n)^2\ge 0\tag{1}$$ Because $r_i\le \dfrac{n^3}{k}$, we have $$k-r_i\ge k-\dfrac{n^3}{k}=\dfrac{k^2-n^3}{k}>0$$ i.e. $$k-r_i>0$$ Similarly, we have $$k-c_i>0$$ Because $n\ge 1$, we have $$k-n>\dfrac{n(n+1)}{2}-n=\dfrac{n(n-1)}{2}\ge 0$$ Based on $(1)$, we have $$\sqrt{k-r_i}\sqrt{k-c_i}>k-n$$ Therefore $$\sum_{i=1}^{n}\sqrt{k-r_i}\sqrt{k-c_i}>n(k-n)\tag{2}$$ By Cauchy-Schwarz inequality, we have $$\Big{(}\sum_{i=1}^{n}\sqrt{k-r_i}\sqrt{k-c_i}\Big)^2\le\Big{(}\sum_{i}^{n}(k-r_i)\Big{)}\cdot\Big(\sum_{i}^{n}(k-c_i)\Big{)}\ \ \ \ \ \ \ \ \ $$ $$=\Big{(}nk-\sum_{i=1}^{n}r_i\Big{)}\cdot\Big{(}nk-\sum_{i=1}^{n}c_i\Big{)}=(nk-n^2)\cdot(nk-n^2)=n^2(k-n)^2$$ Because $k-n>0$ and $n\ge 1$, we have $$\sum_{i=1}^{n}\sqrt{k-r_i}\sqrt{k-c_i}\le n(k-n)$$ However, the above result contradicts $(2)$. Therefore the assumption of $k>\dfrac{n(n+1)}{2}$ is false. We have
$$k\le\dfrac{n(n+1)}{2}$$ with the equality be attainable if we choose $r_i=c_i=n$, and $$k\cdot(r_i+c_i)-r_i\cdot c_i=n^3$$ for every value of $i$, $i=1,2,…,n$. Therefore the maximum value of $k$ is $\dfrac{n(n+1)}{2}$.