Results 1 to 8 of 8

Math Help - a pigeonhole problem

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    15

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Intersesting problem. Thanks

    Hint - divide the bigger triangle into 4 smaller trainge (each area = 0.25 and similar to the bigger one)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    15
    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
    Attached Thumbnails Attached Thumbnails a pigeonhole problem-sixpintriangle.jpg  
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    @ 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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2010
    Posts
    15
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    677
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    677
    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)
    Last edited by aman_cc; October 10th 2010 at 10:17 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Apr 2009
    Posts
    677
    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 20th 2011, 03:46 PM
  2. Pigeonhole Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 15th 2009, 04:31 PM
  3. pigeonhole problem ... ASAP please
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 29th 2008, 11:03 PM
  4. Pigeonhole problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: October 18th 2008, 02:41 PM
  5. A pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 12th 2007, 10:22 AM

Search Tags


/mathhelpforum @mathhelpforum