I'm posting one puzzle, riddle, math, or statistical problem a day. Try to answer each one and post your answers in the comments section. I'll post the answer the next day. Even if you have the same answer as someone else, feel free to put up your answer, too!
Friday, October 12, 2007
Connecting the Dots
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.
Well, not sure how to write this into an equation (or as an answer) but, if n was: 1, 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)
The problem as stated is too broad, it needs clarification. If 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:
n!/(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:
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.
I'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.
Leave your answer or, if you want to post a question of your own, send me an e-mail. Look in the about section to find my e-mail address. If it's new, I'll post it soon.
Please don't leave spam or 'Awesome blog, come visit mine' messages. I'll delete them soon after.
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.