There are $n^2$ segments in the plane (read walls), no two of which are parallel or intersecting. Prove that there are at least $n$ points in the plane such that no two of them see each other (meaning there is a wall separating them).
Problem
Source: 2023 Serbia TST Problem 6
Tags: geometry, combinatorial geometry, walls
24.05.2023 19:18
Can someone post the official solution?
24.05.2023 21:21
I didn't come up with this solution, maybe someone smarter can shed some light on the intricacies of this problem. Basically, you want to introduce a coordinate system that isn't parallel to any of the segments (you want slopes to be defined). Also like make the segments short enough that their projections are non-intersecting or something. Then take all the left endpoints of the walls. Consider their height and the slope of their segment. Applying $\textit{Erdos-Szekeres}$ on these two parameters to obtain that there is a sequence of $n$ endpoints such that both the height and slope are increasing/decreasing. Taking $n$ points just below/above these segments will work. This means that $(n-1)^2+1$ segments is enough.
24.05.2023 22:09
I would love to see a proof that doesn't quote Erdos-Szekeres. Surely it can be avoided using other global arguments?
28.05.2023 02:53
The Erdos-Szekeres idea could be reminded especially if one has seen ICMC 2020/4 https://icmathscomp.org/files/2019-2020/2019-2020_Round_Two_Solutions_20200708.pdf See Solution 2
28.05.2023 17:23
Solved with AdhityaMV, Siddharth03, starchan For each segment $S_1, S_2, \cdots, S_{n^2}$, pick a point $P_i$ on it such that all of them have distinct $x$ coordinates. Reorder them by $x$-coordinate, and call them $P_1, P_2, \cdots, P_{n^2}$. Now to each $P_i$, assign the slope of the line $S_i$. By Erdos-Szekeres, since $n^2 \geqslant (n-1)^2 + 1$, we can find either an increasing-slope sequence of $n$ points or a decreasing-slope sequence. Since no two lines are parallel, they all have distinct slopes. Now, if its an increasing sequence, pick a point extremely close and below the $P_i$'s part of the increasing thing, call these $Q_i$. Suppose some $Q_i$ and $Q_j$ (with $i < j$) can see each other. Then the slope of line of $P_i$ must be greater than the slope of line $Q_iQ_j$, and the slope of line of $P_j$, which is a contradiction to the increasing condition. In the case when it's decreasing, pick points above the lines and a similar argument works. $\blacksquare$ To the above post, I think it's quite natural to want to pick a point "on" or close enough to some segments. If you look at when it's possible that two such points see each other, you see that for any two line segments, you can either choose the points just above or just below to make it work. Further, which side depends only on the relative ordering of the slopes. So all you want is a monotone sequence of slopes, and Erdos-Szekeres gives us just this