Points on a grid

Hi,

This is again one of the question that tejas faced in the CMI entrance exam.

Problem : Given an nxn grid. You choose 2n-1 points randomly ( each with different co-ordinates on the grid ). Prove that there will be three points amongst these 2n-1 point forming a right-angle triangle.

Solution :

It is easy to see that if we prove that it always have to be the case that there will be a point sharing a column with one point and a row with another point we are done. Looks like good old pigeon hole principle (php) should come to the rescue. Unfortunately, I could not come up with a solution using php.

I used mathematical induction to come up with a proof. And I agree with many other people who say that it does not give much insight into the problem.  Anyways, here it goes.

I am going to prove a general claim.

Claim : If you choose m+n-1 points from an mxn grid, there will be three points forming a right angle triangle.

Base case : 2×2 grid ( does not make sense when m or n is 1 ). This is trivial because we have to choose 3 points.

Also, 2xn is also trivial. We have n+1 points. Using php it is easy to see that there will be two points on the same row and two points on the same column. Because there are only two rows, it has to form a triangle. Similar argument goes for mx2 grid.

Assume that the claim is true for any m-1xn-1 grid.

Now,

(1) choose a point p at (x,y) which does not share either a row or column with any other point.  Remove the column and row denoted by x and y. Now we have m-1Xn-1 grid with m+n-2 (= (m-1) + (n-1) – 1  + 1) points to choose from. Follows from induction hypothesis.

(2) choose a point p at (x,y) which shares the column x ( or row y) with only one another point p1. If p also share a row(or column) with some other point p2, we are done. If not, remove column x and row y. m-1xn-1 grid with m+n-3 = (m-1 +n-1 -1) points to choose from. Follows from induction hypothesis.

(3) There are points p1…pk in the same row ( or column ). One can see that there can not be a point p in any of the column of p1…pk. Hence, remove all columns of p1…pk and the row in question. Now, grid is m-1 X n-k with m+n-1-k ( = m-1 + n-k -1 + 1 ) points to choose from. Follows from the induction hypothesis.

I know that there must be extremely simple proof for this. Arrgh, unable to find it :(.

–Saurabh Joshi

Puzzle : A number game

Well,

This is comparatively a simple puzzle with a nice observation. Given to me by tejas, who in turn, faced it in an entrance exam of CMI.

Problem : You are given integers from 1…2n. You are supposed to divide it in two sub sequence A and B such that, A and B both are of the same size n. A is monotonically increasing and B is monotonically decreasing. Prove that,

for any two such sequences .

Solution : A very simple observation and you have the solution. Let,  . So here is what you do. The moment you observe that A[i] > B[i] for some i, you swap the elements. So the element at A[i] is now in B[i] and vice versa. Thus, you can make sure that set A has all and only elements from 1…n and B has all and only elements from n+1….2n. Note, that the difference is taken over the absolute value, hence swapping does not change it. Now we know that difference between summation of elements of B and A is .

Neat, isn’t it?

–Saurabh Joshi