There are $2020$ points on the coordinate plane {$A_i = (x_i, y_i):i = 1, ..., 2020$}, satisfying $$0=x_1<x_2<...<x_{2020}$$$$0=y_{2020}<y_{2019}<...<y_1$$ Let $O=(0, 0)$ be the origin, $OA_1A_2...A_{2020}$ forms a polygon $C$. Now, you want to blacken the polygon $C$. Every time you can choose a point $(x,y)$ with $x, y > 0$, and blacken the area {$(x', y'): 0\leq x' \leq x, 0\leq y' \leq y$}. However, you have to pay $xy$ dollars for doing so. Prove that you could blacken the whole polygon $C$ by using $4|C|$ dollars. Here, $|C|$ stands for the area of the polygon $C$. Proposed by me
Problem
Source: 2021 Taiwan TST Round 3 Independent Study 2-C
Tags: combinatorics, geometry
20.08.2021 21:30
Is one allowed to blacken points that are not in $C$?
20.08.2021 21:52
I think so because if not then the question implies the polygon is a collection of rectangles which is not necessarily true
20.08.2021 21:53
Hopefully I didn't misunderstand the problem
21.08.2021 02:42
p_square wrote: Is one allowed to blacken points that are not in $C$? Yes, it is.
04.10.2021 21:31
Bump this interesting problem (also the last problem unsolved in 2021 Taiwan TST XD).
05.02.2022 22:46
Bump
19.05.2022 14:15
Let me know if there is evidence to the contrary. I believe I have proven that you can blacken the whole polygon $C$ with at most $\frac{8}{3} |C|$ dollars. I think this constant is also sharp, as I have a construction that asymptotically approaches this bound.
21.05.2022 16:08
Could you please provide your proof?
11.08.2022 19:16
I have a proof draft from a while ago that I was planning to clean up with a friend of mine and post here, but it appears that this seems unlikely to happen soon and I probably won't bother making it look nice. There is a little ambiguity when the minimization process is infinite where you should approach by picking the minimal configuration that isn't totally degenerate by preventing the leftmost point from being on the axis via induction on the total number of points and ensuring the function is smooth. I forgot where I wrote the fix so it's an exercise for the reader, most of the ideas necessary should more or less be here.