Iranian Mathematical Olympiad

We start with a lemma.

Lemma 1. Suppose that are given two sequences $a_1 > a_2 > \dots > a_m$ and $b_1 < b_2 < \dots < b_m$ of positive real numbers as lengths of segments. We start from the origin and at the step $i$ ($1 \le i \le m$), we go up with a segment of length $a_i$ and then we go right with a segment of length $b_i$. Suppose that $l$ is the line connecting origin to the endpoint of the last segment. Show that all segments lie in the top of line $l$.

Proof. Assume to the contrary that there is a first segment which intersects $l$, say $l'$. Obviously, $l'$ is a horizontal segment because if it was vertical, it could not be the first segment intersecting $l$. Suppose that $l' = b_i$. We denote by $O$ and $X$ the origin and the endpoint of the segment $b_i$, respectively. Since $X$ lies below the line $l$, we get that the slope of $OX$ is less than the slope of $l$.
$$\frac{\sum_{j=0}^{i} a_j}{\sum_{j=0}^{i} b_j} = \text{Slope of } OX < \text{Slope of } l = \frac{\sum_{j=0}^{m} a_j}{\sum_{j=0}^{m} b_j}$$
or equivalently
$$\frac{\sum_{j=0}^{i} a_j}{\sum_{j=0}^{m} a_j} < \frac{\sum_{j=0}^{i} b_j}{\sum_{j=0}^{m} b_j} \quad (*)$$

Note that since $b_i$'s are increasing we have
$$i \sum_{j=i+1}^{m} b_j > (m-i) \sum_{j=0}^{i} b_j \Rightarrow i \sum_{j=0}^{m} b_j > m \sum_{j=0}^{i} b_j$$
This implies that the right hand side of $(*)$ is less than $\frac{i}{m}$. Similar arguments show that the left hand side of $(*)$ is greater than $\frac{i}{m}$ (note that $a_i$'s assumed to be decreasing). This contradiction established the lemma. $\Box$

For the main problem suppose that we have divided both $a_i$'s and $b_i$'s into two sets having equal sums.

* $\sum_{i=1}^{k} a_i = \sum_{i=k+1}^{n} a_i$ such that $a_k \le a_{k-1} \le \dots \le a_2 \le a_1, a_n \le a_{n-1} \le \dots \le a_{k+1}$, where $a_1 \ge a_{k+1}$.
* $\sum_{i=1}^{s} b_i = \sum_{i=s+1}^{n} b_i$ such that $b_s \ge b_{s-1} \ge \dots \ge b_2 \ge b_1, b_n \ge b_{n-1} \ge \dots \ge b_{s+1}$, where $b_1 \le b_{s+1}$.

There is no loss of generality in assuming that $k \le \frac{n}{2} \le s$. We will use the following algorithm for constructing the polygon.

* We start from the origin ($C_0$ is the origin).
* For $1 \le i \le s$, at the $i$-th step, we start from $C_{2(i-1)}$, then we go up in a segment of length $a_i$ to get $C_{2i-1}$ and then right in a segment of length $b_i$ to get $C_{2i}$.
* For $s < i \le k$, at the $i$-th step, we start from $C_{2(i-1)}$, then we go down in a segment of length $a_i$ to get $C_{2i-1}$ and then left in a segment of length $b_i$ to get $C_{2i}$.

Note that since the lengths of $a_i$'s and $b_i$'s are assumed to be monotone, according to the lemma, first $2s$ sides of polygon lie in the top of the segment $C_0C_{2s}$ and the next $2(k-s)$ sides lie in the bottom of $C_{2s}C_{2k}$.

* For $k < i \le n$, at the $i$-th step, we start from $C_{2(i-1)}$, then we go down in a segment of length $a_i$ to get $C_{2i-1}$ and then left in a segment of length $b_i$ to get $C_{2i}$.

Again because of the lemma, all these sides lie in the bottom of the segment $C_{2k}C_{2n}$.

Because $\sum_{i=1}^{k} a_i = \sum_{i=k+1}^{n} a_i$ and $\sum_{i=1}^{s} b_i = \sum_{i=s+1}^{n} b_i$, we return to the origin at the end of the algorithm and so we get a polygon. Now it suffices to prove that this polygon is simple.

Obviously, in each part of algorithm the segments can not intersect each other. On the other hand, according to the lemma, two segments from two different parts of algorithm can intersect only if the segment connecting the first and the last vertex of each part lie on the same line. But this is possible only if $k = s$ (it means that there is not any side in the second part of algorithm). In this case we have intersection on the connecting line only if there are some $1 \le t \le k$ and $k+1 \le l \le n$, such that
$$a_1 + \dots + a_t = a_{l+1} + \dots + a_n, \quad a_{t+1} + \dots + a_k = a_{k+1} + \dots + a_l \quad (1)$$
$$b_1 + \dots + b_t = b_{l+1} + \dots + b_n, \quad b_{t+1} + \dots + b_k = b_{k+1} + \dots + b_l \quad (2)$$
Since $\frac{a_1+\dots+a_t}{t} \ge \frac{a_{t+1}+\dots+a_k}{k-t}$ and $\frac{a_{l+1}+\dots+a_n}{n-l} \le \frac{a_{k+1}+\dots+a_l}{l-k}$, from (1) we get
$$\frac{t}{k-t}(a_{t+1} + \dots + a_k) \le a_1 + \dots + a_t = a_{l+1} + \dots + a_n \le \frac{n-l}{l-k}(a_{k+1} + \dots + a_l) \quad (3)$$
So $\frac{t}{k-t} \le \frac{n-l}{l-k}$. Similar arguments for $b_i$'s instead of $a_i$'s imply $\frac{n-l}{l-k} \le \frac{t}{k-t}$. Therefore, $\frac{t}{k-t} = \frac{n-l}{l-k}$. Thus, all inequities in (3) are equalities. So
$$a_t \le \frac{a_1 + \dots + a_t}{t} \le \frac{a_{t+1} + \dots + a_k}{k-t} \le a_{t+1} \le a_t$$
Therefore, $a_1 = a_2 = \dots = a_k$ (say this common value $a$) and similarly, $a_{k+1} = \dots = a_n$ (say this common value $a'$). Now since $a_1 + \dots + a_k = a_{k+1} + \dots + a_n$, we have $ka = (n-k)a'$. In the same manner, $b_1 = b_2 = \dots = b_k$ (say this common value $b$), $b_{k+1} = \dots = b_n$ (say this common value $b'$) and $kb = (n-k)b'$. But since $a = a_1 \ge a_{k+1} = a'$ and $b = b_1 \le b_{s+1} = b'$, we have $1 \le \frac{a}{a'} = \frac{n-k}{k} = \frac{b}{b'} \le 1$. Hence, $a = a'$ and $b = b'$. It means that all the horizontal segments have equal lengths and all the vertical segments have equal lengths, which contradicts problem conditions.