Printable View
All of n elderly dons initially know 1 (different) item of gossip. There are n items of gossip in total. One don can telephone another don and, during the telephone call, each will reveal all the gossip they know so far to the other.
What is the minimum number of telephone calls required so that all the dons know all n items of gossip?
(Yep, I'm back from university. The course is great everyone. Good to see the board is still up and running with some familiar names around :))
n = 1 -> 0 calls (hey, 0 is plural?)
n = 2 -> 1 call
n = 3 -> 3 calls
n = 4 -> 5 calls (I'm seeing a pattern :) )
a(1 to 4) = 1
a(1) and a(2) = 2
a(3) and a(2) = 3
a(4) and a(3) = 4
a(1) and a(3) = 4
a(2) and a(3) = 4
n = 5 -> 7
a(1 to 5) = 1
a(1) and a(2) = 2
a(2) and a(3) = 3
a(3) and a(4) = 4
a(4) and a(5) = 5
a(1) and a(5) = 5
a(2) and a(5) = 5
a(3) and a(5) = 5
total = 2(n-2)+1
Unless there's a better way?
Just wondering, what does the a(x) bit mean?
Other than that, the first part i get the same.
I'm "putting the old people in an array" called A
Yup, well done. :)
For 4 people, only 4 calls are necessary.
a,b,c,d are the dons.
a knows gossip #1
b knows gossip #2
c knows gossip #3
d knows gossip #4
a calls b...(1)
c calls d...(2)
a knows gossip #1,2
b knows gossip #2,1
c knows gossip #3,4
d knows gossip #4,3
a calls c...(3)
b calls d...(4)
a knows gossip #1,2,3,4
b knows gossip #2,1,4,3
c knows gossip #3,4,1,2
d knows gossip #4,3,2,1
=> 4 calls, not 5
So, to find the least calls needed, i think you do this.
For N dons, find the smallest X such that 2^X >= N
This is calls per person.
Multiply this by N(total calls) and divide by 2 (each call counted twice-two people per call)
Using this you get:
N_X_NX/2
1_0___0
2_1___1
3_2___3
4_2___4
5_4__10
I now realise that for N=5, X=3, but then NX/2 isn't an integer. I gotta just think it through a bit more.
Hmm. Good point.
I'm afraid I don't actually know the answer then :(
I found this problem on a Numbers & Sets for Enthusiasts sheet at university and copied it over. It was the last on the sheet and double starred, ie v hard. Sorry!