## triangle in a square has area less than 1/2

For discussing Olympiad Level Combinatorics problems
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

### triangle in a square has area less than 1/2

Take a square of length \$n\$ and choose \$(n+1)^2\$ points inside the square. Prove that, you can choose some \$3\$ points so that the triangle made by them has an area at most \$\dfrac12\$.
One one thing is neutral in the universe, that is \$0\$.

nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

### Re: triangle in a square has area less than 1/2

I think \$(n+1)^2\$ is more than sufficient, we just need \$n^2+1\$.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

SN.Pushpita
Posts: 11
Joined: Thu Aug 10, 2017 1:44 pm

### Re: triangle in a square has area less than 1/2

Masum wrote:
Sun Feb 08, 2015 10:57 pm
Take a square of length \$n\$ and choose \$(n+1)^2\$ points inside the square. Prove that, you can choose some \$3\$ points so that the triangle made by them has an area at most \$\dfrac12\$.
It is a nice problem.
Sketch of solution:
Take the convex hull of points . Denote it by H.Apparently,the hull has area at most n^2 and perimeter 4n.Now suppose that hull has k points on its boundary. So definitely n^2+2n+1-k points in the interior of the hull.Now triangulate the hull .This use exactly 2 (n^2+2n)-k triangles. So one has area at most n^2/{2 (n^2+2n)-k} .Next there must exist 2 consecutive edges such that if side length r a,b then a+b/2 <= 4n/k
So this triangle will have area at most 8n^2/k^2
SO some triangle will have area at most minimum of the above mentioned 2 triangles. The first one is increasing wrt k while the 2nd one is decreasing.So that area will be maximized when both will be equal.Then k=4n
The rest is just calculation Last edited by SN.Pushpita on Tue Feb 20, 2018 11:39 am, edited 3 times in total.

SN.Pushpita
Posts: 11
Joined: Thu Aug 10, 2017 1:44 pm

### Re: triangle in a square has area less than 1/2

Silly me.Couldn't latex for shortage of time :"(

samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

### Re: triangle in a square has area less than 1/2

SN.Pushpita wrote:
Mon Feb 19, 2018 12:59 pm
Masum wrote:
Sun Feb 08, 2015 10:57 pm
Take a square of length \$n\$ and choose \$(n+1)^2\$ points inside the square. Prove that, you can choose some \$3\$ points so that the triangle made by them has an area at most \$\dfrac12\$.
It is a nice problem.
Sketch of solution:
Take the convex hull of points H. Apparently,the hull has area at most n^2 and perimeter 4n.Now suppose that hull has k points on its boundary .Now triangulate the hull .This use exactly 2 (n^2+2n)-k triangles. So one has area at most n^2/{2 (n^2+2n)-k} .Next there must exist 2 consecutive edges such that if side length r a,b then a+b/2 <= 4n/k
So this triangle will have area at most 8n^2/k^2
SO some triangle will have area at most minimum of the above mentioned 2 triangles. The first one is increasing wrt k while the 2nd one is decreasing.So that area will be maximized when both will be equal.Then k=4n
The rest is just calculation I didn't uderstand the first line of the skectch of solution.

SN.Pushpita
Posts: 11
Joined: Thu Aug 10, 2017 1:44 pm

### Re: triangle in a square has area less than 1/2

samiul_samin wrote:
Mon Feb 19, 2018 2:27 pm
SN.Pushpita wrote:
Mon Feb 19, 2018 12:59 pm
Masum wrote:
Sun Feb 08, 2015 10:57 pm
Take a square of length \$n\$ and choose \$(n+1)^2\$ points inside the square. Prove that, you can choose some \$3\$ points so that the triangle made by them has an area at most \$\dfrac12\$.
It is a nice problem.
Sketch of solution:
Take the convex hull of points H. Apparently,the hull has area at most n^2 and perimeter 4n.Now suppose that hull has k points on its boundary .Now triangulate the hull .This use exactly 2 (n^2+2n)-k triangles. So one has area at most n^2/{2 (n^2+2n)-k} .Next there must exist 2 consecutive edges such that if side length r a,b then a+b/2 <= 4n/k
So this triangle will have area at most 8n^2/k^2
SO some triangle will have area at most minimum of the above mentioned 2 triangles. The first one is increasing wrt k while the 2nd one is decreasing.So that area will be maximized when both will be equal.Then k=4n
The rest is just calculation I didn't uderstand the first line of the skectch of solution.
Well ,read about convex hull then. I have also edited some lines to increase understability .