## 5 point problem

Posted by Chris on March 14, 2011 – 5:30 pm

Five points are arranged in space so that no more than three at a time can have a single plane surface pass through them. Each group of three points has an infinite plane pass through them. What is the maximum number of lines at which these planes may intersect?

March 14th, 2011 at 7:07 pm

The maximum number of lines where the planes may intersect is 9. The shape I have constructed for this is made from two tetrahedron, which share a side.

March 14th, 2011 at 11:49 pm

With five points as described you can construct ten different planes (5!/3! = 10).

Each pair of planes intersect to form one line.

So that gives 10!/2! = 1,814,400 lines.

That’s quite a tangle!

March 14th, 2011 at 11:54 pm

Let me just rephrase that . . .

Each pair of the ten planes intersect to form one line.

So that gives 9+8+7+6+5+4+3+2+1 = 45 lines.

Now a bit less of a tangle!

March 15th, 2011 at 4:05 am

45 lines. 5C2 = 10 planes and 10C2 = 45 lines.

March 15th, 2011 at 7:43 am

um…Wiz…

first of all, 5!/3! = 10?

no, 5!/3! = (5*4*3*2*1)/(3*2*1) = 5*4*(3/3)*(2/2)*(1/1) = 5*4*1*1*1 = 20

However…I agree that there are 6+3+1=10 different planes with only 3 of the 5 points being passed through.

And I get that there are 9+8+7+6+5+4+3+2+1 = 45 lines made by any 2 interesecting planes.

March 15th, 2011 at 9:41 am

I say 10 planes with 15 intersect lines.

3 points create 1 plane with 0 lines.

4 points create 4 planes with 6 lines. Tetrahedron layout

5 points create 10 planes with 45 lines. 2 Tetrahedron layout with shared side.

45 lines contains many duplicate lines though. Not sure how many unique lines there are

March 15th, 2011 at 11:10 am

I’d say 10 lines.

Each pair of planes intersects in one line… but some pairs may intersect in the same line.

For example, the abc and bcd planes intersect in bc. But so do bcd and bce.

… actually, it turns out that the planes as such are unimportant, and that we are only looking at the number of lines defined by 5 points. You need 2 points to define a line. And among 5 points, there are exactly 10 pairings (4+3+2+1 = 10).

So, the answer is: 10 lines…

March 15th, 2011 at 11:15 am

I guess I was only looking at it from the theoretical perscpective, and not keeping real space in mind.

If you are doing the double-tetrahedron layout, There would only be 3 planes per tetrahedron (6 total), plus the one shared plane. However, you cannot assume that the 9 “edges” of the enclosed space are the only lines possible. These are simply the most ‘inward’ lines, creating the closed block.

Since there are no parallel planes, each of the planes that do not intersect on the block will intersect out in space. I say that because the problem statement points out that these are infinite planes.

Now, what happens when 3 planes intersect along the same line? this happens on all 3 edges between the 2 tetrahedrons. I assume these are considered 1 line, rather than 2. Because of this, I would be inclined to investigate more “shapes” to be sure we attain the maximum number of lines as asked for.

March 15th, 2011 at 11:25 am

Thanks, DP. Yes, I should have said 5!/(3!2!) or 5C2 = 10 planes.

That’s why I flunked maths at uni.

I’ll stand by 45 lines as the final answer.

March 15th, 2011 at 12:43 pm

Oh I forgot something…

There are 3 more planes not mentioned in the double-tetrahedron method. they would be “captured” inside the common shape. They are defined by the two points opposite each other, and one of the 3 “shared” points. This would bring the total to 10 planes. 3 inner (just described), 6 outter, and 1 “shared”.

This makes me believe that 45 is more correct than i first believed. maybe the theoretical approach wasn’t so wrong to do in the first place.

March 15th, 2011 at 12:52 pm

DOH! now I know I’m losing it.

For one, I am wrong to say “captured”, even if in quotes. I simple meant the difined triangle would be inside the main shape.

