How many conversations?
We have a network of 6 computers that have some pre-loaded software on them that help in conversing with other computers. A conversation means exchange of information between the 2 computers and thus a single conversation helps in both computers knowing what information is present on each of their disks. If at some point of time all the computers have something new to share with the others, then at the most how many conversations should occur between the computers until all of them have all the information? By conjecture how many such conversations should occur at the most for a 'n' connected computer network? Do not assume any relation to an actual computer network problem, hence don't apply your network protocol skills here. Its a pure combinatorics problem!Difficulty: Medium
posted by Karthik Nagaraj at
11:15 PM
18 Comments:
9 converstions for 6 computers???
solution - if a,b,c,d,e,f are 6 nodes then
a b c d e f -> ab ab cd cd ef ef (3) -> ab abcd abcd cd ef ef (1)-> ab abcdef abcd cd abcdef ef (1) -> abcdef abcdef abcdef abcdef abcdef abcdef (4)
3 +1 +1 +4 = 9
is there a shorter method???
with regards to 'n' nodes, I don't yet have a generic mathematical formula, but a generic algorithm definitely has been derived if the above solution is correct. Here i believe that you are looking for a mathematical formula. so i'll wait till thats cracked.
well i m new to this field but just trying
according to me {2(n-2)+1}
take two systems out of total n systems
n-2 systems will communicate to 1 system (say system-a)-> (n-2) conversations
this system will communicate with last system -> 1 conversation
again system-a will back communicate to (n-2) systems -> (n-2) conversations
total = 2(n-2)+1
this looks fine for smaller values too
n=2: 1
n=3: 3
n=4: 5
n=5: 7
n=6: 9
same as panda said
correct me if i m wrong
Bobach writes:
I think every PC needs to have a conversation with every other PC because of the sequential order.
Take 3 PCs - A,B,C. A and B talk and they are synchronized, but neither has the new data that was on C.
So A has to talk with C and so does B. So, for 3 PCs, we need 3 conversations.
Take 4 PCs - A,B,C,D. The required conversations are AB, AC, AD, BC, BD and CD - 6 in all.
I did the same thing up to 7 PC's and then applied Newton's Forward Difference Formula to derive the general statement.
For N computers, Newton's formula gives the formulat N(N-1)/2, For 6 nodes, you need 15 conversations.
By the way, this the number of conversations in the series (starting with 2 PCs and adding a PC) are the triangular numbers:
When N=2, conversations = 1.
3 3
4 6
5 10
6 15
7 21
Think of how bowling pins are arranged in a triangle on a traditional, American bowling alley. There is 1 pin if you
consider only the first row, 3 pins in the first 2 rows, 6 pins in the first 3 rows, and 10 pins in the first 4 rows.
Maybe this is so wrong that Karthik will chime in, we miss his comments.
"at the most"? that means a computer cannot communicate the status of another computer it has already had a conversation with, I assume. It seems then that the answer would be the same as the number of edges in a fully connected (undirected) graph. So (n-1) + (n-2) + (n-3) ... + 0? Or summation {i: 1 to n } (n-i) ?
so for two nodes (computers), 2-1 + 2-2 = 1 conversation (edge)
for 3: 3-1 + 3-2 + 3-3 = 3 conversations (edges)
and so on ?
or am I way off? :)
oh and this is the same as n choose 2 (n C 2) or n(n-1) /2
hehe I still want to say some thing - instead of "at the most" if u were to optimize it (for no. of conversations) you cud even have a liner solution instead of O(n^2). If opne guy talks to everyone else and then broadcasts, or if you ordered the conversations chronologically so that the infromation is bubbled up to the last guy in one pass and then trasmitted back all the way from last guy to first guy in the second pass. Both the alternatives would lead to an O(2n) or O(n) solution in terms of no. of conversations, however timewise it is longer since the conversations happen serially. So it really depends whether you want to optimize based on time of no. of conversations I guess...
I think Bobach's got it, but I didnt get into so many formulas.
Every computer has to be connected, so considering each computer to be a vertex of a graph, we need a complete graph to solve the problem.
So, given 6 computers, I will have to use 12 connections.
For a complete graph with n vertices, number of edges is n(n-1)/2
So, I guess the answer is n(n-1)/2 conversations, for n computers.
Ah, a small mistake in the answer. For 6 computers, it is 15 conversations.
It grows out as a fibonacci series.
I think it is 2*n-3 .. it works for 3,4 and for greater numbers we can prove by contradiction and mathematical induction...
Note : there is atleast one comp which communicates twice ... so the difference b/w n+1 case to n case should be atleast 2, by just collapsing this node.
This comment has been removed by the author.
i think the solution could be simpler.
assume 4 PC's.
assume that we start with A.
let A get updated data from all the PC's, so its AB, AC, AD. ie 3.
next, all the other PC get updated info from A.
so its again
AB, AC and AD ie 3.
so in total 6.
so on so forth.
i think this is the shortest path (although maybe not the fastest)
Damn, I was too late.
Sir, would you be kind enough to write a demonstration to your last post`s solution? I found it out somewhere else, solved it without much difficulty but i am still unable to (not quite sure how to say that in english) transform that solution into pure algebra.. to demonstrate it properly, see?
id be happy to hear from you, my e-mail is rm.ferrari@hotmail.com
(sorry to post it here, i was unable to find an e-mail adress)
Damn, I was too late.
Sir, would you be kind enough to write a demonstration to your last post`s solution? I found it out somewhere else, solved it without much difficulty but i am still unable to (not quite sure how to say that in english) transform that solution into pure algebra.. to demonstrate it properly, see?
Id be happy to hear from you, my e-mail is rm.ferrari@hotmail.com
(sorry to post it here, i was unable to find an e-mail adress)
Lets assume that there are N nodes.
Lets make it as: N = 4 + K
Now N1 (node1) shares the information with:
N5 - 1 conn.n (N1 has data of N5)
N6 - 2 conn.s (N1 has data of N5, N6)
...
Nn - K conn.s (N1 has data of N5,..Nn)
Now N1 has data of all nodes from N5 to Nn.
N1 - N2
N3 - N4
N1 - N3
N2 - N4
With the above 4 calls.
N1, N2, N3, N4 has complete data.
Now again make K conn.s from N1:
(to share complete data)
N5 - 1 conn.
N6 - 2 conn.s
...
Nn - K conn.s
Now all the nodes will have complete data.
So total connections = K + 4 + K = 2K + 4 = 2(N-4) + 4 = 2N - 4.
Total connections required = 2n -4.
Reason why we choose N = K + 4
-------------------------------
Within the first 4 nodes total data can be shared within 4 connections.
N1 - N2
N1 - N3
N1 - N4 (N1,N4 has info of all)
N1 - N2
N1 - N3
In normal case it takes 5 as shown above.
N1 - N2
N3 - N4
N1 - N3
N2 - N4
Only 4 connections are required in this.
So to optimize this "1" connection, N is chosen as K + 4.
Hope this helps.
Let me know if any one has any other optimized solution or other way of simple explanation.
Is it really necessary to use a formula? I just used Notepad. Here's what I came up with:
Six computers: A B C D E F
Conversations between the computers: AB AC AD AE AF BC BD BE BF CD CE CF DE DF EF
15 conversations
Yes, it's just a simple combinatorics problem! I just hope that those conversations don't happen in real life all at the same time. A problem in the computer network might occur due to information overload. In such case, an IT consulting service must be called. Nice puzzle, Karthik!
its 2n-2
sorry it should be 2n-3
Post a Comment
Subscribe to Post Comments [Atom]
<< Home