In a $n \times n$ grid show that if you choose any $2n-1$ points at least $3$ points would make a right triangle.
Source: May be bdmo (actually it said it bdmo 2012 secondary 8 but when i checked it was not )
Again PHP
-
- Posts:194
- Joined:Sat Jan 02, 2021 9:28 pm
Hmm..Hammer...Treat everything as nail
-
- Posts:194
- Joined:Sat Jan 02, 2021 9:28 pm
Re: Again PHP
Update: i have got close to proving it through induction but the arguments are not as pretty as pigeonhole principal...
(it included deleting horizontal and vertical lines but no pretty PHP )
(it included deleting horizontal and vertical lines but no pretty PHP )
Hmm..Hammer...Treat everything as nail
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: Again PHP
In that case feel free to share your solution here.Asif Hossain wrote: ↑Thu Feb 25, 2021 3:57 pmUpdate: i have got close to proving it through induction but the arguments are not as pretty as pigeonhole principal...
(it included deleting horizontal and vertical lines but no pretty PHP )
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
-
- Posts:194
- Joined:Sat Jan 02, 2021 9:28 pm
Re: Again PHP
It is not complete and i also couldn't write it formally. But the main idea was add a extra row and column and you have to at least 3 points from the extra portion due to induction hypothesis then you have to delete some columns to avoid right triangle. then i stucked..(ik that it must be that the smaller rectangular portions must have a right triangle but i couldn't prove it...)(i doubt that it can be solved by some pretty php but i couldn't have insight on it so i gave up )Anindya Biswas wrote: ↑Mon Mar 08, 2021 2:52 amIn that case feel free to share your solution here.Asif Hossain wrote: ↑Thu Feb 25, 2021 3:57 pmUpdate: i have got close to proving it through induction but the arguments are not as pretty as pigeonhole principal...
(it included deleting horizontal and vertical lines but no pretty PHP )
Hmm..Hammer...Treat everything as nail
Re: Again PHP
well how can it satisfy n=2 ? I think we can select exactly n+1 points maximum that wont make a right triangle . hence for all n> 2 , 2n-1>n+1 . and so I think its done .
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: Again PHP
It is possible to choose $n+1$ points without making a triangle
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann