Hi /sci/,
First time poster. I'm a /g/ man normally.
There was a question in a book I was reading about how many single-lines would be needed to connect each computer in a 5 computer network to every other computer. I was wondering if there was an easy and way to express this relationship that holds true at any scale.
Here are 3 images showing my work. I'm wondering what type of math this is, and what education level it's consistent with.
>>8474856
I'm also wondering can this be proven at a large scale (eg. 9000 points) without having to draw out the network or use these formulas?
>>8474856
There are n computers.
each computer has to connect to n-1 computers so total non-unique connections will be n^2 - n.
We can take this as the upper bound, but there is actually just one optimization that needs to be done and you only need to consider:
A connected to B is equivalent to B connected to A which means that in a system with k non-unique connections, there are k/2 non-unique connections
So we get the formula: (n^2 - n)/2
For a moment I was going to say this was graph theory but it really is just traditional modelling algebra and if you are generous maybe elementary graph theory.
>>8474856
>tfw says hes a g man
>>8474877
>there are k/2 non-unique connections
I meant k/2 unique connections.
Analyzing my logic I actually feel it is pretty weak so I will take this as an informed guess and prove by induction.
For the case n=2 we get (4-2)/2 = 1 which is exactly what you would expect.
So suppose now you have n computers and our formula (n^2 - n)/2 holds true for that arbitrary n. We add an extra computer and connect it to every other computer, yielding n new connections.
(n^2 - n)/2 + n/1 =
(n^2 - n + 2n)/2 =
(n^2 + n)/2
now lets consider the expression
(n+1)^2 = n^2 + 2n + 1 so
n^2 + n = (n+1)^2 - n - 1 =
(n+1)^2 - (n+1)
Substituting into the equation we get
((n+1)^2 - (n+1))/2
Confirming the equations holds for n+1 and thus, by induction, this formula holds true for any number of connections.
>>8474866
Yes, just use the formula I just proved. With this argument you know it is true, even if you use it for 999999999999999999999999 computers.
>>8474856
Are you retarded? It's clearly the (number of computers)*(number of computers- 1 "of other computer to connect to")/(2 since you double count A to B and B to A)
Which is the same as (n choose 2) aka the number of different pairs of computers
> I'm wondering what type of math this is
Combinatorics and/or Graph Theory
>>8474914
Can you please direct me to a test to see if I am retarded? Thank you
>>8474938
>Thank you, that's what I was looking for. Really appreciate the thorough explanation
No problem. At least your thread is about math and not Trump, weed, IQ or pop philosophy.
If you want to learn about how to perform this kind of analysis I'd recommend reading a discrete math book. It is really light and really intuitive. I suggest the book by Don Knuth.
>>8474954
Thank you very much. My library doesn't have it, but I found it online
>>8474954
Also MIT seems to have a well regarded MOOC on "elementary discrete mathematics for computer science and engineering"