$a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n$ are $2n$ positive real numbers such that $a_1,a_2,\cdots ,a_n$ aren't all equal. And assume that we can divide $a_1,a_2,\cdots ,a_n$ into two subsets with equal sums.similarly $b_1,b_2,\cdots ,b_n$ have these two conditions. Prove that there exist a simple $2n$-gon with sides $a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n$ and parallel to coordinate axises Such that the lengths of horizontal sides are among $a_1,a_2,\cdots ,a_n$ and the lengths of vertical sides are among $b_1,b_2,\cdots ,b_n$.(simple polygon is a polygon such that it doesn't intersect itself)
Problem
Source: iran TST 2015 third exam p3
Tags: combinatorics
15.10.2016 16:00
andria wrote: $a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n$ are $2n$ positive real numbers such that $a_1,a_2,\cdots ,a_n$ aren't all equal. And assume that we can divide $a_1,a_2,\cdots ,a_n$ into two subsets with equal sums.similarly $b_1,b_2,\cdots ,b_n$ have these two conditions. Prove that there exist a simple $2n$-gon with sides $a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n$ and parallel to coordinate axises Such that the lengths of horizontal sides are among $a_1,a_2,\cdots ,a_n$ and the lengths of vertical sides are among $b_1,b_2,\cdots ,b_n$.(simple polygon is a polygon such that it doesn't intersect itself) http://www.artofproblemsolving.com/community/c6h1248171p6414327
02.11.2016 05:34
bump! Does anyone have a solution?
18.12.2017 11:22
Divide $\{a_i\}_{1\leq i\leq n}$ and $\{b_i\}_{1\leq i\leq n}$ respectively into two sets: $\{a_i\}_{1\leq i\leq n}=\{x_i\}_{1\leq i\leq k}\cup\{y_i\}_{1\leq i\leq n-k}$ such that $k\leq \frac{n}{2}, \sum_{i=1}^{k}x_i=\sum_{i=1}^{n-k}y_i,$ $x_1\geq x_2\geq \dots\geq x_k, y_1\leq y_2\leq \dots\leq y_{n-k};$ $\{b_i\}_{1\leq i\leq n}=\{z_i\}_{1\leq i\leq l}\cup\{w_i\}_{1\leq i\leq n-l}$ such that $l\leq \frac{n}{2}, \sum_{i=1}^{l}z_i=\sum_{i=1}^{n-l}w_i,$ $z_1\geq z_2\geq \dots\geq z_l, w_1\leq w_2\leq \dots\leq w_{n-l}.$ Let $X_j=\sum_{i=1}^{j}x_i, Y_j=\sum_{i=1}^{j}y_i, Z_j=\sum_{i=1}^{j}z_i, W_j=\sum_{i=1}^{j}w_i$, we construct a $2n$-polygon $P_1P_2\dots P_{2n}$ as follows: $P_{2i-1}=(X_i,W_{i-1}), P_{2i}=(X_i,W_i)(1\leq i\leq k),$ $P_{2i-1}=(Y_{n-i},W_{i-1}), P_{2i}=(Y_{n-i},W_{i})(k+1\leq i\leq n-l),$ $P_{2i-1}=(Y_{n-i},Z_{n-i+1}), P_{2i}=(Y_{n-i},Z_{n-i})(n-l+1\leq i\leq n).$ To prove $P_1P_2\dots P_{2n}$ is simple, it suffices to show that (1)$\frac{W_1}{X_1}\leq \frac{W_2}{X_2}\leq \dots\leq \frac{W_k}{X_k}\leq \frac{Z_l}{Y_l}\leq \frac{Z_{l-1}}{Y_{l-1}}\leq \dots\leq \frac{Z_1}{Y_1};$ (2)$\frac{W_{k-1}}{X_{k-1}}< \frac{Z_{l-1}}{Y_{l-1}}.$ (1) is easy; Suppose (2) is false, by calculation we can conclude that all $a_i$'s are equal and that all $b_i$'s are equal, contradiction.
02.05.2023 05:49
sccdgsy wrote: Divide $\{a_i\}_{1\leq i\leq n}$ and $\{b_i\}_{1\leq i\leq n}$ respectively into two sets: $\{a_i\}_{1\leq i\leq n}=\{x_i\}_{1\leq i\leq k}\cup\{y_i\}_{1\leq i\leq n-k}$ such that $k\leq \frac{n}{2}, \sum_{i=1}^{k}x_i=\sum_{i=1}^{n-k}y_i,$ $x_1\geq x_2\geq \dots\geq x_k, y_1\leq y_2\leq \dots\leq y_{n-k};$ $\{b_i\}_{1\leq i\leq n}=\{z_i\}_{1\leq i\leq l}\cup\{w_i\}_{1\leq i\leq n-l}$ such that $l\leq \frac{n}{2}, \sum_{i=1}^{l}z_i=\sum_{i=1}^{n-l}w_i,$ $z_1\geq z_2\geq \dots\geq z_l, w_1\leq w_2\leq \dots\leq w_{n-l}.$ Let $X_j=\sum_{i=1}^{j}x_i, Y_j=\sum_{i=1}^{j}y_i, Z_j=\sum_{i=1}^{j}z_i, W_j=\sum_{i=1}^{j}w_i$, we construct a $2n$-polygon $P_1P_2\dots P_{2n}$ as follows: $P_{2i-1}=(X_i,W_{i-1}), P_{2i}=(X_i,W_i)(1\leq i\leq k),$ $P_{2i-1}=(Y_{n-i},W_{i-1}), P_{2i}=(Y_{n-i},W_{i})(k+1\leq i\leq n-l),$ $P_{2i-1}=(Y_{n-i},Z_{n-i+1}), P_{2i}=(Y_{n-i},Z_{n-i})(n-l+1\leq i\leq n).$ To prove $P_1P_2\dots P_{2n}$ is simple, it suffices to show that (1)$\frac{W_1}{X_1}\leq \frac{W_2}{X_2}\leq \dots\leq \frac{W_k}{X_k}\leq \frac{Z_l}{Y_l}\leq \frac{Z_{l-1}}{Y_{l-1}}\leq \dots\leq \frac{Z_1}{Y_1};$ (2)$\frac{W_{k-1}}{X_{k-1}}< \frac{Z_{l-1}}{Y_{l-1}}.$ (1) is easy; Suppose (2) is false, by calculation we can conclude that all $a_i$'s are equal and that all $b_i$'s are equal, contradiction. I think it's too hard for somebody to understand it if he just take a glance of it, I think it's easy to explain that we first ignore the disjoint, we just build a poly and then we change it, it's easy to understand.