sketch: consider the graph with vertex set $\mathcal S$ starting with no edges; add all the triangles (i.e. their sides) to graph by nondecreasing order of area; any triangle decreasing the number of connected components is beautiful, and there are at least $\tfrac 12 (n-1)$ of these

A problem by Aleksandar Ivanov (Bulgaria). His solution is as follows. Partition the set of points into two sets $A,B.$ Among all triangles with vertices in both $A$ and $B$ pick one with minimum area. This is a beautiful triangle. This is the key observation. Now, start with a set $A$ of only one point and $B$ has $n-1$ points. Take a beautiful triangle $XYZ$ and move those of its vertices (at most $2$) that are in $B,$ from $B$ to $A$. Do it as long as there are still vertices in $B.$ It can be done at least $(n-1)/2$ times, so you find at least $(n-1)/2$ distinct beautiful triangles. Remark. Actually, the original problem Aleksandar proposed was to find the minimum number of beautiful triangles.

Arbitrarily draw two edges from each beautiful triangle. If there are fewer than $\tfrac12(n-1)$ beautiful triangles, then the resulting graph has $n$ vertices and fewer than $n-1$ edges, so it is not connected. Hence the $n$ points may be partitioned into two nonempty sets $A$ and $B$ so that no edge is drawn between a vertex in $A$ and a vertex in $B$. However the triangle of minimal area with vertices in both sets is beautiful, and two of its edges go between $A$ and $B$, so one of these two edges must have been drawn, contradiction.

Just another comment. This problem is not combinatorial geometry, because it is not related to geometry at all. One can generalize it as follows. The set $S$ of $n$ points is given as in the original statement. Let $f : S_3\to \mathbb{R}$ be a function defined on the set $S_3$ of all subsets of $S$ with exactly $3$ elements. We call a "triangle" $\{x,y,z\}\in S_3$ nice for the pair $\{x,y\}$ if $f(\{x,y,z\})\le f(\{x,y,w\})$ for all $w\ne x,y.$ In the same way we define what is a beautiful triangle. Then there are at least $(n-1)/2$ beautiful triangles. The fact that the area is used in order to define the term "beautiful" is of absolutely no importance. Moreover, in the above definition the fact that $\{x,y,z\}$ is a min (max) is also not important. It's enough $\{x,y,z\}$ be in some sense distinguishable among other triples $\{x,y,w\}$ in that context. What I think is that if the problem was given in this general way, it would have been solved by many more contestants.

I used to think RMM 2023/2 was a tragedy, but I now realize that it is a comedy.

Main Lemma: Consider any partition of $\mathcal{S}$ into disjoint, nonempty subsets $P$ and $Q$. Call a triangle mixed if it has at least one vertex from $P$ and at least one vertex from $Q$. Then there exists a beautiful mixed triangle. Proof: Take a mixed triangle $\triangle ABC$ with minimal area. Without loss of generality, assume $A \in P$, $B \in Q$ and $C \in P$. Then $\triangle ABC$ is nice for $AB$, since replacing $C$ with any other point keeps the triangle mixed, so doing so cannot decrease the area by minimality. By the same logic, $\triangle ABC$ is nice for $BC$ as well, so $\triangle ABC$ is beautiful, as desired. $\square$ Now use the following algorithm: Let $X$ initially consist of a single arbitrary point in $\mathcal{S}$, and let $Y = \mathcal{S} \setminus X$, so $X$ and $Y$ always form a partition of $\mathcal{S}$. Then, repeatedly select a beautiful triangle $t$ mixed with respect to the current sets $X$ and $Y$, and move the vertices of $t$ that were in $Y$ to $X$. Repeat until $Y$ is empty. Each step consumes at most two elements of $Y$, and generates a new beautiful triangle (since a new point in $Y$ is involved). Since there are $n-1$ elements in $Y$ in the beginning, this can happen at least $\frac{n-1}{2}$ times, giving this many beautiful triangles, as desired.

dgrozev wrote: The fact that the area is used in order to define the term "beautiful" is of absolutely no importance. And here I had been staring at the solutions wondering where on earth "area" was used! Glad to see I'm not just crazy...

v_Enhance wrote: dgrozev wrote: The fact that the area is used in order to define the term "beautiful" is of absolutely no importance. And here I had been staring at the solutions wondering where on earth "area" was used! Glad to see I'm not just crazy... Please note that the use of "area" in this version of the problem is not due to the author, as it is the case that the PSC wanted to make the problem easier compared to the original submission (and yeah, there was not much thought of changing the problem substantially and that's fine with me, accidents happen!). The original proposal was for odd $n$ and to find the minimum number of beautiful triangles (the construction is explained in the official solutions аnd geometrically it does rely on the notion of area, PSC have also added such for even $n$ there), so the author is certainly not to be blamed.

