Problems from Ukrainian Authors

Let us put points on these two lines in such a way that projections of every two adjacent points from one line to another surround exactly one point on another line and there are no obtuse angles $\angle ABC$ such that $B$ lies on one line and $A,C$ on another one (clearly, we can achieve this if distances between points will be sufficiently small). It's easy to check that in this case there are exactly $\frac{1}{6}m(m+1)(2m+1)$ acute triangles.

Let us project all the points on one of the two lines and color projections of the points from one line in white and from another one in black. Then an acute triangle may be obtained only from points $A,B,C$ such that $B$ lies between $A$ and $C$ and $A$ and $C$ have the same color which is different from $B$ (but we should note that the converse is not necessarily true). We will show by induction that there are at most $1^2+2^2+\cdots +m^2=\frac{1}{6}m(m+1)(2m+1)$ such good triples if there are $2m+1$ points.

For $m=0$ the statement is obvious. Suppose that we proved it for $m-1$. Let us show that this is also true for $m$. We number the points as $A_1,A_2,\dots ,A_{2m+1}$ and consider a coloring with the largest number of such triples.

Assume that $A_1,A_{2m+1}$ have the same color (WLOG it's white). Let among the points from $A_2$ to $A_{2m}$ exactly $w$ are white and $b$ are black points. Observe that there are at most $1^2+2^2+\cdots +(m-1{)}^2$ good triples among the points from $A_2$ to $A_{2m}$, $b$ triples which contain $A_1$ and $A_{2m+1}$ and also $bw$ triples which contain exactly one point from $A_1$ and $A_{2m+1}$ (because for every pair of points of different colors, there is exactly one point from $A_1$ and $A_{2m+1}$ which will form a good triple with them). So, we have at most $1^2+2^2+\cdots +(m-1{)}^2+b(w+1)$ good triples. Observe also that $b+w=2m-1$, hence $b(w+1)\le m^2$ and there are at most $1^2+2^2+\cdots +(m-1{)}^2+m^2$ good triples and in this case the induction proceeds.

From now we will assume that $A_1$ and $A_{2m+1}$ have different colors.

Consider any two adjacent points $A_i,A_{i+1}$ such that $A_i$ is white and $A_{i+1}$ is black. Let there are $w_1$ white and $b_1$ black points among the points from $A_1$ to $A_{i-1}$, and $w_2$ white and $b_2$ black points among the points from $A_{i+2}$ to $A_{2m+1}$. Then if we swap $A_i$ and $A_{i+1}$, the number of good triples will increase by $(b_2+w_1)-(b_1+w_2)$. Since our coloring is optimal by assumption then $(b_1+w_2)\ge (b_2+w_1)$ and so $(w_1-b_1)\le (w_2-b_2)$.

WLOG $A_1$ is white and $A_{2m+1}$ is black. Let $A_k$ be the first black point and $A_l$ be the last white ($k<l$, because otherwise, we don't have good triples). Let us apply the statement above for the points $A_{k-1},A_k$: for the points to the left of them the difference (white points)–(black points) = $k-2\ge 0$ and so for the points to the right of them this is non-negative. Hence, the difference (white points)–(black points) for all the points is non-negative. On the other hand, let us apply this statement for the points $A_l,A_{l+1}$: for the points to the right of them the difference (white points)–(black points) = $-(2m+1-l-1)=l-2m\le 0$ and so for the points to the left of them this is non-positive. Hence, the difference (white points)–(black points) for all the points is non-positive. But before we showed that this difference is non-negative, so it's zero and then the number of points is even, so we got a contradiction.