BdMO Online Forum

Problem 9:
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.

(i am describing my way in short, if someone assures me that the logic behind it is not totally wrong, i'll post the full solution.otherwise, there is no logic behind writing it fully)

firstly, we can prove that, the best way to take $2n-2$ points is to take the points of two sides of the excepting one corner point, now, no matter which is taken as the $2n-1^{th}$ point, it will make a right angled triangle.
i did it by induction.

what about using pigeon hole?

Let's think like this....
1 point(no matter how we choose) will use 1 column & 1 row(2 colrows).now let's choose another point from 1 colrow that has been used already by the 1st point.2nd point will use another new colrow.now if we choose any point from any of these 2 used colrows,a right triangle will be definitely made.let's avoid choosing the 3rd point.
here every 2 points use 3 colrows.so,2n-1 points will use 3(2n-1)/2 colrows.but we've total 2n colrows.
For n>1, always 3(2n-1)/2>2n.
So,we've to choose point(s) from used colrow & right triangle will be made.

itsnafi, how r there 2n col-rows. I can only find n col-rows.

Oh! sorry I found exactly how. I was considering 1 column and 1row equal to 1 colrow.

(I am posting this via a friend of mine)
Let us colour the points which are chosen. Now call a point "Row happy" if it is the only coloured point in its row.
Similarly define "Column happy" points.
Now by the pigeon-hole principal, at least one of the rows contain more than $1$ point. So the number of maximum "Row happy" points is $n-1$. Similarly, the maximum number of "Column happy" points is $n-1$.
Note that there exists a right triangle if there is a point that is neither "Row happy" nor "Column happy", Now from our argument the maximum number of points when every point is either "Row happy" or "Column happy" is $n-1+n-1=2n-2$. So,if we choose $2n-1$ points,there must be a point that is neither "Row happy" nor "Column happy" and there will be a right triangle too.