Any solutions?

I actually was about to post this problem until I saw this post, which was a weird coincidence. The problem also appears as N. 128 in Komal. We go by strong induction. Suppose for the sake of contradiction that $S$ does not have a monochromatic planar spanning tree. Consider the convex hull of the set $S$, suppose it is $v_1,...,v_m$. Now let $1 \le k\le m$ be arbitrary. Then by the induction hypothesis, $S\setminus \{v_k\}$ has a monochromatic planar spanning tree, WLOG it is blue. Then the edges $v_kv_{k+1}$ and $v_kv_{k-1}$ must both be red, otherwise we could add them to get a blue planar spanning tree for $S$ since none of the edges of the convex hull intersect other edges. So the entire convex hull must be a red cycle. The fact that adding edges from the convex hull does not "disturb anything" is important in the remaining proof. Now pick some direction to be vertical, such that no segment is vertical. Let the points from left to right be $p_1,...,p_N$. For each $1 \le i \le N-1$, let $L_i = \{p_1,...,p_i\}$ and $R_i = S\setminus L_i$. Note that $p_1$ and $p_N$ are both on the convex hull, hence $R_1$ and $L_{N-1}$ both only have blue planar spanning trees. By convention we can assume $L_1$ and $R_{N-1}$ have red planar spanning trees. Hence, initially, the color of the spanning trees is (red,blue), and it ends at (blue, red). If at some point, we have $R_j$ and $L_{j+1}$ have the same color planar spanning tree, we can just merge these trees together and no edges will cross, forming a monochromatic planar spanning tree for $S$. Now suppose at some point that $L_j$ and $R_j$ both red planar spanning trees. If for some $1\le k \le m$, $v_k$ and $v_{k+1}$ are in different sets, then we can merge the trees by adding the edge $v_kv_{k+1}$ which is red and does not affect anything since it is part of the convex hull, giving a red planar spanning tree of $S$. Since $p_1$, a vertex in the convex hull, is in $L_j$, we conclude that all the vertices in the convex hull are in $L_j$, but $p_N \in R_j$, which is a contradiction. So we cannot have a (red,red) pair at any point. But by our observations, a (red,blue) pair can only be followed by a (red, blue) pair, so we can never have the (blue,red) pair $(L_{N-1},R_{N-1})$ at the end since we start with a (red,blue) pair $(L_1,R_1)$, so we have a contradiction, as desired. Edit: Fixed typo

The following solution is totally wrong, as pointed out by dgrozev. I leave it as a reference, and as an eternal sign of my shame. test20 wrote: Pick a maximal subset $E$ of the segments so that no two segments in $E$ intersect except in their endpoints. By Euler's formula, the cardinality of $E$ equals $3N-3-c$, where $c$ denotes the number of points on the convex hull of $S$. Since $c\le N$, we conclude $|E|\ge2N-3$. At least half of the at least $2N-3$ edges in $E$ have the same color. Hence there are at least $N-1$ segments of the same color which don't intersect except in their endpoints such that no subset of them forms a polygon with positive area.

test20 wrote: Pick a maximal subset $E$ of the segments so that no two segments in $E$ intersect except in their endpoints. By Euler's formula, the cardinality of $E$ equals $3N-3-c$, where $c$ denotes the number of points on the convex hull of $S$. Since $c\le N$, we conclude $|E|\ge2N-3$. At least half of the at least $2N-3$ edges in $E$ have the same color. Hence there are at least $N-1$ segments of the same color which don't intersect except in their endpoints such that no subset of them forms a polygon with positive area. Why does the text in red hold? For example, it may happen there is a triangle with sides of the same color.

Pathological wrote: Firstly, note that if the graph of red edges is disconnected, the the graph of blue edges is connected and hence possesses a spanning tree. Hence, let's take a all $n-1$ edges of some spanning tree, that is blue WLOG. Now, we will consider the following process which we perform whenever there are two segments of our spanning tree, say $AB$ and $CD$, which intersect each other in their interiors. Now, observe that there exist two adjacent vertices among $A,C,B,D$ for which there exists a direct path among the two vertices which doesn't go through the other two of the vertices, WLOG $A$ and $C$. Then, we will swap the edges $AB, CD$ for the edges $AD, BC$. We are done since the sum of the lengths of all side present strictly decreases, and the $n-1$ edges still comprise a tree. $\square$ Why are we sure that the edges $AD, BC$ are of the same color as $AB, CD$? Furthermore, if they are of same color, it may happen $AD$ or/and $BC$ intersect another part of the tree, so the number of intersections do not decrease, but even may increase.

@above Oops, sorry you are correct that there is no way to guaranteed the monochromatic-ness. However, the second part about number of intersections is irrelevant, since I am claiming that the sum of the lengths of the chosen segments decreases, not the number of intersections .

Pathological wrote: @above ...I am claiming that the sum of the lengths of the chosen segments decreases, not the number of intersections . Ok, I see, $AD+BC<AB+CD$. A promising idea. But still, if it happens $AD$ or/and $BC$ to intersect another segments of the tree, you should add to $AD+BC$ the lengths of that other intersecting segments and finally it might be more than $AB+CD$.

Originally from Kömal N.128.