Some really strong contestants I talked to (myself included) said they thought they were missing some purely geometric insight and were going in that direction the entire time of the contest. Very interesting decision by the PSC.

I don't think someone blames the author for this nice problem. Especially me! The fact that the notion of "area" is only used to distinguish between triangles is even more appealing to me. What PSC did was actually two things 1) they gave the answer to the contestants 2) they freed the contestants for the more tedious task of finding an example of $n$ points with $(n-1)/2$ beautiful triangles. This was certainly the routine part of the problem. So, PSC made the problem easier. The task of the contestants is to solve the problem. A complaint like: "I expected some pure geometric insight to be applied" is an opinion that I respect, because I expected it too, but it does not make the problem worse. Exactly the opposite.

This was not necessarily a complaint, just an observation. I don't think the decision was bad (although I can't help but be a little salty since I didn't solve it), and I would love to hear more opinions on this. It is a really fun topic to discuss!

dgrozev wrote: Partition the set of points into two sets $A,B$. Among all triangles with vertices in both $A$ and $B$ pick one with minimum area. This is a beautiful triangle. Here is a nice way to motivate this claim, observed by the approach of BGR5 (@nikiliverpool4) during the contest. Observe that for any point $A \in \mathcal{S}$ the triangle $AXY$ with minimal area $(X, Y \in \mathcal{S})$ is beautiful, as it is nice for $AX$ and $AY$. (It now follows that there are at least $\left\lfloor \frac{n}{3} \right\rfloor$ beautiful triangles, which is worth 3/7 for the problem, but we'll do better.) Call this triangle special for $A$. If it turns out that no triangle is special for all of its three vertices, then there would be at least $\left\lfloor \frac{n}{2} \right\rfloor$ beautiful triangles and we shall be done. What to do if otherwise? So suppose there is such a triangle, say $ABC$. Then in order to somehow use $A$, $B$ or $C$, you have nothing else to do but consider the triangle $A_1X_1Y_1$ with minimal area where $A_1 \in \{A,B,C\}$ and $X_1, Y_1 \in \mathcal{S} \setminus \{A,B,C\}$ - it is beautiful. (If you only allow, say $A_1 = A$, then you may not get a beautiful triangle.) Finally, observe that the latter observation does not depend on the left part being with 3 points, i.e. it works in general.

No blame from me either, just a lighthearted comment I jotted on my phone

以 $\mathcal{S}$ 的 ${n}$ 个点为顶点$,$ 若某个 ${}{\triangle ABC}$ 为美丽的$,$ 将其相对"好的"两条边连边$($若三条边均为"好的"则取两条相连$),$ 得到一个 ${n}$ 阶图 $G(V,E).$ 若某个图中美丽三角形的个数小于 $\frac{n-1}2,$ 则 ${G}$ 中边数小于 $2\cdot\frac {n-1}2=n-1,$ 因此 ${G}$ 不连通$.$ 设 ${G}$ 有两个不连通的子图 $X,Y.$ 取一个三角形$,$ 且 $X,Y$ 中均至少有一个顶点$.$ 取这些三角形中面积最小的一个$,$ 设为 $\triangle{ABC},$ 不妨设 $A\in X,B,C\in Y.$ 则 $\triangle {ABC}$ 对边 $AB,AC$ 是"好的"$.$ 因此 ${G}$ 包含 $AB,AC$ 中至少 ${1}$ 条边$,$ 矛盾$!.$ 因此至少有 $\frac{n-1}2$ 个美丽三角形$.\blacksquare$

IAmTheHazard wrote: I used to think RMM 2023/2 was a tragedy, but I now realize that it is a comedy. Benefits of having bad memory: being able to redo this problem after reading its solution and forgetting it. Although I'm not really sure if it was worth it for this particular problem... Clearly the triangle with smallest area (if there are ties break arbitrarily) is beautiful. Color its vertices red, and color all the other points in $\mathcal{S}$ black. Now repeatedly perform the following algorithm. Consider the triangle $\mathcal{T}$ with minimal area that has both red and black vertices. I claim that it is beautiful. Indeed, if $\mathcal{T}$ has exactly one red vertex, then it's nice for the edges from this red vertex, otherwise, it's nice for the edges from its unique black vertex. Then color all vertices of $\mathcal{T}$ to red and repeat. Since we color at most $2$ points red in each iteration and start with $3$ red points, it follows that when this algorithm terminates (i.e. every point is red) we have found at least $\tfrac{1}{2}(n-3)+1$ beautiful triangles, as desired. $\blacksquare$