a pigeonhole problem
Question: If we are given six points in a triangle of area 1, three of them form a triangle whose area is less than or equal to 0.25
I know this must be solvable by pigeonhole principle but I just can't figure out how many parts I should divide the bigger triangle into. If i make 3 buckets, it's useless. If i make 2 buckets it still doesn't help.
Any help is appreciated.
Intersesting problem. Thanks
Hint - divide the bigger triangle into 4 smaller trainge (each area = 0.25 and similar to the bigger one)
Kindly see the attached image. Do you mean something like this? (Here AB=BC , CD=DE.)
I still don't see how to place the six points here. I put 4 points in each of the smaller triangles. The 2 leftover ones are placed into two different triangles. I don't get 3 points within the same triangle to enable me to apply the pigeonhole principle :(
@ mathdigger - i made a mistake in my earlier post, so i still don't know how to solve this problem.
but i can offer some more hints, if that helps
consider parallelogram ABDF (in your figure above) - it cant have 3 points - because maximum area 3 points in a parallelogram can enclose is half (this is easy to see - as you can prove to maximize the area the points should be on the boundary and then corners)
using above we can rule out any point in BDF
so only configuration left is 2 points each in all the remaining tri-angles - this is where even i'm stuck
umm i think you made a little mistake here. The max area enclosed by 3 points in a parallelogram of area 1/2 is actually 0.25, not half. Nevertheless, i think you've pointed me in the right direction. So what we do is, we put 4 points in the 4 triangles. Then, if the 2 left over points go into the same triangle, we are done. Otherwise, there exists a parallelogram containing 3 points exactly. These will enclose an area of 0.25 at max.
yes by half i meant half of the area of the parallelogram
so u can't have any point in BDF
Which leaves us with the only possible configuration of 2 points each in BCD, ABF, FDE
and this is where i'm stuck
ok, this is getting little complicated but i guess will lead us to solution.
Now we know that if there is a parallelogram with area = 0.5 it can't enclose three points
So, let us construct such a parallelogram
move pts B and D in your figure to B` and D` such that Area(AB`D`E) = 0.5
you can do this with other line segments DF, BF as well.
so we will have quite a few partition of the trangle and hopefully we will find a contradiction
i haven't had a chance to try it completely myself - but looks promising, though a little messy
On second thoughts - it is better to have B' such that it bisects AB (and similarly with all othe points).
So we will have 16 smaller and congurent trangles to deal with (but lot of symmetry) - and may lead us to the answer. I will try it and post back - looks like we should get it with this approach (and on hindsight it doesn't look all that bad to approach this problem like this)
Yes - It works !!
Let me know if you want the solution
You need to remember only 2 rules
1. You can't have three points inside a trangle with an area = 0.25
2. You can't have three points inside a parallelogram an area = 0.5
(These are easy to prove)