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 :

Optimal

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 !

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s