For any two convex polygons $P_1$ and $P_2$ with mutually distinct vertices, denote by $f(P_1, P_2)$ the total number of their vertices that lie on a side of the other polygon. For each positive integer $n \ge 4$, determine \[ \max \{ f(P_1, P_2) ~ | ~ P_1 ~ \text{and} ~ P_2 ~ \text{are convex} ~ n \text{-gons} \}. \](We say that a polygon is convex if all its internal angles are strictly less than $180^\circ$.) Josef Tkadlec (Czech Republic)
Problem
Source: 2021 Czech-Polish-Slovak Match, P3
Tags:
05.05.2022 13:27
The answer is $[\frac{4n}{3}]$ . the example can be constructed easily . Just fix $P_1$ and put $P_2$ in such a way that alternatively , there is two of three vertices of $P_i$ on $P_{i+1}$ ($i$ is considered mod 2) Now , we shall somehow give an order to the $2n$ vertices of $P_1 , P_2$.Consider a point which is not on any of lines passing through two of $2n$ vertices , name this point $A$. Now consider all $2n$ lines connecting $A$ and vertices of $P_1,P_2$.We can consider the $2n$ vertices ,in clockwise order , so we have the order we wanted. Let's show that for any three consecutive vertices in this clockwise order , at most two of them satisfies the condition (name this points good). Assume by contrary. clearly this three vertices cannot belong to the same polygon. If two of them belonged to $P_1$(or $P_2$ , there's no difference between this two case) , then if there were like $ 1 ,1 , 2$ (exactly in this order) ,then there is another $1$ in the right side of $2$ so the $1$'s are all collinear which is impossible. If it was like $1,2,1$ , these three points should be collinear and So there is another $2$ in the right of $2,1$ and another $2$ in the left of $12$ , So three of $2$s are collinear which in contradiction . So at most two of any three consecutive vertices satisfy the condition. Summing up , the answer would be $[\frac{4n}{3}]$.