But the big thing: Any time 3 planes intersect we should subtract 2 lines. say we have planes A, B, and C. The lines we could potentilly have are AB, AC, & BC. However, if those three lines are 1, then we subtract 2. (3-2=1)

I see this happening at least 4 times. Once on each edge where the 2 tetrahedrons meet, as well as the ‘axis’ down the middle of the 2 (from tip-to-tip) as defined by the 3 planes I mentioned in the above post.

4*2=8

so my new answer is 45-8= 37 lines. until my next revelation..

March 15th, 2011 at 1:58 pm

Can’t see why there’s any need to define this problem in terms of geometic shapes, like double tetrahedra.

To me that just adds more complications and possibly introduces unnecessary constraints.

We have ten planes going every which way, i.e. none parallel, so the MAXIMUM number of lines formed (which is what the question is asking) would be from the first plane intersecting the planes 2 to 10, the second intersecting 3 to 10, and so on, hence 45 lines.

This is just another way of saying that I don’t understand DP’s solution, hence my “dumbing down” approach.

March 15th, 2011 at 2:17 pm

John 24 has the answer that I agree with (15 lines). I’ll post my reasoning later – if someone doesn’t beat me to it.

The planes are not independent. You’d need 30 points to define 10 independent planes.

Also, there are C(5,2) = 10 pairs of points; so there must be at least 10 lines.

In my opinion, visualising it as two tetrahedra is the best way to see it. Personally, I started with one tetrahedron, then I added the fifth point.

March 15th, 2011 at 4:02 pm

I think the answer is 25, but I don’t visualize any tetrahedrons, maybe because I hate geometry and love Combinatorics. First of all, there are C(5,2)=10 lines that contain exactly 2 of the 5 points. Each plane goes through 3 points, so we have two cases:

Case 1: The intersecting planes have 2 of the 5 points in common – then the intersection line is one of the above 10.

Case 2: The intersection planes have only 1 point in common. Let us denote the points by A,B,C,D,E and let A be the common point. Each plane contain A and two more points, so without loss of generality consider the plane that contains both A and B. We have 3 cases for the plane: ABC, ABD, ABE. We will show that each of the three cases leads to a different intersection line. Indeed, assume that ABC intersects ADE in the line through AL and so does ABD with ACE. Then ABCL lie on a single plane and so does ABDL. But ABL doesn’t lie on a line, so there exists a unique plane through ABL, leading to the conclusion that all the points ABCDL lie on a single plane – contradiction with the statement that ABCD are not co-planar. Hence, we have 3 different intersection lines that contain only A. Analogously, there are 3 different intersection lines that contain each of the other 4 points. Two lines of different groups cannot coincide, since such a line should contain 2 points from the given 5 – a contradiction. Therefore this case gives rise to 15 intersection lines, which added to the previous 10 give 25 in total…

March 15th, 2011 at 6:16 pm

I goofed. I think it’s 19. I’ll read slavy’s comment before posting again.

March 15th, 2011 at 6:24 pm

25 is my final answer (unless I go back to 19). Now I really will read what slavy wrote.

March 16th, 2011 at 2:57 am

‘I think the answer is 25′ 4:02 pm

‘I goofed. I think it’s 19. I’ll read slavy’s comment before posting again.’ 6:16 pm

*oh shit he has 25 as the answer*

‘25 is my final answer (unless I go back to 19). Now I really will read what slavy wrote.’ 6:24 pm

March 16th, 2011 at 7:03 am

Jan, you missed ‘John 24 has the answer that I agree with (15 lines)’.

25 is my final answer. Slavy’s solution is excellent.

I’ll call the intersection of two planes a “double” and of 3 planes a “triple”.

I’ll use the double tetrahedron to explain it. I visualise the first tetrahedron as having vertices A,B,C and D, with A being at the top (like a pyramid). We then have 4 planes: ABC,ABD,ACD and BCD. They intersect at 6 lines: AB,AC,AD,BC,BD and CD. Those 6 lines are doubles (so far).

