Problem: Suppose you have an \(n \times n\) grid. Show that for any \(2n - 1\) points chosen on the grid, there exist \(3\) points that form a right-angle triangle.

Solution: The standard solution here is to use the pigeon-hole principle.

We note that the existence of an (axis-aligned) right-angle triangle is guaranteed if there exists a point such that there exists one point in the same row (i.e. with the same y-coordinate) and another point in the same column (i.e. with the same x-coordinate).

This motivates us to try to find the number of points that share a row/column with another point. To find the minimum number of points that share a row/column with another point, we find the maximum number of points that don’t share a row/column with another point. This comes out to \(n - 1\) since we can isolate \(n-1\) points in \(n - 1\) row/columns (we can’t do \(n\) since we only have \(n\) rows and given we have \(>n\) points, one row will have more than one point.)

Therefore, the minimum number of points that share a row is \(n\). Likewise, the number of points that share a column is \(n\). Given that we have only \(2n - 1\) points, we see that there must be \(1\) point which both shares a row with another point and shares a column with another point.

Extension: Show that \(2n - 2\) points aren’t sufficient to get an (axis-aligned) right-angle triangle. Is it sufficient to get any right-angle triangle (not necessarily axis-aligned)?

Solution (Extension): If the grid is \([1,n] \times [1,n]\), consider the \(2n - 2\) points \((1,1), (1,2), \dots, (1,n-2), (1,n-1), (2,n), (3,n), \dots, (n-1,n), (n,n)\). We see that no right-angle triangle can be made (even non axis aligned).