45th Mongolian Mathematical Olympiad

By the induction method we will show that divide in to two subset $A,B$ such that $a_i+b_i$ is prime number for $i|1,n$. If $n=1$ then $\{1,2\}=\{1\}\cup \{2\}$, $1+2=3$ is prime number and $\{1\}\cap \{2\}=\varnothing$. Assume now that the result is proved for $1,2,3,...,n-1$. Now we will show that for $n$. By well known Bertrand's postulate there exists prime number $p$ such that $2n<p<4n$. Because of $p>2n\ge 2$ then $p$-odd prime number. Thus $p=2n+m$, $m$-odd positive integer. Now consider $$(2n,m);(2n-1,m+1);\dots \left(\frac{2n+m+1}{2},\frac{2n+m-1}{2}\right)$$ pairs and those pair's two numbers sum is $p=2n+m$. For other remaining numbers are $1,2,...,m-1$ get new set that is $\{1,2,...,m-1\}$, which is by the induction method dividing into two subsets. Because $m-1$ is even number. Thus the set $\{1,2,3,...,2n\}$ dividing into two subsets.

Let $(a_1+b_1)...(a_n+b_n)=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}...p_s^{{\alpha }_s}$, ${\alpha }_1+...+{\alpha }_s=n$, ${\alpha }_i\in \mathbb{N}$. Hence the number of divisors of $(a_1+b_1)...(a_n+b_n)$ is $N:=({\alpha }_1+1)...({\alpha }_s+1)$.

If ${\alpha }_j=1$ for some $j$ then $$N=2\cdot ({\alpha }_1+1)({\alpha }_2+1)...({\alpha }_{j-1}+1)({\alpha }_{j+1}+1)...({\alpha }_s+1).$$ So we need to prove that following inequality $$\frac{\prod ({\alpha }_j+1)}{{\alpha }_j+1}\le 2^{n-1}.$$

This inequality is same as property (iii). Hence we can assume that ${\alpha }_j+1$ for arbitrary $i\in \{1,2,...,s\}$. Using the Cauchy's inequality, we get that $$\prod _{i=1}^s({\alpha }_i+1)\le {\left(\frac{{\sum }_{i=1}^s({\alpha }_i+1)}{s}\right)}^s={\left(\frac{n+s}{s}\right)}^s.$$

Let us consider $f(x)=(\frac{n+x}{x}{)}^x$ function on $\mathbb{R}$. Taking derivative, we get that $$\begin{array}{rl}{f}^{\prime }(x)& =(1+\frac{n}{x}{)}^x\ln (1+\frac{n}{x})-\frac{n}{x}(1+\frac{n}{x}{)}^{n-1}=\\ & =(1+\frac{n}{x}{)}^{x-1}\cdot \left((1+\frac{n}{x})\ln (1+\frac{n}{x})-\frac{n}{x}\right).\end{array}$$

Observe that $x\le \frac{n}{2}\iff \frac{n}{x}\ge 2$. So $\ln (1+\frac{n}{x})\ge \ln 3>1$, thus we concluded that $(1+\frac{n}{x})\ln (1+\frac{n}{x})-\frac{n}{x}>1>0$. So $f$ is increasing function on $(0;n/2]$. Finally, the $f(x)$ function get maximum value the point $x=\frac{n}{2}$. Hence we can see that $f(\frac{n}{2})=3^{n/2}<2^n$. Proof is completed.