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.

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