Page **1** of **1**

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

Posted: **Sun Feb 08, 2015 10:57 pm**

by **Masum**

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$.

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

Posted: **Sun Feb 15, 2015 9:51 pm**

by **nayel**

I think $(n+1)^2$ is more than sufficient, we just need $n^2+1$.

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

Posted: **Mon Feb 19, 2018 12:59 pm**

by **SN.Pushpita**

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

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

Posted: **Mon Feb 19, 2018 1:00 pm**

by **SN.Pushpita**

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

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

Posted: **Mon Feb 19, 2018 2:27 pm**

by **samiul_samin**

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.

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

Posted: **Tue Feb 20, 2018 11:32 am**

by **SN.Pushpita**

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 .