Add the point E. Place this as an approximate mirror image of the point E, on the other side of the plane BCD. We now get the planes EBC,EBD,ECD. That gives the three lines EB,EC and ED (doubles) and triples the lines BC,BD and CD.

Add the plane ABE. It triples the lines AB and BE. ABE intersects CD at the point B’ and creates three double lines BB’ (on BCD), AB’ (on ACD) and EB’ (on CDE).

Add the plane ACE. It triples the lines AC and CE. ACE intersects BD at C’, creating the three doubles: CC’ (on BCD), AC’ (on ABD) and EC’ (on BDE). It also creates the double line AE by intersecting with ABE).

Add the plane ADE. It triples the lines AD and AE. ADE intersects BC at D’, creating the three doubles: DD’ (on BCD), AD’ (on ABC), ED’ (on BCE), and triples AE.

Finally plane ABC intersects CDE and BDE at some place outside the double tetrahedron. Similarly ABD intersects CDE and BCE, and ACD intersects BCE and BDE, again outside the double tetrahedron. That’s 6 more doubles. In fact the lines will pass through the points B,C and D (two lines through each).

We have 10 planes: ABC,ABD,ABE,ACD,ACE,ADE,BCD,BCE,BDE,CDE.

We have 10 triple lines: AB,AC,AD,AE,BC,BD,BE,CD,CE,DE.

We have 15 double lines: AB’,BB’,EB’, AC’,CC’,EC’, AD’,DD’,ED’ plus the 6 that I haven’t named.

Note: A triple could be considered as 3 doubles (i.e. 3 pairs of planes). So we could count the 10 triples as 30 doubles, giving a total of 45 doubles.

March 16th, 2011 at 7:34 am

ah ha. I agree with you Chris. I was working toward that answer with my post on subtracting 2 lines from the 45 total everytime you have 3 planes intersecting. I hadn’t yet got to where those newly found inner planes intersect the shell of the double tetrahedron. Those provide for another 6 lines that are created by 3 intersecting planes. 6*2=12 more lines to subtract. combine that with the 8 mentioned in post 11 gets me 45-8-12= 25 lines maximum. I think that will be my final answer.

March 16th, 2011 at 8:17 am

I like the idea of a double tetrahedron because it provides the easiest shape to visualize. This object has 6 exterior planes and 4 interior planes (1 is the common base of the two tetrahedrons and the other 3 contain the point of each tetrahedron not on the base and a single base point)

A B C are the base points D E are the end points.

Each plane can and will intersect with all other planes with 45 unique combinations 10C2. Of these 45 combinations we have 6 duplicated lines AD AE BD BE CD CE and 4 triplicated lines AB BC CA DE. 45 – 6 – 4 * 2 = 31 lines.

31 lines is my new answer!

March 16th, 2011 at 8:20 am

Hi DP. I think that you’d be wise to make 25 your final answer

I kept on failing to notice the 6 “external” lines. That’s why I thought it was 19. When I realised that the “triples” were equivalent to three doubles, I then got 10*3 + 9 = 39. I realised that this was 6 short of the conjectured 45 lines – that forced the penny to drop.

March 16th, 2011 at 8:24 am

Sorry for the 2nd post so soon.

After reading Chris’, Slavy’s and DP’s post I realize I missed my 6 doubles were actually triples when using the inner planes. So 25 lines is indeed correct.

What happens if the 5th point is within our initial tetrahedron?

March 16th, 2011 at 8:26 am

Hi John 24. There are 10 duplicated (I’ve called them triple)lines. Each triple is virtually equivalent to 3 doubles. Imagine one of the 3 planes being moved a very small amount in the direction of it’s perpendicular, then the triple line becomes three doubles. So 45 – 3*10 = 15 real double lines.

I’m sticking with 25 (slavy’s solution is the clincher).

March 16th, 2011 at 9:03 am

