Results 1 to 6 of 6

Math Help - Help with combinatorics.

  1. #1
    Newbie
    Joined
    Feb 2011
    From
    Ireland
    Posts
    16

    Help with combinatorics.

    Can somebody explain how to do these please?

    Q: Show that if 5 points are placed in a unit square then there are two points no more than 1/root2 units apart.

    and

    Q: Show that if 5 points are placed in an equilateral triangle of side length 1 unit then there are two points no more that 1/2 units apart.

    This is probably very easy, but we all have to start somewhere. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    This is related to Pigeonhole principle. In both cases pigeons are points. In the first case, holes are the four squares that you get when you connect the middles of the opposite sides of the given square. In the second case, also connect the middles of the given triangle's sides to get four small triangles.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2011
    From
    Ireland
    Posts
    16
    Ok thanks! But can you tell me where are the points supposed to be placed on the squae and the triangle?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    The idea of pigeonhole principle is that wherever the pigeons (points) are placed, there will be a hole (a small square or triangle) with more than one pigeon. Since there are four smaller figures and five points, one figure will contain at least two points (maybe on the border). So the problem reduces to proving that the maximum distance between two points in a square with side 1/2 is 1/\sqrt{2}=\sqrt{2}/2, and the maximum distance between two points in an equilateral triangle with side 1/2 is 1/2.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    778
    Hello, JoshuaJava!

    Here is a rather juvenile approach.


    Q: Show that if 5 points are placed in a unit square.
    then there are two points no more than \tfrac{1}{\sqrt{2}} units apart.

    Place four points in a square with maximum distances between them.
    . . They will be at the vertices of the square.

    Code:
    
          ♥ - - - - - ♥
          |           |
          |           |
        1 |           |
          |           |
          |           |
          ♥ - - - - - ♥
                1

    Now place a fifth point in the square,
    . . maximizing its distances from the first four points.

    Code:
    
          ♥ - - - - - ♥
          | *       * |
          |   *   *   |
        1 |     ♠     |
          |   *   *   |
          | *       * |
          ♥ - - - - - ♥
               1

    The best we do is use the center of the square.

    And we find that its distance from its neighbors is \frac{1}{\sqrt{2}}

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    @Soroban - Though you are correct in your working but I do not think it constitutes a valid proof.
    Better would be divide the original square into 4 sub-squares (each with side = 1/2). Note any two points on/inside the sub square will be =< 1/sqrt(2).

    Now use the pegion-hole principle as suggested by emakarov.
    Last edited by aman_cc; February 7th 2011 at 09:03 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 03:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 09:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 06:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 11:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 07:03 AM

Search Tags


/mathhelpforum @mathhelpforum