Again PHP

For discussing Olympiad Level Combinatorics problems
Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm
Again PHP

Unread post by Asif Hossain » Mon Feb 22, 2021 10:47 am

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 :?: )
Hmm..Hammer...Treat everything as nail

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Again PHP

Unread post by Asif Hossain » Thu Feb 25, 2021 3:57 pm

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 :x :x )
Hmm..Hammer...Treat everything as nail

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Again PHP

Unread post by Anindya Biswas » Mon Mar 08, 2021 2:52 am

Asif Hossain wrote:
Thu Feb 25, 2021 3:57 pm
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 :x :x )
In that case feel free to share your solution here.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Again PHP

Unread post by Asif Hossain » Mon Mar 08, 2021 11:30 am

Anindya Biswas wrote:
Mon Mar 08, 2021 2:52 am
Asif Hossain wrote:
Thu Feb 25, 2021 3:57 pm
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 :x :x )
In that case feel free to share your solution here.
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 :cry: )
Hmm..Hammer...Treat everything as nail

User avatar
Zafar
Posts:10
Joined:Thu Dec 03, 2020 8:57 pm
Location:Dhaka , Bangladesh

Re: Again PHP

Unread post by Zafar » Thu Mar 11, 2021 1:00 am

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 .

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Again PHP

Unread post by Anindya Biswas » Fri Mar 12, 2021 7:23 pm

Zafar wrote:
Thu Mar 11, 2021 1:00 am
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 .
It is possible to choose $n+1$ points without making a triangle :roll:
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply