Choosing $2n-1$ points from $n\times n$ grid such that $3$ points always form a right triangle

Question

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.

Answer 1

Here is a hint: try picking a pair of points in the same horizontal line.

Note that $2n-2$ points can be arranged without a triangle by filling the left column and the bottom row, but missing the corner.

Further hint: When you have two points in the same horizontal line, which must exist when $2n-1\gt n$ i.e. $n\gt 1$ - and no right-angled triangle - there can be no other points in the two columns containing those points. You can delete the two columns, taking out two points, and leaving a rectangular arrangement with no right-angled triangle. Can you see how to use a similar argument in the rectangle, which would recover a smaller square arrangement?