Library / /76 of 397

, 2021

Geometry Difficulty 5.2 AIME, harder Prove it Taiwan

There are 2020 points $\{A_i = (x_i, y_i) : i = 1, \dots, 2020\}$ on the plane, satisfying
$\begin{aligned} 0 &= x_1 < x_2 < \dots < x_{2020}, \\ 0 &= y_{2020} < y_{2019} < \dots < y_1. \end{aligned}$
Denote $O = (0,0)$ , the origin. Sequentially construct edges $OA_1, A_1A_2, \dots, A_{2019}A_{2020}, A_{2020}O$ to form a 2021-gon $C$ . Tao wants to paint the entire region $C$ in black. On each turn, he chooses a point $(x, y)$ , pays $xy$ dollars, and paints the entire region $\{(x', y') : 0 \le x' \le x, 0 \le y' \le y\}$ in black. Prove that Tao can always paint the entire region $C$ in black while spending at most $4|C|$ dollars, where $|C|$ is the area of $C$ .

Solution

The problem can be generalized as follows: in the first quadrant, there is a continuous bounded decreasing function $f$ , and let $C$ be the region enclosed by this curve and the $x$ - and $y$ -axes. Then we can paint this region using the method described in the problem, spending at most $4|C|$ dollars. We can directly construct this painting scheme:

In the construction above, $x$ is a positive real number such that $f(x) \ge f(0)/2$ (by continuity, such an $x$ must exist). Then we have:
- Area of colored region No. 1 $\times 4 = 4x f(x) \ge x f(0) + 2x f(x) = \text{the amount required when choosing } (x, f(0)) \text{ plus choosing } (2x, f(x)).$
- Area of colored region No. 2 $\times 4 = 4x f(2x) = \text{the amount required when choosing } (4x, f(2x)).$
- Area of colored region No. 3 $\times 4 = 8x f(4x) = \text{the amount required when choosing } (8x, f(4x)).$
- And so on in this manner.

Therefore, if we choose $(x, f(0)), (2x, f(x)), (4x, f(2x)), (8x, f(4x)), \dots$ in sequence, we will necessarily paint the entire region below $f$ (that is, $C$ ) in black, and we have
$\text{the amount required to pay} \le 4 \times \text{area of colored region} \le 4 \times \text{area below } f = 4|C|$
Thus the construction is complete.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.