69th Belarusian Mathematical Olympiad

Answer:

a) The maximal possible value of area equals $\frac{1}{3}(4^n-1)(4^n+n-1)$ and it is attained at sets $(1,1,\dots ,1,2^{2n})$ and $(2^2,2^4,\dots ,2^{2n-2},1)$.

b) The minimal possible value equals $4(2^n-1{)}^2$ and it is attained in two cases: either the sets $x_i$ and $y_i$ equal $(2^2,2^3,\dots ,2^{n+1})$ and $(2^0,2^1,\dots ,2^{n-1})$ or both sets equal $(2^1,2^2,\dots ,2^n)$.

Since the lengths $x_i$ and $y_j$ are divisors of the given numbers, the total amount of sets is finite, so there exist the minimal area of the rectangle $OABC$. We will prove the following

Lemma. The area of the rectangle $OABC$ is maximal if and only if the next two conditions hold:

1) For each $i$ from $1$ to $n$ either $x_i$ or $y_i$ equals $1$;

2) The difference $|(x_1+x_2+\cdots +x_n)-(y_1+y_2+\cdots +y_n)|$ is minimal among all sets, satisfying condition 1).

Proof of the lemma. Take sets $(x_1,x_2,\dots ,x_n)$ and $(y_1,y_2,\dots ,y_n)$ such that the area of the rectangle $OABC$ is maximal.

First we prove the necessity of the first condition. Suppose there exists $k$ such that both $x_k$ and $y_k$ are greater than $1$. Denote $x_1+x_2+\cdots +x_n=X$, $X-x_k=X_k$, $y_1+y_2+\cdots +y_n=Y$ and $Y-y_k=Y_k$. Then the area of the rectangle $OABC$ equals $S=XY=(X_k+x_k)(Y_k+y_k)$. Without loss of generality let $X_k\ge Y_k$. Replace in the sets $(x_i)$ and $(y_i)$ the lengths $x_k$ and $y_k$ by $1$ and $S_k$, respectively. The area of the new rectangle equals $S^{\prime }=(X_k+1)(Y_k+S_k)$. The difference between new and old areas equals

$$S^{\prime }-S=(X_k+1)(Y_k+S_k)-(X_k+x_k)(Y_k+y_k)=(X_k{y}_k-Y_k)(x_k-1)>0,$$

which contradicts the minimality of $S$.

Now we prove the necessity of the second condition. The first condition implies

$$X+Y=S_1+S_2+\cdots +S_n+n.$$

This sum depends only on the given values $S_1,S_2,\dots ,S_n$, denote this sum by $C$. The area of the rectangle $OABC$ equals $S=XY=X(C-X)$, which is the quadratic polynomial of the variable $X$. The corresponding parabola is opened to the bottom and the abscissa of its vertex equals $C/2$ (which corresponds $X=Y$). Hence the area of the rectangle is maximal when $X$ is closest to $C/2$, which is equivalent to the minimality of $|X-Y|$.

To prove the sufficiency of the conditions 1) and 2) note that for all sets satisfying these conditions the values of $X$ and $Y$ are the same (up to permutation), hence they all provide the maximal value of the area. The lemma is proved.

Proceed to the solution of a). Since $2^{2n}=1+2^0+2^1+\cdots +2^{2n-1}$, we have

$$2^{2n}>2^2+2^4+\cdots +2^{2n-2},$$

whence the conditions of the lemma are satisfied if and only if one set equals $(1,1,\dots ,1,2^{2n})$ while the second set equals $(2^2,2^4,\dots ,2^{2(n-1)},1)$. Wherein the maximal possible area of the rectangle equals $\frac{1}{3}(4^n-1)(4^n+n-1)$. Thus, a) is finished.

To find the minimal possible area, we use the Cauchy-Bunyakovsky inequality

$$(x_1+x_2+\cdots +x_n)(y_1+y_2+\cdots +y_n)\ge (\sqrt{x_1{y}_1}+\sqrt{x_2{y}_2}+\cdots +\sqrt{x_n{y}_n}{)}^2=(\sqrt{S_1}+\sqrt{S_2}+\cdots +\sqrt{S_n}{)}^2.$$

If there exist at least one pair of sets $(x_i)$ and $(y_i)$ at which this inequality is the equality, then the last expression provides the minimal possible area. Moreover, then this minimal value is attained only for such sets $(x_i)$ and $(y_i)$. The Cauchy-Bunyakovsky inequality turns into the equality if and only if $\frac{x_1}{y_1}=\frac{x_2}{y_2}=\cdots =\frac{x_n}{y_n}$. Since $x_1{y}_1=S_1=4$, there exist the three variants: $x_1=4$, $y_1=1$; $x_1=1$, $y_1=4$; and $x_1=y_1=2$. First two variants give the pair $(2^2,2^3,\dots ,2^{n+1})$ and $(2^0,2^1,\dots ,2^{n-1})$ of sets, and the third variant gives two sets equal $(2^1,2^2,\dots ,2^n)$. Both cases provide the minimal possible area $4(2^n-1{)}^2$.