# Always some right angle or the other

Q : Given an $n\times n$ grid and a set of at least $2n-1$ marked points on it, prove that you always end up with a right angle.

Proof : You can see that this number is optimal because of the following picture :

Fred’s very cute solution :

Let $S$ denote the set of marked points. We say a point $s\in S$ has a horizontal neighbour if you can find a $t(\neq s)\in S$ such that $s,t$ lie on one horizontal line on the grid. Similarly define when a point $s\in S$ has a vertical neighbour.

Now there are $n$ rows, so atmost $n-1$ points don’t have horizontal neighbours. Since there are $|S|=2n+r\geq 2n-1$ where $-1\leq r\leq n^2-2n$ marked points, there are atleast $|S|-(n-1)=(2n+r)+1-n=n+r+1\geq n$ points which DO have horizontal neighbours. Let $H$ denote the set of marked points with horizontal neighbours, so $|H|\geq n+r+1\geq n$.

Play a similar game and conclude that there are atleast $|S|+1-n=n+r+1\geq n$ points which DO have vertical neighbours. Let $V$ denote the set of marked points having vertical neighbours. So $|V|\geq n+r+1\geq n$.

Since $|S|=2n+r$ and $|V|+|H|=2n+2r+2$ and $2n+2r+2>2n+r$ because $r>-2$, $V\cap H\neq \emptyset$. So there is a point which has a horizontal AND a vertical neighbour and hence you get a right triangle !