Q : Given an grid and a set of at least 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 denote the set of marked points. We say a point has a horizontal neighbour if you can find a such that lie on one horizontal line on the grid. Similarly define when a point has a vertical neighbour.
Now there are rows, so atmost points don’t have horizontal neighbours. Since there are where marked points, there are atleast points which DO have horizontal neighbours. Let denote the set of marked points with horizontal neighbours, so .
Play a similar game and conclude that there are atleast points which DO have vertical neighbours. Let denote the set of marked points having vertical neighbours. So .
Since and and because , . So there is a point which has a horizontal AND a vertical neighbour and hence you get a right triangle !