I was thinking about it, and this is what I came up with:
If everybody would call the same one person, which is n-1 calls, he would know all the secrets. And then he could call everybody, which is n-1 calls too, and tell them all that he knows.This gives us 2n-2 calls.
I don't know if this is the minimum number of calls, but I did what I could.

I hope you'll find the right answer.
Good Luck!
-Liliya

Judging by the given examples it's not.

> but I did what I could.

You got a good upper bound. I good problem is seldom solved in a single step. Furthermore, your first solution may suggest improvements.

For example, assume the number of people is 2n. Then your solution gives an estimate of 2(2n - 1) = 4n - 2.

Now, split the fellows into two groups of n people each and mark one fellow in each group. Proceed as follows:

1. Let the marked fellows call (n - 1) people in their respective groups. This takes 2(n - 1) calls.
   
2. Let one of the marked fellows call the other: one more call.
   
3. Repeat 1 with 2(n - 1) calls.
   

This leads to the total of

2·2(n - 1) + 1 = 4n - 3,

which is less than your estimate.

If there are 4n people, we'll split them into 2 groups of 2n people each. In each group we need 4n - 3 with one call in-between between the two groups. This gives you

2(4n - 3) + 1 = 8n - 5,

which is better than 8n - 3 of the previous estimate.

>2ž2(n - 1) + 1 = 4n - 3,

>which is less than your estimate.

I don't agree with you.
In your case you need one more extra call. And the more groups you divide you'll need more extra calls.

2n-2 is less than 4n-3 or 8n-5.

Am I right??

-Liliya

What for?

>And the
>more groups you divide you'll
>need more extra calls.

To see how it works, try small numbers like 4, 8, etc.

For 4 you have two groups: 2 and 2. The first fellow in each group makes a call to the other fellow. In the notations of the original poster:

1, 2, 3, 4
12, 12, 34, 34

Then the first fellows talk to each other:

1234, 12, 1234, 34

Then it takes 2 more intragroup calls:

1234, 1234, 1234, 1234

In all, 5 calls for n = 4. Your estimate would give 2(4 - 1) = 6 calls, right?

>2n-2 is less than 4n-3 or
>8n-5.
>
>Am I right??

Yes, of course, but this is irrelevant here. n is different from expression to expression. In words your formula says "Twice the number minus 1." If the number is n, then the result is 2(n - 1). If the number is 2n, the result is 2(2n - 1), and so on.

In the previous post, I considered two cases of the number being 2n and 4n.

What's the answer to Manoj's question??

Empirically it'seems to be 2n-4 from the examples listed in the original post. However I am not satisfied until the problem can be formulated and solved. Cant seem to find a proof by induction. My gut feel tells me that it could have something to do with the range of the given number ie: <=4, <=16, <=64 <=256 and a div()/mod() in the resultant formula. But then I may be totally wrong.

For eg: if <=4 then seems to be 2*n-3

For 4<n<=16 seems to be 2n-4

So can we extend this?

>My
>gut feel tells me that
>it could have something to
>do with the range of
>the given number ie

Right

><=4,
><=16, <=64 <=256 and a
>div()/mod() in the resultant formula.
>But then I may be
>totally wrong.

You are, but not totally.

The relevant ranges are 4, 8, 16, 32, ...

>For eg: if <=4 then seems
>to be 2*n-3
>
>For 4<n<=16 seems to be 2n-4

For 8, it's 11. How does it fit with your formula?

You can prove by induction that for N = 2ⁿ, n > 1, that 3N/2 - 1 is a sufficient number of calls. Whether it's minimal I do not know. Whether you can interpolate between the powers of 2, I do not know either.

>For 8, it's 11. How does it fit with your formula?
Hi Alex

I simply cannot figure out how to arrive at 11 calls for 8 people. The best I can do is 12 calls. Neither can I figure out how you got the formula 3N/2-1 for N=2^n. To me the formula seems to be n*2^(n-1).

Anyway, here are a couple of elegant 'proofs' that I got from the sci.math groups. Each prove that 2N-4 is sufficient, but not minimal.

Math Induction:
Step 1 Prove that the solution is valid for some n>=4
Step 2 For N=N+1, have the 'new' person call any one person (1 call)
Step 3 For the N persons excluding the 'new' person, share the secret as
before. All N people now know the 'new' persons secret. (2N-4 calls) per
formula
Step 4 One from this N calls up the 'new' person (1 call)
Step 5 Total for N+1 = 1+2N-4+1 = 2N-2 = 2(N+1) -4. Hence valid for N=>
valid for N+1

Or intuitive one ...
Number the people from 1...n. Have person 1 call all people greater than 4.
(N-4) calls.
Now 1..4 share the secret in 4 calls (4 calls)
Now the person 1 calls all people greater than 4 again. (N-4 calls)
Total = N-4+4+N-4 = 2N-4.

Still no solution that it is indeed least number of calls. And no formulation in sight for my added twist.

Manoj.

If 2N-4 is minimal, then a solution, or rather two solutions, to your "bookkeeping" twist are strongly suggested by the forms of the inductive arguments you noted. With the tiniest bit of tidying up you can turn either into an algorithm. As long as each person knows his part in the algorithm, he doesn't need to know who has called whom or what anyone else knows.

In the third step, how did you come up with 2n-4?

Or intuitive one ...
Number the people from 1...n. Have person 1 call all people greater than 4.
(N-4) calls.
Now 1..4 share the secret in 4 calls (4 calls)
Now the person 1 calls all people greater than 4 again. (N-4 calls)
Total = N-4+4+N-4 = 2N-4.

How can 4 people share their secrets in 4 calls?

One more question.
I simply don't understand how you came up with this:
2n-4 is for 4<n<=16

I would appreciate if someone would answer my questions.

-Liliya

Anyway, the induction hypothesis in the first proof was that
2n-4 was an upper bound for the number of calls needed to fully share information among n people. Because it was the induction hypothesis, he could use it to show that 2(n+1)-4 is an upper bound for the case of n+1 people.

Although he alluded to the crucial first step of his induction proof, he did not go into the details. The first step (which also answers your second question) is to prove that 2k-4 is an upper bound for some number of people, in this case, 4.

Using Manoj Nair's notation:

12, 12, 3, 4
12, 12, 34, 34
1234, 12, 1234, 34
1234, 1234, 1234, 1234

Four people, four phone calls.

www.cut-the-knot.com/induction.shtml

From time to time, one sees new variations on this problem, and
extensive lists of references have been published. Unfortunately, I don't have any of them handy right now.