Monday, December 25, 2006

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

20 Comments:

Anonymous panda said...

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.

10:20 AM, January 13, 2007  
Blogger dandy said...

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

2:20 PM, February 07, 2007  
Anonymous Anonymous said...

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.

6:14 PM, March 15, 2007  
Blogger SUMI said...

"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? :)

6:14 PM, May 02, 2007  
Blogger SUMI said...

oh and this is the same as n choose 2 (n C 2) or n(n-1) /2

7:27 PM, May 02, 2007  
Blogger SUMI said...

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...

7:39 PM, May 02, 2007  
Anonymous Karthik R said...

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.

11:59 AM, June 13, 2007  
Anonymous Karthik R said...

Ah, a small mistake in the answer. For 6 computers, it is 15 conversations.

12:02 PM, June 13, 2007  
Blogger Prash said...

It grows out as a fibonacci series.

5:05 PM, September 10, 2007  
Blogger Anup said...

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.

10:05 AM, May 28, 2008  
Blogger Anup said...

This comment has been removed by the author.

10:06 AM, May 28, 2008  
Blogger Amit Sarda said...

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)

10:43 AM, June 03, 2009  
Blogger 晡晡 said...

看看blog調整心情,又要來繼續工作,大家加油.........................

8:58 PM, January 31, 2010  
Blogger 東京 said...

想像是什麼並不重要,想像能做什麼才重要..............................

3:50 AM, February 25, 2010  
Blogger Dr. Voldo said...

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)

3:57 PM, April 15, 2010  
Blogger Dr. Voldo said...

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)

3:58 PM, April 15, 2010  
Blogger trinadh said...

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.

5:33 AM, July 02, 2010  
Blogger Phyllis said...

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!

6:18 PM, November 29, 2010  
Blogger raja gunasekaran said...

its 2n-2

9:08 AM, July 16, 2013  
Blogger raja gunasekaran said...

sorry it should be 2n-3

9:10 AM, July 16, 2013  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home