There are n men in a village. Each of them has a piece of juicy information about the private life of someone they all know. They want to share the information so that every one of them has all of it. And they want to do all of this by phone because they're all sick with different contagious diseases. And it's 1951 so there are no conference calls.
How many calls is the least they have to make between themselves?
Originally posted by WanderingKing6
There are n men in a village. Each of them has a piece of juicy information about the private life of someone they all know. They want to share the information so that every one of them has all of it. And they want to do all of this by phone because they're all sick with different contagious diseases. And it's 1951 so there are no conference calls.
How many calls is the least they have to make between themselves?
a calls b with item 1
b calls c with items 1 & 2
c calls d with itmes 1, 2 & 3
d calls e with items 1, 2, 3 & 4
e calls f with itmes 1, 2, 3, 4 & 5
a still needs a call to get the information
Originally posted by WanderingKing(n-1)^2 ... or less.
There are n men in a village. Each of them has a piece of juicy information about the private life of someone they all know. They want to share the information so that every one of them has all of it. And they want to do all of this by phone because they're all sick with different contagious diseases. And it's 1951 so there are no conference calls.
How many calls is the least they have to make between themselves?
Originally posted by WanderingKing(n-1)^2
How did you arrive at this number? An obvious bound is n^2, a slightly less obvious one is (n-1)*n/2.
It looked pleasant after a few drinks. 🙄
But isn't 2n-2 a possibility?
One person takes a call from all the others. (That is (n-1) calls).
He now knows everything.
He then informs the rest of the village. (Another (n-1) calls)
So it can be done in (2n-2) calls. Not sure how to prove that is minimum or even if it is minimum.
- Joined
- 26 Apr 03
- Moves
- 26771
8 people, a,b,c,d,e,f,g,h
first calls: ab, cd, ef, gh
second calls : ac, eg
third calls : cg
now c and g know everything
a calls e, now a and e know everything too
finish off by someone who knows everything calling b,d,f and h
So 12 calls are needed for 8 people.
Another way:
round 1: ab, cd, ef, gh
round 2: ac, bd, eg, fh
round 3: ae, cg, bf, gh
now they know everything, 12 calls again
So I think it is n * log2(n) if n is a power of 2
This must surely be a minimum, in the second way shown it is clear that everyone's amount of information is doubling in each round.
That's the correct number for 8 men.
About the log conjecture: for 2 men 1 call is enough! So even if it's true in some sense it must be honed. 🙂
Edit: Oh, and this contradicts wolfgang's conjecture, since 2*8-2 is 14. 🙂 But wolfgang's 2*n-2 is certainly correct as an upper bound so let's compare 2n-2 to n*log2(n).
We have n*log2(n)-(2n-2)=n(log2(n)-2)+2=n(log2(n/4))+2.
This is clearly positive for n>=4 because then log2(n/4)>=0. Actually, it's still positive for n=3. So, for n>=3, n*log2(2) is greater than the upper bound given by wolfgang, so it cannot be correct. That's another thing that needs to be taken care of if this idea is to be taken further. 🙂
- Joined
- 26 Apr 03
- Moves
- 26771
Ah yes sorry! n*log(2)/2
16 people should be 32 calls...
ab, cd, ef, gh, ij, kL, mn, op
ac, bd, eg, fh, ik, jL, mo, np
ae, cg, bf, dh, im, ko, jn, Lp
ai, em, ck, go, bj, fn, dL, Hp.
The idea is that with n/2 calls each round we can double the size of groups, where everyone in the group knows what everyone else in the group knows. It starts off with n groups of size 1, then n/2 group of size 2, then n/4 groups of size 4... etc.
Originally posted by iamatigerThere's a general problem with this function, the same that I mentioned in the previous post. x*log(x) grows faster than any linear function and wolfgang's bound (which is correct) is linear. Any idea around x*log(x) will have to take it into account and might be doomed because of the bound.
Ah yes sorry! n*log(2)/2
16 people should be 32 calls...
ab, cd, ef, gh, ij, kL, mn, op
ac, bd, eg, fh, ik, jL, mo, np
ae, cg, bf, dh, im, ko, jn, Lp
ai, em, ck, go, bj, fn, dL, Hp.
The idea is that with n/2 calls each round we can double the size of groups, where everyone in the group knows what everyone else in the group knows. It starts off with n groups of size 1, then n/2 group of size 2, then n/4 groups of size 4... etc.
Here's a plot of the function showing that x*log2(x)/2 is a convex function: http://postimg.org/image/5vp85c7sz/
Wolgang's observation gives us that for 16 men the number of necessary calls is not greater than 2*16-2=30. So 32 can't be the right number. 🙂
I think the two kinds of approach in your (wolfgang and tiger's) posts can complement each other. It's a good idea to give a general algorithm for any n as wolfgang did and try to show that it gives the optimal number of calls (which wolfgang refused to do 😉). Trying to get a "feel" for how the function grows as tiger did is also not a bad idea. 🙂
In any case I think it is clear by now that a proof that a certain solution, however obtained, is optimal will be the hard part.
- Joined
- 26 Apr 03
- Moves
- 26771
Hmm, actually Wolfgang's method is (n-1) + (n-2) = 2n-3 calls I think, because if person 'a' calls everyone else, then on the call where he finds everything out he can tell the person he is currently calling everything without incurring another call
that means my method beats Wolfgang's at n = 8, but at n-16 Wolfgang's method takes 29 calls and mine takes 32, so wolfgang is clearly best
But, how about we do this:
ab cd ef gh ij kl mn op
ac eg ik mo
ae im
ai
now a and i know everything, 15 calls so far (equal progress with wolfgang's method)
em
now a,i,e and m know everything 16 calls so far
in 12 more calls we can distribute the knowledge to the remainder
So we took 28 calls, one better than wolfgang's method
Theorem: Wolfgang's method is a worst case that can always be bettered when n is a power of 2
Very nice!
So to summarize: when n=2^k, we can do this in 2n-4 calls.
This is proven using your method: we need
(2^(k-1)+2^(k-2)+...+2^1+2^0)+1=(2^k-1)+1=2^k=n
calls to fully inform 4 people, and then n-4 calls are enough to inform the rest. Care needs to be taken of the initial values of course since we might not even have a group of 4.
For four people this method works. For two people the method is a bit meaningless and the formula doesn't work: it would imply that 0 calls are needed while 1 call is necessary. For one person we need 0 calls and the formula gives a negative number. But this is a formality. I'll list the values:
1 man - 0 calls,
2 men - 1 call,
3 men - 3 calls,
4 men - 4 calls.
These are easily verified to be optimal.
For n=2^k, k>1, we have a procedure to do it in 2n-4 calls.
There are two paths to take now. We could try to continue working on the powers of two (either show that 2n-4 is optimal for them or find a better algorithm), or we could try to take a look at other numbers, for which, so far, we know a procedure to do it in 2n-3 calls.