## BdMO National 2012: Secondary 9

Zzzz
Posts: 172
Joined: Tue Dec 07, 2010 6:28 am
Location: 22° 48' 0" N / 89° 33' 0" E

### BdMO National 2012: Secondary 9

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.
Every logical solution to a problem has its own beauty.

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.
$\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.

itsnafi
Posts: 24
Joined: Tue Mar 20, 2012 1:16 am
Location: Dhaka(past Bogra)

### Re: BdMO National 2012: Secondary 9

itsnafi
Posts: 24
Joined: Tue Mar 20, 2012 1:16 am
Location: Dhaka(past Bogra)

### 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.

sakib.creza
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.

sakib.creza
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.

SANZEED
Posts: 550
Joined: Wed Dec 28, 2011 6:45 pm
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!}}$