Thread: 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!

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.

Ok thanks! But can you tell me where are the points supposed to be placed on the squae and the triangle?

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 , and the maximum distance between two points in an equilateral triangle with side 1/2 is 1/2.

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

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