Given $n^2+1$ points on a Euclidean plane, I have to prove that there exists a monotone curve passing through at least n of these points.
My intuition pigeon hole principle has to be used to solve the problem. Now my idea is : For each given point $P_i$, define $(A_i, B_i)$, where
$A_i$=maximum number of points (including $P_i$) among the given set of points that can be joined to get an monotone increasing curve ending at $P_i$
$B_i$=maximum number of points (including $P_i$) among the given set of points that can be joined to get an monotone decreasing curve ending at $P_i$
If we assume there cannot be a monotone curve having atleast n points of the given set on it, then $A_i, B_i \leq n-1$. Hence $|\{(A_i, B_i) : i=1(1)n^2+1\}|\leq(n-1)^2$. Thus by pigeon hole principle there are two different points having same value of (A,B) that can lead to a contradiction. Now firstly, I don't know whether this approach of mine is right or not. Secondly, even if the approach is right this seems complicated. Can someone please suggest some better and efficient way to tackle the problem? Any help is highly appreciated.