BdMO Online Forum

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 )

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 )

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 )

In that case feel free to share your solution here.

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 )

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 )

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 .

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