Problem 9:
Consider a $n×n$ grid of points. Prove that no matter how we choose $2n-1$ points from these, there will always be a right triangle with vertices among these $2n-1$ points.
BdMO National 2012: Secondary 9
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)
- nafistiham
- Posts:829
- Joined:Mon Oct 17, 2011 3:56 pm
- Location:24.758613,90.400161
- Contact:
Re: BdMO National 2012: Secondary 9
(i am describing my way in short, if someone assures me that the logic behind it is not totally wrong, i'll post the full solution.otherwise, there is no logic behind writing it fully)
firstly, we can prove that, the best way to take $2n-2$ points is to take the points of two sides of the excepting one corner point, now, no matter which is taken as the $2n-1^{th}$ point, it will make a right angled triangle.
i did it by induction.
firstly, we can prove that, the best way to take $2n-2$ points is to take the points of two sides of the excepting one corner point, now, no matter which is taken as the $2n-1^{th}$ point, it will make a right angled triangle.
i did it by induction.
\[\sum_{k=0}^{n-1}e^{\frac{2 \pi i k}{n}}=0\]
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
Re: BdMO National 2012: Secondary 9
what about using pigeon hole?
Re: BdMO National 2012: Secondary 9
Let's think like this....
1 point(no matter how we choose) will use 1 column & 1 row(2 colrows).now let's choose another point from 1 colrow that has been used already by the 1st point.2nd point will use another new colrow.now if we choose any point from any of these 2 used colrows,a right triangle will be definitely made.let's avoid choosing the 3rd point.
here every 2 points use 3 colrows.so,2n-1 points will use 3(2n-1)/2 colrows.but we've total 2n colrows.
For n>1, always 3(2n-1)/2>2n.
So,we've to choose point(s) from used colrow & right triangle will be made.
1 point(no matter how we choose) will use 1 column & 1 row(2 colrows).now let's choose another point from 1 colrow that has been used already by the 1st point.2nd point will use another new colrow.now if we choose any point from any of these 2 used colrows,a right triangle will be definitely made.let's avoid choosing the 3rd point.
here every 2 points use 3 colrows.so,2n-1 points will use 3(2n-1)/2 colrows.but we've total 2n colrows.
For n>1, always 3(2n-1)/2>2n.
So,we've to choose point(s) from used colrow & right triangle will be made.
-
- Posts:26
- Joined:Sat Nov 03, 2012 6:36 am
Re: BdMO National 2012: Secondary 9
itsnafi, how r there 2n col-rows. I can only find n col-rows.
-
- Posts:26
- Joined:Sat Nov 03, 2012 6:36 am
Re: BdMO National 2012: Secondary 9
Oh! sorry I found exactly how. I was considering 1 column and 1row equal to 1 colrow.
Re: BdMO National 2012: Secondary 9
(I am posting this via a friend of mine)
Let us colour the points which are chosen. Now call a point "Row happy" if it is the only coloured point in its row.
Similarly define "Column happy" points.
Now by the pigeon-hole principal, at least one of the rows contain more than $1$ point. So the number of maximum "Row happy" points is $n-1$. Similarly, the maximum number of "Column happy" points is $n-1$.
Note that there exists a right triangle if there is a point that is neither "Row happy" nor "Column happy", Now from our argument the maximum number of points when every point is either "Row happy" or "Column happy" is $n-1+n-1=2n-2$. So,if we choose $2n-1$ points,there must be a point that is neither "Row happy" nor "Column happy" and there will be a right triangle too.
Let us colour the points which are chosen. Now call a point "Row happy" if it is the only coloured point in its row.
Similarly define "Column happy" points.
Now by the pigeon-hole principal, at least one of the rows contain more than $1$ point. So the number of maximum "Row happy" points is $n-1$. Similarly, the maximum number of "Column happy" points is $n-1$.
Note that there exists a right triangle if there is a point that is neither "Row happy" nor "Column happy", Now from our argument the maximum number of points when every point is either "Row happy" or "Column happy" is $n-1+n-1=2n-2$. So,if we choose $2n-1$ points,there must be a point that is neither "Row happy" nor "Column happy" and there will be a right triangle too.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$