2
$\begingroup$

There is a puzzle:

Find a finite set of points with the following property:
1. Points are placed in space (not on a single plane)
2. If you take any pair of points A and B there are different points C and D such that AB segment is parallel to CD and doesn't lay on the same line.

Known solution to this problem:

Take a regular hexagon. Obviously it satisfies rule #2. Now take another hexagon, which has common center O with the first one. This will be the required set of points.

Indeed, if you take A and B on the same hexagon then there are C and D on it; if you take A and B on different hexagons then take C symmetric to A relatively to O and D symmetric to B relatively to O, obviously ABCDO are in the same plane and AB || CD.

I asked myself a question: what if we want to minimise number of points in the set? What is the minimal number to build a set with the described properties? The given solution allows you to get a set with

6+6-2 = 10 points. Just make 2 points of the hexagons coincide.

my question is: Can you find a smaller number points or to prove that this is not possible?

$\endgroup$
  • 1
    $\begingroup$ I think a picture might help others understand your solution/problem easier. $\endgroup$ – Mark N May 8 '15 at 17:33
  • $\begingroup$ @klm123 You have created a new tag 'optimum'. Could please add a tag wiki to differentiate it from 'optimization'? $\endgroup$ – ghosts_in_the_code May 10 '15 at 17:06
  • $\begingroup$ @ghosts_in_the_code, thank you, I think that tag is good here. $\endgroup$ – klm123 May 10 '15 at 17:13
  • $\begingroup$ Why the 'not on a plane' restriction, out of curiosity? The plane seems the natural setting for this problem. (And the six vertices of a regular hexagon are likely the solution there - you can probably use the classic case of Ramsey's theorem to show that 5 don't work) $\endgroup$ – Steven Stadnicki May 12 '15 at 3:39
  • $\begingroup$ @StevenStadnicki, em, just because... that would be another problem. and too simple. And the solution there is obviously optimal. and why ask about it here... $\endgroup$ – klm123 May 12 '15 at 7:27
1
$\begingroup$

Incomplete proof for 10 being the minimum, please feel free to add/modify it.

There must exist a plane with 4 points. Let us assume that no plane has more than 4 points.

The quad formed on our starting plane is ABCD. Now AC needs a parallel. So we need EF||AC on the same plane as AC but not BD. Now EFAC becomes a quad. We can use the same logic to show that we need another 2 points, so on till infinity.

Therefore, there must exist a plane with more than 4 points. Suppose the plane has 5 points. We notice that we still need 2 more points not on the plane because 2 diagonals will have no parallels within the plane. Using earlier logic, we can eliminate this case as well.

Suppose now, that the plane has 6 points. We soon realise that we can use a regular hexagon such that there is no dependence on parallels outside the plane. So 6 is valid. However, by rule we need a point outside the plane. This point creates 6 new lines, one with each corner, that require parallels.

$\endgroup$
  • $\begingroup$ Why ABCD is quad? it can be any trapeze $\endgroup$ – klm123 May 12 '15 at 7:29
  • $\begingroup$ @klm123 Quad is short for quadrilateral - it means any four-sided planar shape. $\endgroup$ – not my job May 22 '15 at 1:55
0
$\begingroup$

I think the OP's solution is the minimal.

For any regular polygon > 4, you can match any line between 2 points.

To get into 3D, why not just take a polygon and put it into 3 dimensions? Let's try a pentagon. If you rotate about 1 point, you have symmetry on 2 planes, but the slopes off the square base doesn't have parallel lines. If we rotate about 2 points, you end up with some points creating a rectangle that you can't match its diagonals.

Ok, let's try a hexagon. If you rotate the shape on opposite points, you end up with a flattened cube with 2 pyramids on top. Let's have the tips be top and bottom. Any line from either tip will fall on one of the planes of the original hexagon, which we know has a match. For the edges along the middle, opposite edges are part of the same hexagon, so any pairs there have matches. So, the last pairs are from one edge to another, each of those pairs has a match on the opposite face.

Pretty crappy pictures, but here:
enter image description here enter image description here
For the first, the purple area is the part of the red hex behind the blue hex. The second image shows the polyhedron created by all the points.

$\endgroup$
  • $\begingroup$ Can I get a picture please? $\endgroup$ – Mark N May 8 '15 at 20:05
  • $\begingroup$ There is at least one another solution with 10 points, which doesn't involve rotation of polygons... $\endgroup$ – klm123 May 8 '15 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.