«
»

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

Tags: , , ,

This entry was posted on February 25, 2011 at 1:52 pm and is filed under math, theorem. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “Points on a grid”

  1. Jagadish Says:
    March 2, 2011 at 4:52 am | Reply

    Since there are more than n points, some two points share the same row (column). Let their columns (rows) be c1 (r1) and c2 (r2). If there is any point in c1 (r1) or c2 (r2) apart from these two we are done; else remove columns c1 and c2 and rows r1 and r2. This removes exactly 4 points. Now we have an n-2 x n-2 grid with 2(n-2) – 1 points.

  2. Saurabh Joshi Says:
    March 2, 2011 at 5:46 am | Reply

    True. But I somehow have a feeling that there should be some simpler proof not involving induction.

  3. Pratik Poddar Says:
    March 14, 2011 at 6:36 pm | Reply

    Solution not using induction.

    You have 2n-1 points. Sort these points according to their x-co-ordinates (n possible values). If some points have same x-value, we group them into a group.
    What is the number of groups of size>=0? Its n.
    What is the maximum number of groups of size 1? Its n-1

    At least n elements have at least one partner with them on x-axis.

    Now do the same for y co-ordinates. At least n elements have at least one partner with them on y-axis.

    In 2n-1 element set, these two sets cannot be disjoint. So, there is at least one element with partners from both y-co-ordinates and x-co-ordinates. Hence, we have at least one right triangle. 🙂

    This was simple, I think!

    http://www.pratikpoddarcse.blogspot.com

Leave a comment