NOTE: Looking for a hint,not the whole solution.
BdMO 2012 Nationals Secondary
Consider a $n×n$ grid of points. Prove that no matter how we choose $2n-1$ points from these, there will always be a right triangle with vertices among these $2n-1$ points.
If we are trying to get a right triangle,we need a point which has one more point in the row that it is in and one more point in the column that it is in.Now,we have to prove that it is impossible to pick $2n-1$ points from $n\times n$ grid without having a point that satisfies the above property.I think we can somehow use the Pigeonhole Principle to prove that.
If we pick $n$ points from the same row/column,then picking one more point would result in a right triangle.If we pick only one point from each column and row(resulting in $n$ chosen points),then picking one more point would give us a right triangle.
I of course did not mention all possible cases in the last paragraph,and quite frankly,I am not sure if listing out the cases would help here.A nudge in the correct direction will be appreciated.
EDIT: I also tried induction but with no luck.