You have n dots on a piece of paper. How many lines do you need to connect the n dots?

The answer to this question is pretty well known, so if you want to provide the answer, please share your explanation for everyone else.

## Friday, October 12, 2007

Subscribe to:
Post Comments (Atom)

Is the answer not "n-1"?

ReplyDeleteWell, not sure how to write this into an equation (or as an answer) but, if n was:

ReplyDelete1, there would be 0 lines connecting

2=1

3=3

4=6

5=10

6=15

The pattern is shown in the difference between the number of lines (1,2,3,4,5)

n(sub x)=n(sub x-1)!

ReplyDeleteor: (I dont know if this will come out right when posted.)

n =n !

x x-1

no, i guess not

ReplyDeleteThe problem as stated is too broad, it needs clarification.

ReplyDeleteIf we on't consider the case of colinear points, then we could say:

it is the same as finding the number of pairs from a set of objects.

Because each pair of dots define a line.

For example:

If you have 2 points A, B in a space, then you have AB and BA, or 2*1 = 2

possibilities.

If you have 3 points A, B, C in the space, then you would have:

AB, BA, AC, CA, BC, CB or 3*2 = 6 possibilities.

You may argue that AB and BA are the same, thus giving 1 possibility

Similarly, that AB=BA, BC=CB and AC=CA, thus giving you 3 possibilities.

So, we could say that the number of pairs is 1/2 the number of

possibilities.

With n=4 points, we have 4*3/2 = 6

With n points, n(n-1)/2.

But, if we consider that the points could be colinear, then the number of lines are between 1 and n(n-1)/2.

Mike, I think what you were meaning is n, non-colinear points. In order to draw lines connecting n points that meet that criterion, the number of lines you would need is:

ReplyDeleten!/(2*(n-2)!)

Basically, for each line, you're "choosing" two points, and order does not matter, so it is the general formula for "combinations" (similar to the last post, only order does matter here).

Incidentally, for our case, the above formula reduces to:

n!/(2*(n-2)!)

= (n*(n-1)*(n-2)!)/(2*(n-2!)

= n(n-1)/2

which is the same as benvitale's answer (as well as consistent with everyone else's more empirical results).

To say I'm impressed by these answers would be an understatement. As I said before, the answer is well known, but the explanations you gave were thorough.

ReplyDeleteI'm not really sorry the question was vague, though. To see so many possibilities explained and discussed helps me think things through, and I hope it does the same for everyone else who reads them.