Hi John 24. Sorry, my last post crossed with yours.

It doesn’t matter if the fifth point is inside. If your brain is up to it (mine can only just cope ) you can deform the figure by continuously moving point E from outside the first tetrahedron to inside it.

March 16th, 2011 at 11:03 am

Well that was a fun one. Good stuff Chris.

March 16th, 2011 at 11:53 am

This may be an easier way of looking at it:

I originally said 45 lines (well, second attempt) in post # 3.

Then, as Chris pointed out in post 13, the planes are not independent. I’d overlooked this.

In fact each line is shared between three planes. E.g. line AB is shared with planes ABC, ABD and ABE.

Since each line is duplicated twice and since there are ten lines (AB, AC, AD, AE, BC, BD, BE, CD, CE, DE) then 20 of our original 45 lines are duplicates, so we end up with 25.

So, I fall into line (!) with the final consensus that others have reached.

I also agree with DP, this was a good one.

March 16th, 2011 at 2:43 pm

Just to clarify my previous post . . .

When I said each line is shared between three planes I was referring only to the the lines between the original five starting points, not the additional lines formed when the planes intersect elsewhere.

I share Slavy’s dislike of geometry so I’m pleased to offer a non-geometric solution (if it’s right), with not a tetrahedron in sight.

March 16th, 2011 at 2:47 pm

I’m a twit. This was so easy to do. I’ve been out for the last four hours and so Wiz has beat me to it.

For n points there are C(n,2) dot pairs. Each dot pair has n-2 planes passing through it. So each of those lines is really C(n-2,2) lines. There are C(n,3) planes and the max number of intersections is therefore C(C(n,3),2). So the number of unique lines is C(C(n,3),2) – C(n,2)*(C(n-2,2) -1)

n = 4 => C(4,2) – C(4,2)*(C(2,2) -1) = 6 – 6(0) = 6

n = 5 => C(10,2) – C(5,2)*(C(3,2) -1) = 45 – 10*(3-1) = 45-20 = 25

n = 6 => C(20,2) – C(6,2)*(C(4,2) -1) = 190 – 15*(6-1) = 115

n = 7 => 406, n = 8 => 1148, n = 9 => 2766, n = 10 => 5925, n = 11 => 11605

March 16th, 2011 at 4:00 pm

Hi Wiz, essentially your solution is the same as mine, but you didn’t bother to prove that all the other lines are non-duplicate. This is where my post gets lengthier and uglier.

Hi Chris, your formula is not true in general! For 6 points it is still valid, I agree. However, it is harder to show that all the intersection lines, apart from those that connect 2 of the given points. For n>8 we already have a problem, because we can easily have the three planes (1,2,3) (4,5,6) and (7,8,9) to intersect in the same line, which we have counted as 3 different lines in the formula.

March 16th, 2011 at 4:02 pm

The second sentence in the second paragraph of the previous post is incomplete. It should have been: “However, it is harder to show that all the intersection lines, apart from those that connect 2 of the given points, appear only once.”

March 16th, 2011 at 4:42 pm

Hi slavy. I agree the formula is not true in general. But the question is for the maximum number of lines => no two planes are parallel and if you do get other lines that are more than two planes intersecting, then one of the original points need to be shifted. So e.g. we can’t have all the points in one plane => no lines (or is that a line at infinity?)

March 16th, 2011 at 4:57 pm

Hi Chris. Yes, two parallel planes intersect in a line through infinity. I didn’t read the problem carefully, so I assumed we are looking for the exact number of intersecting lines with given n points. If you just want to give an upper bound for the quantity, then I agree with the formula

March 16th, 2011 at 5:04 pm

Hi slavy. Phew! (mops brow), I thought I had missed something amazing about 3D space.

Strangely, when I set this problem, I thought that the so-called Euler formula V + F – E = 2 was going to crop up.

I have also tried (not hard and not successfully) to pose the dual problem involving how many points you get given 5 (or n) planes.