Maths Olympiad Prep

Track / Stage 7 / 265 of 300 #1665 of 1964

Problem 1665

National olympiad second round; IMO P1/P4
Geometry Difficulty 7.6 Prove it

a1,a2,⋯ ,an,b1,b2,⋯ ,bna_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n are 2n2n positive real numbers such that a1,a2,⋯ ,ana_1,a_2,\cdots ,a_n aren't all equal. And assume that we can divide a1,a2,⋯ ,ana_1,a_2,\cdots ,a_n into two subsets with equal sums.similarly b1,b2,⋯ ,bnb_1,b_2,\cdots ,b_n have these two conditions. Prove that there exist a simple 2n2n-gon with sides a1,a2,⋯ ,an,b1,b2,⋯ ,bna_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 a1,a2,⋯ ,ana_1,a_2,\cdots ,a_n and the lengths of vertical sides are among b1,b2,⋯ ,bnb_1,b_2,\cdots ,b_n.(simple polygon is a polygon such that it doesn't intersect itself)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Divide the sequences: Given the sequences {ai}1≤i≤n \{a_i\}_{1 \leq i \leq n} and {bi}1≤i≤n \{b_i\}_{1 \leq i \leq n} , we can divide them into two subsets each with equal sums. Specifically, we divide {ai} \{a_i\} into {xi}1≤i≤k \{x_i\}_{1 \leq i \leq k} and {yi}1≤i≤n−k \{y_i\}_{1 \leq i \leq n-k} such that:
∑i=1kxi=∑i=1n−kyi \sum_{i=1}^{k} x_i = \sum_{i=1}^{n-k} y_i
Similarly, we divide {bi} \{b_i\} into {zi}1≤i≤l \{z_i\}_{1 \leq i \leq l} and {wi}1≤i≤n−l \{w_i\}_{1 \leq i \leq n-l} such that:
∑i=1lzi=∑i=1n−lwi \sum_{i=1}^{l} z_i = \sum_{i=1}^{n-l} w_i

2. Order the subsets: Arrange the elements in each subset in non-increasing or non-decreasing order:
x1≥x2≥⋯≥xk,y1≤y2≤⋯≤yn−k x_1 \geq x_2 \geq \dots \geq x_k, \quad y_1 \leq y_2 \leq \dots \leq y_{n-k}
z1≥z2≥⋯≥zl,w1≤w2≤⋯≤wn−l z_1 \geq z_2 \geq \dots \geq z_l, \quad w_1 \leq w_2 \leq \dots \leq w_{n-l}

3. Define cumulative sums: Define the cumulative sums for each subset:
Xj=∑i=1jxi,Yj=∑i=1jyi X_j = \sum_{i=1}^{j} x_i, \quad Y_j = \sum_{i=1}^{j} y_i
Zj=∑i=1jzi,Wj=∑i=1jwi Z_j = \sum_{i=1}^{j} z_i, \quad W_j = \sum_{i=1}^{j} w_i

4. Construct the polygon: Construct a 2n2n-polygon P1P2…P2nP_1P_2 \dots P_{2n} with vertices defined as follows:
P2i−1=(Xi,Wi−1),P2i=(Xi,Wi)for 1≤i≤k P_{2i-1} = (X_i, W_{i-1}), \quad P_{2i} = (X_i, W_i) \quad \text{for } 1 \leq i \leq k
P2i−1=(Yn−i,Wi−1),P2i=(Yn−i,Wi)for k+1≤i≤n−l P_{2i-1} = (Y_{n-i}, W_{i-1}), \quad P_{2i} = (Y_{n-i}, W_i) \quad \text{for } k+1 \leq i \leq n-l
P2i−1=(Yn−i,Zn−i+1),P2i=(Yn−i,Zn−i)for n−l+1≤i≤n P_{2i-1} = (Y_{n-i}, Z_{n-i+1}), \quad P_{2i} = (Y_{n-i}, Z_{n-i}) \quad \text{for } n-l+1 \leq i \leq n

5. Prove the polygon is simple: To show that the polygon P1P2…P2nP_1P_2 \dots P_{2n} is simple (i.e., it does not intersect itself), we need to verify the following conditions:
W1X1≤W2X2≤⋯≤WkXk≤ZlYl≤Zl−1Yl−1≤⋯≤Z1Y1 \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}
Wk−1Xk−1<Zl−1Yl−1 \frac{W_{k-1}}{X_{k-1}} < \frac{Z_{l-1}}{Y_{l-1}}

6. Verify condition (1): The first condition is straightforward to verify given the ordering of the subsets and the properties of the cumulative sums.

7. Verify condition (2): Suppose the second condition is false. By calculation, this would imply that all aia_i's are equal and all bib_i's are equal, which contradicts the given condition that a1,a2,…,ana_1, a_2, \dots, a_n are not all equal.

Thus, the conditions are satisfied, and the constructed polygon is simple.

■\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.