#### Posers and Puzzles

WanderingKing
Posers and Puzzles 05 Mar '15 02:34
1. 05 Mar '15 02:34
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?
2. coquette
05 Mar '15 07:21
Originally posted by WanderingKing
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?
6

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
3. wolfgang59
05 Mar '15 07:49
Originally posted by WanderingKing
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?
(n-1)^2 ... or less.
4. 05 Mar '15 08:54
Originally posted by coquette
6

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
Does b know item 3 after all of this? ðŸ™‚
5. 05 Mar '15 08:59
Originally posted by wolfgang59
(n-1)^2 ... or less.
How did you arrive at this number? An obvious bound is n^2, a slightly less obvious one is (n-1)*n/2.
6. wolfgang59
06 Mar '15 03:11
Originally posted by WanderingKing
How did you arrive at this number? An obvious bound is n^2, a slightly less obvious one is (n-1)*n/2.
(n-1)^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.
7. 06 Mar '15 13:422 edits
That's a great observation! Maybe taking a look at some small values of n would be a good idea now so we can test this bound.
8. 06 Mar '15 21:284 edits
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.
9. 07 Mar '15 00:011 edit
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. ðŸ™‚
10. 07 Mar '15 01:21
Oh, I didn't notice one thing. 8*log2(8)=24. Did you mean n*log2(n)/2?
11. 07 Mar '15 21:163 edits
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.
12. 07 Mar '15 22:123 edits
Originally posted by iamatiger
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.
There'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.

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. ðŸ™‚
13. 07 Mar '15 22:28
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.
14. 07 Mar '15 23:053 edits
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
15. 08 Mar '15 00:384 edits
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.