Welcome to NRICH.

 
Spreading secrets problem
By Anonymous on Tuesday, August 29, 2000 - 08:03 pm:

Hello,

I was wondering if someone could help me with the following problem:

n people each know one, different secret. When any two people speak together on the telephone, then can exchange as many secrets as they know; what is the least number of telephone calls necessary for all n people to know all n secrets?

Thank you in advance,

Anon

By Marcus Hill (T3280) on Tuesday, September 26, 2000 - 10:57 pm:

This is one best attacked by considering specific values of n and seeing a pattern, not just in the numbers but in how you distributed the secrets efficiently.

By Chris Jefferson (Caj30) on Sunday, September 3, 2000 - 11:33 pm:

Hmm.. Here's my attempt at it.

Obviously everyone must know everyone else's secret.

So unless one person knows everyone's secret, it will take at least 2 people communicating with them to learn all the secrets.

Only one person can only be phoned once, by someone who knows everyone's secret except theirs. (Make sure you agree with this bit, it's important.)

So therefore we get a possible minimum of:

(n-1)×2 + 1

Where one person is rung once with all the secrets, and everyone else is rung twice. Now we have this as a minimum, can we achieve it?

Yes we can, we pick one person, and everyone rings them and they swap secrets. Now that person rings everyone back EXCEPT the last person to ring him, who already knows all the secrets. This gives (n-1)×2 + 1..

I'm not 100% sure that is watertight, although at 11:30 at night, I can't spot any problems in it!

Whenever you are faced with a problem like this, the best way to tackle it is to try to get a value for the minimum a solution MIGHT be, and then get a solution for that value.

Anyway, do write back if you didn't follow that or you think I've made a mistake :-)

Chris Jefferson

By Arvan Pritchard (T708) on Monday, September 4, 2000 - 09:27 am:

That does give a scheme for sharing all the solutions, and so an upper bound for the minimum solution.

It is not however the minimum solution. Here is a better one, but I don't know if it is minimum.

If you have 4 people you can share all the secrets in 4 calls

A calls B - A and B know 2 secrets
C calls D - C and D know the other 2 secrets
A calls C - A and C know all secrets
B calls D - everyone knows all secrets

You can extend a solution for n people to one for n+1 people by having the extra person call someone before and after the n people share all their secrets.

This gives a solution for 4 or more people in (n×2)-4 calls.

By Alex Barnard (Agb21) on Sunday, October 1, 2000 - 11:16 pm:

Well, I know the answer - and a little experimentation leads you to guess it. However the actually proof is really messy and so I won't be posting it!

3 people need 2 phone calls
4 people need 4 phone calls
5 people need 6 phone calls
6 peolpe need 8 phone calls
7 people need 10 phone calls
8 people need 12 phone calls

After this it starts to get a little tricky to do by hand. But, I'd say, the pattern is now obvious. The number of phone calls needed is 2n-4.

Now, it's really easy (!!) to show that you can always distribute your secrets with 2n-4 phone calls. What is messy is showing that you can't do any better than that.

AlexB.