BdMO National 2012: Secondary 9

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
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

Unread post by Zzzz » Sun Feb 12, 2012 8:55 am

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.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

User avatar
nafistiham
Posts: 829
Joined: Mon Oct 17, 2011 3:56 pm
Location: 24.758613,90.400161
Contact:

Re: BdMO National 2012: Secondary 9

Unread post by nafistiham » Fri Feb 17, 2012 3:37 pm

(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.
Introduction:
Nafis Tiham
CSE Dept. SUST -HSC 14'
http://www.facebook.com/nafistiham
nafistiham@gmail

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

Re: BdMO National 2012: Secondary 9

Unread post by itsnafi » Sun Mar 25, 2012 9:59 pm

what about using pigeon hole?

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

Re: BdMO National 2012: Secondary 9

Unread post by itsnafi » Sun Mar 25, 2012 10:20 pm

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

Unread post by sakib.creza » Mon Jan 21, 2013 10:31 am

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

Unread post by sakib.creza » Tue Jan 22, 2013 6:46 am

Oh! sorry I found exactly how. I was considering 1 column and 1row equal to 1 colrow.

User avatar
SANZEED
Posts: 550
Joined: Wed Dec 28, 2011 6:45 pm
Location: Mymensingh, Bangladesh

Re: BdMO National 2012: Secondary 9

Unread post by SANZEED » Sun Jan 26, 2014 6:58 pm

(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.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

Post Reply